6.12. Linked Queues¶
6.12.1. Linked Queues¶
The linked queue implementation is a straightforward adaptation of the linked list. Here is the linked queue class declaration.
// Linked queue implementation
class LQueue implements Queue {
private Link front; // Pointer to front queue node
private Link rear; // Pointer to rear queue node
private int size; // Number of elements in queue
// Constructors
LQueue() { init(); }
LQueue(int size) { init(); } // Ignore size
// Initialize queue
void init() {
front = rear = new Link(null);
size = 0;
}
// Put element on rear
public boolean enqueue(Object it) {
rear.setNext(new Link(it, null));
rear = rear.next();
size++;
return true;
}
// Remove and return element from front
public Object dequeue() {
if (size == 0) return null;
Object it = front.next().element(); // Store the value
front.setNext(front.next().next()); // Advance front
if (front.next() == null) rear = front; // Last element
size--;
return it; // Return element
}
// Return front element
public Object frontValue() {
if (size == 0) return null;
return front.next().element();
}
// Return queue size
public int length() { return size; }
// Check if the queue is empty
public boolean isEmpty() { return size == 0; }
}
// Linked queue implementation
class LQueue<E> implements Queue<E> {
private Link<E> front; // Pointer to front queue node
private Link<E> rear; // Pointer to rear queue node
private int size; // Number of elements in queue
// Constructors
LQueue() { init(); }
LQueue(int size) { init(); } // Ignore size
// Initialize queue
void init() {
front = rear = new Link<E>(null);
size = 0;
}
// Put element on rear
public boolean enqueue(E it) {
rear.setNext(new Link<E>(it, null));
rear = rear.next();
size++;
return true;
}
// Remove and return element from front
public E dequeue() {
if (size == 0) { return null; }
E it = front.next().element(); // Store the value
front.setNext(front.next().next()); // Advance front
if (front.next() == null) { rear = front; } // Last element
size--;
return it; // Return element
}
// Return front element
public E frontValue() {
if (size == 0) { return null; }
return front.next().element();
}
// Return queue size
public int length() { return size; }
//Tell if the queue is empty or not
public boolean isEmpty() { return size == 0; }
}
6.12.2. Linked Dequeue¶
6.12.3. 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.