Queue and Queue Applications

Queue

From the taxonomy this structure is Linear - Sequential Access - First-in-First-out

Features:

1. A list  structure with two access points called the front and rear.
2. All insertions (enqueue) occur at the rear and deletions (dequeue) occur at the front.
3. Varying length (dynamic).
4. Homogeneous components
5. Has a First-In, First-Out characteristic (FIFO)

Domain:

1. a collection of component values all of the same type
2. two implicit cursors that tracks the oldest component (front) and the newest component (rear)

A list where only the oldest item is accessible.

Applications:

Typical uses of queues are in simulations and operating systems.

• Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.
• Computer systems must often provide a “holding area” for messages between two processes, two programs, or even two systems. This holding area is usually called a “buffer” and is often implemented as a queue.

Our software queues have counterparts in real world queues. We wait in queues to buy pizza, to enter movie theaters, to drive on a turnpike, and to ride on a roller coaster. Another important application of the queue data structure is to help us simulate and analyze such real world queues.

Queue Operations and Specifications

enqueue - adds an element to the rear of a queue
dequeue - removes and returns the front element of the queue

To complete the formal specification of the Queue ADT we need to identify and address any exceptional situations and determine boundedness.

Exceptional Situations

• for dequeue – what if the queue is empty? throw a QueueUnderflowException
• plus define an isEmpty method for use by the application
• for enqueue – what if the queue is full? throw a QueueOverflowException
• plus define an isFull method for use by the application

Boundedness is supported by two versions of the Queue ADT:

• a bounded version
• an unbounded version

We define three interfaces

• QueueInterface: features of a queue not affected by boundedness
• BoundedQueueInterface: features specific to a bounded queue
• UnboundedQueueInterface: features specific to an unbounded queue

The Queue Interface

public interface QueueInterface {

    public Object dequeue() throws QueueUnderflowException;
   // Throws QueueUnderflowException if this queue is empty,
   // otherwise removes front element from this queue and returns it.

 public boolean isEmpty(); 
  // Returns true    if this queue is empty, otherwise returns false.
 

 }

 public interface BoundedQueueInterface extends QueueInterface
{
  public void enqueue(Object element) throws QueueOverflowException;
  // Throws QueueOverflowException if this queue is full,
  // otherwise adds element to the rear of this queue.

public boolean isFull();
   // Returns true if this queue is full, otherwise returns false.
   }
}

public interface UnboundedQueueInterface extends QueueInterface
{
  public void enqueue(Object element);
  // Adds element to the rear of this queue.
} 
    

Queue Demonstration

Array Implementation

Like a stack, an array is simple to use but has the limitation that the array may overflow.

Solution to reuse the array is to wrap around the end of the array.

Implementation

public class ArrayBndQueue implements BoundedQueueInterface 
{
  protected final int defCap = 100; // default capacity
  protected Object[] queue;         // array that holds queue elements protected int origCap;            // original capacity
  protected int numElements = 0;    // number of elements n the queue
  protected int front = 0;          // index of front of queue
  protected int rear = -1;          // index of rear of queue

 public ArrayBndQueue() 
   {
     ArrayBndQueue(defCap);
   }

