Queue and Queue Applications

last updated 3/12/18

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)

Structure:

A list where only the oldest item is accessible.


Applications:

Typical uses of queues are in simulations and operating systems.

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

Boundedness is supported by two versions of the Queue ADT:

We define an interface to represent the operations


The Queue Interface

public interface QueueInterface <T> {
  public void enqueue(T element) throws QueueOverflowException;
// Throws QueueOverflowException if this queue is full,
// otherwise adds element to the rear of this queue.
public T 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 boolean isFull();
    // Returns true if this queue is full, otherwise returns false.
  }

  public int size();
    // Returns the number of elements in this queue.
  }
 }
	 

 


Queue Demonstration

 

Queue Operations: size: isEmpty:

Value to Add:

Front:

 

 

 

 


Array Implementation

The text initially introduces the idea that we enqueue like appending a value to the array and dequeue as removing the front element and moving all the entries up to close the hole. Exactly like we did with the sound mashups. This costs linear time for each dequeue operation.

front is always element 0

rear of queue is at the end of the array

Solution for more efficiency is to NOT move the elements but track the front by moving a pointer to the next front and the rear similarly. Reuse the array by wrapping around the end of the array.

 

 


Implementation

public class ArrayBoundedQueue<T> implements QueueInterface <T> 
{
protected final int DEFCAP = 100; // default capacity
protected T[] elements; // 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 ArrayBoundedQueue() 
{
   ArrayBndQueue(DEFCAP);
}
public ArrayBoundedQueue(int maxSize) 
{
   elements = (T[]) new Object[DEFCAP];
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 == elements.length);
}

public int size()
   // Returns the number of elements in this queue.
{
   return numElements; 
} 
public void enqueue(T 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) % elements.length;
elements[rear] = element;
numElements++;
}
}
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 {
T temp = queue[front];
elements[front] = null;
front = (front + 1) % elements.length;
numElements --;
return temp;
}
}

 


Unbounded Array Implementation

If the array fills, one could double the size of the array and copy it--like ArrayList does. We don't do this, normally

 

 


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.)

"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

    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

    StackInterface <Character> stack;   // holds non blank string characters
    QueueInterface <Character> queue;   // also holds non blank string characters

    // initialize variables and structures
    length = candidate.length();
    stack = new ArrayBoundedStack<Character>(length);
    queue = new ArrayBoundedQueue<Character>(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;
    while (stillPalindrome && !stack.isEmpty())
    {
      fromStack = stack.top();
      stack.pop();
      fromQueue = queue.dequeue();
      if (fromStack != fromQueue)
        stillPalindrome = false;
    }
    
    // return result
    return stillPalindrome;
  }
}

//---------------------------------------------------------------------
// PalindromeCLI.java       by Dale/Joyce/Weems               Chapter 4
//
// Checks for strings that are palidromes.
// Input consists of a sequence of strings.
// Output consists of whether the input string is a palindrome.
// LKR -- This is from the earlier edition.  This works too.
//----------------------------------------------------------------------

import java.util.Scanner;

public class PalindromeCLI 
{
  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 LLNode class we used for the linked implementation of stacks.

Track front and rear:

Linked List Queue


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

Linked list enqueue

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

Linked List Dequeue operation


Unbounded Linked List Queue

public class LinkedQueue<T> implements QueueInterface<T>
{
  protected LLNode<T> front; // reference to the front of this queue
  protected LLNode<T> rear;  // reference to the rear of this queue
  protected int numElements=0;  // number of elements in this queue

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

  public void enqueue(T element)
  // Adds element to the rear of this queue.
  { 
    LLNode<T> newNode = new LLNode<T> (element);  
    if (rear == null)   
      front = newNode;  
    else
      rear.setLink(newNode);  
    rear = newNode;
    numElements ++;
  } 

  public T 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 {
      T temp = front.getInfo();
      front = front.getLink();
    if (front == null)
        rear = null;
    numElements --;
    return temp;
  }
}



Circular linked list queue

Circular linked list queue

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

 


Comparing the implementations.

Visualizing the array versus the linked list implementations

 


Double Ended Queues (deques)

Treat each end as a place to push and pop.

Interface

public interface DequeInterface 
{
  void enqueueFront(T element) throws QueueOverflowException;
  // Throws QueueOverflowException if this queue is full;  
  // otherwise, adds element to the front of this queue.

  void enqueueRear(T element) throws QueueOverflowException;  
  // Throws QueueOverflowException if this queue is full;  
  // otherwise, adds element to the rear of this queue.

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

  T dequeueRear() throws QueueUnderflowException;
  // Throws QueueUnderflowException if this queue is empty;
  // otherwise, removes rear element from this queue and returns it.

  boolean isFull();  
  boolean isEmpty(); 
  int size();
}

An implementation of a deque is best with a doubly linked list.


Queues in the Java Standard library

Elements are always removed from the “front” of the queue.

Two operations for enqueuing:

As with the library Stack, the library Queue was supplanted by the Deque with the release of Java 6.0 in 2006

There are four library classes that implement the Deque interface: