lqueue.h

来自「经典c++程序的实现」· C头文件 代码 · 共 43 行

class Queue {      // Linked queue class
private:
  link *front;     // Pointer to front queue node
  link *rear;      // Pointer to rear queue node

public:
  Queue(const int sz =LIST_SIZE) // Constructor: initialize
    { front = rear = NULL; }
  ~Queue() { clear(); }          // Destructor: return link ELEMs
  void clear();                  // Remove all ELEM's from queue
  void enqueue(const ELEM&);     // Enqueue ELEM at rear
  ELEM dequeue();                // Dequeue ELEM from front
  ELEM firstValue() const        // Get value of front ELEM
    { assert(!isEmpty());  return front->element; }
  bool isEmpty() const           // Return TRUE if queue is empty
    { return front == NULL; }
};

void Queue::clear() {            // Remove all ELEM's from the queue
  while(front != NULL)           // Return link nodes to freelist
    { rear = front;  front = front->next;  delete rear; }
  rear = NULL;
}

// Enqueue ELEM at rear of queue
void Queue::enqueue(const ELEM& item) {
  if (rear != NULL) {   // Queue not empty: add to end
       rear->next = new link(item, NULL);
       rear = rear->next;
     }
     else front = rear = new link(item, NULL); // Empty queue
   }
   
   ELEM Queue::dequeue() {           // Dequeue ELEM from front
     assert(!isEmpty());             // Must be something to dequeue
     ELEM temp = front->element;     // Store dequeued value
     link* ltemp = front;            // Hold onto dequeued link node
     front = front->next;            // Advance front
     delete ltemp;                   // Return link to free store
     if (front == NULL) rear = NULL; // Dequeued last element
     return temp;                    // Return element value
   }