Close
Register
Close Window

Data Structures & Algorithms

Chapter 6 Hash Table and Queue

Show Source |    | About   «  6.11. Queues   ::   Contents   ::   6.13. Linear Structure Summary Exercises  »

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; }
}

Settings

Proficient Saving... Error Saving
Server Error
Resubmit


Settings

Proficient Saving... Error Saving
Server Error
Resubmit

6.12.2. Linked Dequeue

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

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.

6.12.3.1. Stack and Queue Summary Questions

   «  6.11. Queues   ::   Contents   ::   6.13. Linear Structure Summary Exercises  »

Close Window