6.13. 链式队列¶

6.13.1. 链式队列¶

链式队列的实现是对链表的直接改造。下面是链式队列的类声明。

Java (泛型)
Java

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

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