队列的链表方式实现

1、像堆栈一样，也可以使用链表来实现一个队列。此时需要两个变量 f r o n t和r e a r来分别跟踪队列的两端，这时有两种可能的情形：从 f r o n t开始链接到 r e a r（如a所示）或从 r e a r开始链接到f r o n t（如图 b所示）。不同的链接方向将使添加和删除操作的难易程度有所不同。图 6 - 8和6 - 9分别演示了添加元素和删除元素的过程。可以看到，两种链接方向都很适合于添加操作，而从f r o n t到r e a r的链接更便于删除操作的执行。因此，我们将采用从 f r o n t到r e a r的链接模式。可以取初值 f r o n t = r e a r = 0，并且认定当且仅当队列为空时 f r o n t = 0。

2、链表队列的实现

节点定义：Node.h

 1 #ifndef NODE_H
 2 #define NODE_H
 3 template<class T>
 4 class LinkedQueue;//声明模板类
 5 
 6 template<class T>
 7 class Node
 8 {
 9     friend class LinkedQueue<T>;//声明为友元，因为需要访问Node的私有成员
10     friend std::ostream& operator<<(std::ostream& output, const LinkedQueue<T>& q);
11 private:
12     Node<T> *next;
13     T data;
14 };
15 #endif

链表队列：

  1 #ifndef LINKEDQUEUE_H
  2 #define LINKEDQUEUE_H
  3 #include <iostream>
  4 #include <new>
  5 #include "Node.h"
  6 #include "exceptionerror.h"
  7 
  8 template<class T>
  9 class LinkedQueue
 10 {
 11 public:
 12     LinkedQueue():front(0),rear(0){}
 13     ~LinkedQueue();
 14     friend std::ostream& operator<<(std::ostream& output,const LinkedQueue<T>& q)
 15     {
 16         if (q.IsEmpty())
 17         {
 18             output << "empty queue" << std::endl;
 19         }
 20         else
 21         {
 22             Node<T>* p = q.front;
 23             while (p)
 24             {
 25                 output << p->data << " ";
 26                 p = p->next;
 27             }            
 28         }
 29 
 30         return output;
 31     }
 32     bool IsEmpty()const{ return front == 0; }
 33     bool IsFull()const;
 34     T First()const;//返回第一个元素
 35     T Last()const;//返回最后一个元素
 36     LinkedQueue<T>& Add(const T& x);//添加元素
 37     LinkedQueue<T>& Delete(T& x);//删除元素
 38     int Quantity()const;//返回元素个数
 39 private:
 40     Node<T> *front;
 41     Node<T> *rear;
 42 };
 43 
 44 template<class T>
 45 LinkedQueue<T>::~LinkedQueue()
 46 {
 47     Node<T>* next;
 48     while (front)
 49     {
 50         next = front->next;
 51         delete front;
 52         front = next;
 53     }
 54 }
 55 
 56 template<class T>
 57 bool LinkedQueue<T>::IsFull()const
 58 {
 59     Node<T>* p;
 60     try
 61     {
 62         p = new Node<T>;
 63         delete p;
 64         return false;
 65     }
 66     catch (CMemoryException* e)
 67     {
 68         return true;
 69     }
 70 }
 71 
 72 template<class T>
 73 T LinkedQueue<T>::First()const
 74 {
 75     if (IsEmpty())
 76     {
 77         throw OutofBounds();
 78     }
 79 
 80     return front->data;
 81 }
 82 
 83 template<class T>
 84 T LinkedQueue<T>::Last()const
 85 {
 86     if (IsEmpty())
 87     {
 88         throw OutofBounds();
 89     }
 90 
 91     return rear->data;
 92 }
 93 
 94 template<class T>
 95 LinkedQueue<T>& LinkedQueue<T>::Add(const T& x)
 96 {
 97     Node<T> *p = new Node<T>;
 98     p->data = x;
 99     p->next = 0;
100     if (front)
101     {
102         rear->next = p;
103     }
104     else front = p;
105 
106     rear = p;
107     return *this;
108 }
109 
110 template<class T>
111 LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
112 {
113     if (IsEmpty())
114     {
115         throw OutofBounds();
116     }
117     x = front->data;
118     Node<T>* p = front;//为了释放front空间
119     front = front->next;
120     delete p;
121 
122     return *this;
123 }
124 
125 template<class T>
126 int LinkedQueue<T>::Quantity()const
127 {
128     if (IsEmpty())
129     {
130         return 0;
131     }
132     int count = 0;
133     Node<T>* p = front;
134     while (p)
135     {
136         p=p->next;
137         count++;
138     }
139 
140     return count;
141 }
142 #endif

测试代码：

 1 #include "LinkedQueue.h"
 2 
 3 int main()
 4 {
 5     LinkedQueue<int> Q;
 6     std::cout << "Q is Empty? "<<Q.IsEmpty() << std::endl;
 7     Q.Add(1);
 8     Q.Add(2);
 9     Q.Add(3);
10     Q.Add(4);
11     Q.Add(5);
12     Q.Add(6);
13     Q.Add(7);
14     Q.Add(8);
15     std::cout << "Quantity of Q is " << Q.Quantity() << std::endl;
16     std::cout << "Q is:" << std::endl;
17     std::cout << Q << std::endl;
18     int x;
19     Q.Delete(x);
20     std::cout << "The num deleted is " << x << std::endl;
21     std::cout << "Quantity of Q is " << Q.Quantity() << std::endl;
22     std::cout << "Q is:" << std::endl;
23     std::cout << Q << std::endl;
24     system("pause");
25     return 0;
26 }

输出：