4.13. Linked Queues¶
4.13.1. Linked Queues¶
The linked queue implementation is an adaptation of the linked list. The only thing is that we have to add a pointer to the rear node in the queue, to be able to add new elements efficiently.
class LinkedQueue<E> implements Queue<E> {
private Node front; // Pointer to front queue node
private Node rear; // Pointer to rear queue node
private int queueSize; // Size of queue
LinkedQueue() {
front = null;
rear = null;
queueSize = 0;
}
class LinkedQueue(Queue):
def __init__(self):
self._front = None # Pointer to front queue node
self._rear = None # Pointer to rear queue node
self._queueSize = 0 # Size of queue
4.13.2. Enqueueing Elements¶
public void enqueue(E x) {
Node newRear = new Node(x, null);
if (queueSize == 0)
front = newRear;
else
rear.next = newRear;
rear = newRear;
queueSize++;
}
def enqueue(self, x):
newRear = LinkedQueueNode(x, None)
if self._queueSize == 0:
self._front = newRear
else:
self._rear.next = newRear
self._rear = newRear
self._queueSize += 1
4.13.3. Dequeueing Elements¶
public E dequeue() {
if (!(queueSize > 0)) throw new NoSuchElementException("dequeue from empty queue");
Node removed = front;
front = removed.next;
removed.next = null; // For garbage collection
queueSize--;
if (queueSize == 0)
rear = null;
return removed.elem;
}
def dequeue(self):
if not (self._queueSize > 0): raise IndexError("dequeue from empty queue")
removed = self._front
self._front = removed.next
removed.next = None # For garbage collection
self._queueSize -= 1
if self._queueSize == 0:
self._rear = None
return removed.elem
4.13.4. Linked Queue, Full Implementation¶
Here is the full implementation for linked queues.
class LinkedQueue<E> implements Queue<E> {
private Node front; // Pointer to front queue node
private Node rear; // Pointer to rear queue node
private int queueSize; // Size of queue
LinkedQueue() {
front = null;
rear = null;
queueSize = 0;
}
private class Node {
E elem; // Value for this node
Node next; // Pointer to next node in queue
Node(E elem, Node next) {
this.elem = elem;
this.next = next;
}
}
public void enqueue(E x) {
Node newRear = new Node(x, null);
if (queueSize == 0)
front = newRear;
else
rear.next = newRear;
rear = newRear;
queueSize++;
}
public E peek() {
if (!(queueSize > 0)) throw new NoSuchElementException("peek from empty queue");
return front.elem;
}
public E dequeue() {
if (!(queueSize > 0)) throw new NoSuchElementException("dequeue from empty queue");
Node removed = front;
front = removed.next;
removed.next = null; // For garbage collection
queueSize--;
if (queueSize == 0)
rear = null;
return removed.elem;
}
public boolean isEmpty() {
return queueSize == 0;
}
public int size() {
return queueSize;
}
public Iterator<E> iterator() {
return new LinkedQueueIterator();
}
private class LinkedQueueIterator implements Iterator<E> {
private Node current;
LinkedQueueIterator() {
current = front;
}
public boolean hasNext() {
return current != null;
}
public E next() {
E x = current.elem;
current = current.next;
return x;
}
}
}
class LinkedQueue(Queue):
def __init__(self):
self._front = None # Pointer to front queue node
self._rear = None # Pointer to rear queue node
self._queueSize = 0 # Size of queue
def enqueue(self, x):
newRear = LinkedQueueNode(x, None)
if self._queueSize == 0:
self._front = newRear
else:
self._rear.next = newRear
self._rear = newRear
self._queueSize += 1
def peek(self):
if not (self._queueSize > 0): raise IndexError("peek from empty queue")
return self._front.elem
def dequeue(self):
if not (self._queueSize > 0): raise IndexError("dequeue from empty queue")
removed = self._front
self._front = removed.next
removed.next = None # For garbage collection
self._queueSize -= 1
if self._queueSize == 0:
self._rear = None
return removed.elem
def isEmpty(self):
return self._queueSize == 0
def size(self):
return self._queueSize
def __iter__(self):
current = self._front
while current is not None:
yield current.elem
current = current.next
# Python does not have internal classes, so we have to make the queue node standalone.
class LinkedQueueNode:
def __init__(self, elem, next):
self.elem = elem # Value for this node
self.next = next # Pointer to next node in queue
4.13.5. Comparison of Array-Based and Linked Queues¶
All member functions for both the array-based and linked queue implementations require constant time. The space comparison issues are the same as for the equivalent stack implementations.
Unlike the array-based stack implementation, there is no convenient way to store two queues in the same array, unless items are always transferred directly from one queue to the other.
