13.1. Queues¶
13.1.1. Queue Terminology and Interface¶
Like the stack, the queue is a list-like structure that provides restricted access to its elements. Queue elements may only be inserted at the back (called an enqueue operation) and removed from the front (called a dequeue operation). Queues operate like standing in line at a movie theater ticket counter.
If nobody cuts in line, then newcomers go to the back of the line. The person at the front of the line is the next to be served. Thus, queues release their elements in order of arrival. In Britain, a line of people is called a “queue”, and getting into line to wait for service is called “queuing up”. This behavior is called “First-In, First-Out” (FIFO), contrasting with the “Last-In, First-Out” behavior of the stack.
This section presents two implementations for queues: a LinkedList-based and (circular) array-based queue. We first show the interface we will implement:
public interface MHCQueue<E> {
// Add an item to end of queue
public void enqueue(E item);
// Get item waiting the longest
public E front();
// Remove and return item from front of queue
public E dequeue();
// Check if queue is empty, are there any items waiting?
public boolean isEmpty();
// Return number of items in queue
public int size();
}
The main operations we will focus on are enqueue, dequeue, and front:
enqueue: Add an item to the end of the queuedequeue: Remove and return the item at the front of the queuefront: Return the item at the front of the queue without removing it
13.1.2. LinkedList Queue¶
We can use some of our existing functionality from the linked list to implement a queue. Below is a full implementation of the MHCQueue interface:
import java.util.LinkedList;
import java.util.NoSuchElementException;
public class LinkedListQueue<E> implements MHCQueue<E> {
private LinkedList<E> values;
public LinkedListQueue() {
values = new LinkedList<>();
}
public void enqueue(E item) {
values.addLast(item);
}
public E front() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return values.getFirst();
}
public E dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return values.removeFirst();
}
public boolean isEmpty() {
return values.isEmpty();
}
public int size() {
return values.size();
}
}
A singly linked list is a good choice to implement a queue because we can add to the end of the list in constant time, and remove from the front of the list in constant time.
We also maintain references to both head and tail pointers, which correspond naturally to the front and back of the queue!
We store this backing singly linked list in the values instance variable:
public class LinkedListQueue<E> implements MHCQueue<E> {
private LinkedList<E> values;
13.1.2.1. front()¶
The front() method returns the item at the front of the queue without removing it:
public E front() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return values.getFirst();
}
Like the stack, we need to check if the queue is empty. If it is, we throw a NoSuchElementException. Otherwise, we return the item at the front of the queue using the LinkedList getFirst() method, which simply returns the value stored at the head node.
13.1.2.2. enqueue()¶
The enqueue() method adds an item to the end of the queue:
13.1.2.3. dequeue()¶
The dequeue() method removes and returns the item at the front of the queue:
Because we are using a singly linked list with head and tail pointers, our enqueue() and dequeue() operations are both constant time operations. Can we achieve this same performance with an array-based queue?
13.1.3. Attempting an ArrayList Queue¶
Our first attempt might be to use an ArrayList to store the queue, much like we did for the LinkedList-based implementation above. However, we run into a problem:
What we see is that no matter which end we choose to represent the front of the queue, we end up with a performance hit for either the enqueue() or dequeue() operations: one of them ends up being $O(n)$ time!
13.1.4. Circular Array-Based Queue¶
Let’s instead try to implement a queue building off an array. We explicitly keep track of the first and last positions of the queue, as well as the size of the queue:
// instance variables for our array-based queue
private E[] values;
private int first;
private int last;
private int size;
In particular, because we now maintain a first and last index, we can have the “front” of the queue shift around as elements are enqueued and dequeued:
Because of this drifting, we can only call enqueue() n times (where n is the length of our array) before we run out of space!
This problem can be fixed by treating the array as circular, where we “wrap around” the array once we get to the end of it:
Throughout all of this, we maintain a size variable to keep track of when the array backing the queue is at capacity.
Keeping this representation in mind, let’s implement the MHCQueue interface using a circular array. Below is the full implementation:
import java.util.NoSuchElementException;
public class CircularArrayQueue<E> implements MHCQueue<E> {
int first; // index of front of queue
int last; // index of last element of queue
int size; // how many items are in queue
int capacity; // maximum number of items queue can hold
E[] values; // array for data
// Don't worry about the suppress warnings, it is a weird quirk of Java to
// get the generic array working.
@SuppressWarnings("unchecked")
public CircularArrayQueue() {
capacity = 10; // default capacity to 10
values = (E[]) new Object[capacity];
first = 0;
last = capacity - 1;
size = 0;
}
@SuppressWarnings("unchecked")
private void grow() {
// double the capacity
capacity = 2 * capacity;
E[] newValues = (E[]) new Object[capacity];
// copy elements from old array to new array, maintaining order and placing first at the beginning
int j = first;
for (int i = 0; i < size; i++) {
newValues[i] = values[j];
j = (j + 1) % size;
}
// update instance variables
first = 0;
last = size - 1;
values = newValues;
}
public E front() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return values[first];
}
public void enqueue(E item) {
// Grow values array if needed
if (size == capacity) {
grow();
}
// Update last to next position,
// wrapping around if necessary
last = (last + 1) % capacity;
// Add item to the end of the queue
values[last] = item;
// Increment size
size++;
}
public E dequeue() {
if (isEmpty()) {
throw new NoSuchElementException();
}
// get item from the front of the queue
E item = values[first];
// "remove" item from the front
// of the queue by updating first
first = (first + 1) % capacity;
// decrement size
size--;
return item;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
}
13.1.4.1. Circular Queue Instance Variables¶
The instance variables for our circular queue are as follows:
public class CircularArrayQueue<E> implements MHCQueue<E> {
int first; // index of front of queue
int last; // index of last element of queue
int size; // how many items are in queue
int capacity; // maximum number of items queue can hold
E[] values; // array for data
Much like how we did for our implementation of ArrayList, we maintain an array of generic values to store our data. We also maintain first and last indices to keep track of the front and back of the queue, as well as a size variable to keep track of how many elements are in the queue.
Also, just like an ArrayList, we need to be able to dynamically grow our array when it becomes full. We use the capacity variable to keep track of the current capacity of our array, and we use the grow() method to resize our array when it becomes full.
Note
We’ll walk through the grow() implementation in lecture!
13.1.4.2. Circular queue enqueue()¶
The enqueue() method adds an item to the end of the queue:
13.1.4.3. Circular queue dequeue()¶
The dequeue() method removes and returns the item at the front of the queue:
13.1.5. Comparison of Circular Array and LinkedList Queue Implementations¶
Operation |
Circular Array-Based |
LinkedList-Based |
|---|---|---|
enqueue() |
O(1) |
O(1) |
dequeue() |
O(1) |
O(1) |
front() |
O(1) |
O(1) |
size() |
O(1) |
O(1) |
isEmpty() |
O(1) |
O(1) |
Like the stack, the circular array-based queue and the linked list-based queue have the same time efficiency for all operations. We would then choose the implementation based on other factors, such as memory usage or the frequency of grow() operations. The circular array-based queue must declare a fixed-size array initially, and so some of that space is wasted whenever the queue is not full. The linked list-based queue can shrink and grow but requires the overhead of a Node.next field for every element.