一點 · 隊列

隊列

隊列queue也是一種線性表，但它被限制為隻能在隊尾插入，稱為入隊操作（enqueue），從隊首删除，稱為出隊操作（dequeue），是以也被稱為FIFO線性表，即先進先出。

隊列的ADT

template <typename E> class Queue {
private:
  void operator =(const Queue&) {}     // Protect assignment
  Queue(const Queue&) {}         // Protect copy constructor

public:
  Queue() {}          // Default
  virtual ~Queue() {} // Base destructor

  // Reinitialize the queue.  The user is responsible for
  // reclaiming the storage used by the queue elements.
  virtual void clear() = 0;

  // Place an element at the rear of the queue.
  // it: The element being enqueued.
  virtual void enqueue(const E&) = 0;

  // Remove and return element at the front of the queue.
  // Return: The element at the front of the queue.
  virtual E dequeue() = 0;

  // Return: A copy of the front element.
  virtual const E& frontValue() const = 0;

  // Return: The number of elements in the queue.
  virtual int length() const = 0;
};
           

如果使用普通的順序表來實作隊列，就會導緻enqueue和dequeue操作中，一個時間代價為Θ（n），另一個為Θ（1），分别對應隊首隊尾正放與倒放的情況。

是以采用一種循環順序表的方式來實作，即順序表的最後一個結點的next指針指向head，且每次enqueue操作使得front後移，dequeue操作使得rear也後移。

這帶來一個小問題，就是對于一個有着n長度的順序表來說，它應該能表示n+1種狀态，但是由于front和rear各指向一個位置，導緻實際上隻能表示n種狀态，這就是的第一種狀态，空狀态，和第n+1種狀态，滿狀态的區分上産生了困難，一種解決方法是單獨設定一個布爾成員變量，用來記錄是否為空，或者将順序表長度設為n+1，隻在其中儲存最多n個元素，便可表示，n+1種狀态。

鍊式隊列 一種簡單修改後的連結清單，隻是固定front和rear指針指向連結清單的的頭和尾，但是隻能在front處删除，在rear處添加，而初始化時，将front和rear均指向頭結點。 鍊式隊列的實作：

template <typename E> class LQueue: public Queue<E> {
private:
  Link<E>* front;       // Pointer to front queue node
  Link<E>* rear;        // Pointer to rear queue node
  int size;                // Number of elements in queue

public:
  LQueue(int sz =defaultSize) // Constructor 
    { front = rear = new Link<E>(); size = 0; }

  ~LQueue() { clear(); delete front; }      // Destructor

  void clear() {           // Clear queue
    while(front->next != NULL) { // Delete each link node
      rear = front;
      delete rear;
    }
    rear = front;
    size = 0;
  }

  void enqueue(const E& it) { // Put element on rear
    rear->next = new Link<E>(it, NULL);
    rear = rear->next;
    size++;
  }

  E dequeue() {              // Remove element from front
    Assert(size != 0, "Queue is empty");
    E it = front->next->element;  // Store dequeued value
    Link<E>* ltemp = front->next; // Hold dequeued link
    front->next = ltemp->next;       // Advance front
    if (rear == ltemp) rear = front; // Dequeue last element
    delete ltemp;                    // Delete link
    size --;
    return it;                       // Return element value
  }

  const E& frontValue() const { // Get front element
    Assert(size != 0, "Queue is empty");
    return front->next->element;
  }

  virtual int length() const { return size; }
};