Queues

• A queue is a container: it stores a set of objects, which are accessed in a specific way.
• All elements in the queue are the same type.
• A queue is a FIFO (first in first out) container. The objects in the queue are retrieved in the same order in which they were inserted. Queues are used when there is a need to provide fair service.
• The queue data structure is similar to a line or queue of physical objects where you add an item at the end of the queue and remove an item from the front of the queue. It is only possible to add an item at the end and remove an item from the front. Some examples:
• a queue of people waiting at the post office or cashier
• a line of cars waiting at a toll booth
• files waiting to print
• messages waiting to be processed: data being sent between programs or between hardware devices are held in a "buffer", which is often implemented as a queue; for example, mail messages that are to be processed by the mail server
• The insert method for a queue is called enqueue. It can also be called enq, enque, add, or insert.
• The delete method for a queue is called dequeue. It can also be called deq, deque, remove, or delete.
• The end of the queue that is used for adding elements is called the rear (or back); when we draw a queue the rear is the right end of the queue.
• The end of the queue that is used for removing elements is called the front; when we draw a queue the front is the left end of the queue.

Example

Suppose we have a queue of Strings. The following shows some queue calls. Draw a picture of the queue after the first 4 statements, after the 6th statement, and then after the last statement. Also show the value of str after each dequeue.

   qq.enqueue("blue");
   qq.enqueue("red");
   qq.enqueue("green");
   str = qq.dequeue();
   qq.enqueue("black");
   str = qq.dequeue();
   qq.enqueue("yellow");
   str = qq.dequeue();
   str = qq.dequeue();

Queue Interface

As in the stack, we use the Java interface construct to specify the public interface of our queue. We create a generic queue so that the class can contain any type of object needed by the client code.

We have discussed the main methods of the queue: enqueue and dequeue. As with the stack we need exceptions to handle the attempt to add an element to a full queue or remove an element from an empty queue.

The Queue interface from our textbook.

Queue Implementation: Array

To implement the queue we need to be able to store a collection of elements. The elements need to be kept in order so that we can access them according to the specification of the queue (FIFO). In the stack we used topIndex to keep track of the position of the top item in the array. For the queue we will have front and rear to keep track of the position of the front and rear items in the array.

One way to implement the queue is to use an array. Suppose the front is at the beginning of the array (starting at position [0]). Each enqueue will add the new element after (at a higher subscript) than the last element. Each dequeue will remove the element currently at the front. Draw an array with 10 positions and see what happens if you perform the sequence of enqueues and dequeues shown above.

You can see that, unlike the stack, the queue is moving in the array and if we keep going we will run out of room to enqueue. But we're not necessarily running out of room; we may still have room, but not at the end of the array. We need to be able to reuse the unused positions at the beginning of the array.

One option is to move all the elements so that the front element is at position [0]. Then we can keep adding elements at the rear. Another option is to always keep the front element at position [0]. Both of these options are unacceptable. Why?

We choose a different option, one which results in enqueue and dequeue methods with lower complexity. In this approach, called the "floating-front design approach" in the textbook, we reuse the empty positions at the begninng of the array by wrapping the queue around to the beginning of the array.

For example, the following statements will result in the following queue:

   qq.enqueue("yes");
   qq.enqueue("no");
   qq.enqueue("ok");
   str = qq.dequeue();
   qq.enqueue("hi");
   str = qq.dequeue();
   qq.enqueue("far");
   qq.enqueue("bat");

This leads to the following code for enqueue, where capacity is the size of the array that is holding the queue:

if (rear == capacity-1)
   rear = 0;
else
   rear++;

However, queue implementations usually use the following equivalent code:

rear = (rear + 1) % capacity;

And what about dequeue? Can the front also wrap around and reach the front of the array? Start with the last queue in the example above, and show a sequence of enqueues and dequeues that cause front to wrap around. Show front, back and the array for each operation.

How do you think we should update front in the dequeue method?

How should front and rear be initialized when creating a new, empty queue? We want to initialize them so that the first enqueue works correctly. And once there is something in the queue we want the first dequeue to work correctly. To figure this out, remember that the first enqueue is going to place the element in location [0]. What value of rear will cause enqueue to put the element in location [0]? If the first element is in location [0], what value of front will cause dequeue to remove the element in that location? These questions lead us to the following initial values for front and rear:

The textbook has two array based queue classes. The ArrayBoundedQueue class is similar to the stack, in that the array determines the maximum size of the queue. The enqueu method in the ArrayUnboundedQueue does not throw an exception if the array is full. Instead, it creates a larger array and copies all elements of the queue to this new array.

Here is the ArrayUnboundedQueue class. Notice that we include a field for the number of elements in the queue, which is used by isEmpty(), isFull(), and size().

Complexity

Look at the code for the ArrayUnboundedQueue methods. For a queue containing N elements, what is the best case and worst case of each of the following? Count the number of times each statement executes as a function of N, then get the big O.

enqueue

dequeue

size

isEmpty

isFull

Queue Implementation: Linked

We need to be able to access both ends of a queue. Suppose the front of the queue is in the first node. If we have a list with a pointer to the first node, like we have in the stack class, how can we reach the node at the other end of the list?

To avoid having to loop to find the last node, we will keep a pointer to the last node in the list:

public class LinkedQueue<T> implements QueueInterface<T> {
   protected LLNode<T> front;
   protected LLNode<T> rear;
   protected int numElements;

}

Draw a picture below of an empty queue, a queue of Strings that contains only the element "one", and a queue that contains "one", "two", and "three".

To enqueue, we will add the new element at the end of the list. Write the code for this below:

To dequeue, we will remove the element at the front of the list. Write the code for this below:

Here is the LinkedQueue class.

Complexity

Look at the code for the LinkedQueue methods. For a queue containing N elements, what is the best case and worst case of each of the following? Count the number of times each statement executes as a function of N, then get the big O.

enqueue

dequeue

size

isEmpty

isFull

Alternative Version: Glass Queue

You may have noticed that there is nothing like the top method for the queue. To see what's at the front of the queue it must be dequeued. And then what happens to its position in the queue when it is enqueued?

If an application needs to see what is in the queue without removing the item, it can use a "glass queue", which has additional methods to allow the client code access to the items at the front and rear of the queue:

public interface GlassQueueInterface extends QueueInterface {
   public T peekFront();
   // If the queue is empty, returns null.
   // Otherwise returns the element at the front of this queue.

   public T peekRear();
   // If the queue is empty, returns null.
   // Otherwise returns the element at the rear of this queue.
}

What is the code for these methods in the array based queue?

What is the code for these methods in the linked queue?

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2017