3-10 The Static Queue

The Concept of a Queue

We’ve all stood in line at one time or another. The way a line is supposed to work is that new people enter the line at the end (or “tail”) and people exit the line at the front (or “head”). People that “bud-in” or jump a line are frowned upon. You may have heard the word “queue” used in reference to a line of people before.

In computer science, a queue is another data structure that holds items in a sequence. Unlike the stack however, the elements in a queue are added at the tail (end) and removed from the head (front). A queue is a First In, First Out (FIFO) data structure, a name reflecting the fact that the first element enqueued (added) to the queue is the first item to be dequeued (removed) from it. In other words, elements may only be removed from the queue in the same order in which they were placed in the queue.

Queue ADT Interface

As with a stack, a queue is expected to support certain operations:

To add (“enqueue“) an element to the tail (end) of the queue (must not be full).

To remove (“dequeue“) an element at the head (front) of the queue (must not be empty).

To look (“peek“) at the element at the head of the queue, but not remove it.

To check if the queue is empty (“isEmpty“).

To check how many elements are in the queue (“size“).

To clear all elements from the queue (“clear“).

Defining an interface for a queue ADT is clear-cut:

public interface QueueADT<T> {
    // Adds one element to the top of the queue.
    public void enqueue(T element);
    
    // Removes and returns a reference to the front element of the queue.
    public T dequeue();
    
    // Returns a reference to the front element, without removing it from the queue.
    public T peek();
    
    // Returns true if the queue contains no elements, false otherwise.
    public boolean isEmpty();
    
    // Returns the number of elements in the queue.
    public int size();

    // Clears all elements from the queue
    public void clear();
    
    // Returns a String representation of this queue.
    public String toString();   
}

public interface QueueADT<T> {

// Adds one element to the top of the queue.

public void enqueue(T element);

// Removes and returns a reference to the front element of the queue.

public T dequeue();

// Returns a reference to the front element, without removing it from the queue.

public T peek();

// Returns true if the queue contains no elements, false otherwise.

public boolean isEmpty();

// Returns the number of elements in the queue.

public int size();

// Clears all elements from the queue

public void clear();

// Returns a String representation of this queue.

public String toString();

}

Now it’s your turn!

You Try!

Based on the StaticStack and StaticStackTest classes from last day and using the QueueADT interface code above, implement your own StaticQueue class and StaticQueueTest class to demonstrate all operations.