 public ArrayBndQueue(int maxSize) 
   {
      queue = new Object[maxSize];
      rear =  maxSize - 1;
   } 

public boolean isEmpty()
// Returns true if this queue is empty, otherwise returns false
{              
  return (numElements == 0);
}

public boolean isFull()
   // Returns true if this queue is full, otherwise returns false.
   { 
   return (numElements == queue.length);
   } 

public void enqueue(Object element)
// Throws QueueOverflowException if this queue is full,
// otherwise adds element to the rear of this queue.
{
  if (isFull())
    throw new QueueOverflowException(
               "Enqueue attempted on a full queue.");  
  else {
    rear = (rear + 1) % queue.length;
    queue[rear] = element;
    numElements = numElements + 1;
  }
} 

public Object dequeue()
// Throws QueueUnderflowException if this queue is empty,
// otherwise removes front element from this queue and returns it.
{       
  if (isEmpty())
    throw new QueueUnderflowException("Dequeue attempted on empty queue.");  
  else {
    Object toReturn = queue[front];
    queue[front] = null;
    front = (front + 1) % queue.length;
    numElements = numElements - 1;
    return toReturn;
  }
}


  

Applications

Many examples in a computer's operating system

Requests for services come in unpredictable order and timing, sometimes faster than they can be serviced (like at a bank window, cafeteria, etc.)

• print a file
• need a file from the disk system
• send an email

"The print file is in the queue". Your outbox is a queue.

Palindrome strings as an example (a pure stack solution is also possible).

“A man, a plan, a canal—Panama!”
“Able I was ere, I saw Elba.”
“Won ton? Not now!”
“Madam, I’m Adam.”
“Eve.”

//---------------------------------------------------------------------
// Palindrome.java           by Dale/Joyce/Weems              Chapter 5
//
// Provides a method to test whether a string is a palindrome. 
// Non letters are skipped.
//---------------------------------------------------------------------

import ch03.stacks.*;
import ch05.queues.*;

public class Palindrome 
{
  public static boolean test(String candidate)
  // Returns true if candidate is a palindrome, false otherwise.
  {
    char ch;                   // current candidate character being processed
    int length;                // length of candidate string
    int numLetters;            // number of letter characters in candidate string
    int charCount;             // number of characters checked so far

    char fromStack;            // current character popped from stack
    char fromQueue;            // current character dequeued from queue
    boolean stillPalindrome;   // true as long as the string might still be a palindrome

    BoundedStackInterface stack;   // holds non blank string characters
    BoundedQueueInterface queue;   // also holds non blank string characters

    // initialize variables and structures
    length = candidate.length();
    stack = new ArrayStack(length);
    queue = new ArrayBndQueue(length);
    numLetters = 0;

    // obtain and handle characters
    for (int i = 0; i < length; i++)
    {
      ch = candidate.charAt(i);
      if (Character.isLetter(ch))
      {
        numLetters++;
        ch = Character.toLowerCase(ch);
        stack.push(ch);
        queue.enqueue(ch);
      }
    }
    
    // determine if palindrome
    stillPalindrome = true;
    charCount = 0;
    while (stillPalindrome && (charCount < numLetters))
    {
      fromStack = (Character)stack.top();
      stack.pop();
      fromQueue = (Character)queue.dequeue();
      if (fromStack != fromQueue)
        stillPalindrome = false;
      charCount++;
    }
    
    // return result
    return stillPalindrome;
  }
}

//---------------------------------------------------------------------
// PalindromeApp.java       by Dale/Joyce/Weems               Chapter 5
//
// Checks for strings that are palidromes.
// Input consists of a sequence of strings.
// Output consists of whether the input string is a palindrome.
//----------------------------------------------------------------------

import java.util.Scanner;

public class PalindromeApp 
{
  public static void main(String[] args)
  {
    Scanner conIn = new Scanner(System.in);

    String candidate = null;     // string to be evaluated
    String more = null;          // used to stop or continue processing

    do
    {
      // Get next candidate string to be processed.
      System.out.println("Enter a string to be evaluated: ");
      candidate = conIn.nextLine();
      
      // Obtain and output result of palindrome testing.
      if (Palindrome.test(candidate))
        System.out.println("is a palindrome.");
      else
        System.out.println("is NOT a palindrome.");

      // Determine whether there is another candidate string to process.
      System.out.println();
      System.out.print("Evaluate another string? (Y=Yes): ");
      more = conIn.nextLine();
      System.out.println();

    }
    while (more.equalsIgnoreCase("y"));
  }
}

Implementing a queue as a linked list

The limitations of using an array for a stack are the same as using an array for a queue.

For nodes we use the same LLObjectNode class we used for the linked implementation of stacks.

Track front and rear:

Enqueue and Dequeue operations

Enqueue at rear so that dequeue is "pop" from front

1. Create a node for the new element
2. Insert the new node at the rear of the queue
3. Update the reference to the rear of the queue
   if front==null then front = rear

Dequeue operation

1. Set element to the information in the front node
2. Remove the front node from the queue
   if the queue is empty
        Set the rear to null
   return element
   

Unbounded Linked List Queue

public class LinkedUnbndQueue implements UnboundedQueueInterface
{
  protected LLObjectNode front; // reference to the front of this queue
  protected LLObjectNode rear;  // reference to the rear of this queue

  public LinkedUnbndQueue()
  {
    front = null;
    rear = null;
  }

  public void enqueue(Object element)
  // Adds element to the rear of this queue.
  { 
    LLObjectNode newNode = new LLObjectNode(element);  
    if (rear == null)   
      front = newNode;  
    else
      rear.setLink(newNode);  
    rear = newNode;
  } 

  public Object dequeue()
  // Throws QueueUnderflowException if this queue is empty,
  // otherwise removes front element from this queue and returns it.
  {
    if (isEmpty())
      throw new QueueUnderflowException("Dequeue attempted on empty queue.");
    else {
      Object element = front.getInfo();
      front = front.getLink();
    if (front == null)
        rear = null;
    return element;
  }
}

Circular linked list queue

Only need one pointer to track the rear since rear.getNext() would serve as the front.