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 template4 class LinkedQueue;//声明模板类 5 6 template 7 class Node 8 { 9 friend class LinkedQueue ;//声明为友元，因为需要访问Node的私有成员10 friend std::ostream& operator<<(std::ostream& output, const LinkedQueue & q);11 private:12 Node *next;13 T data;14 };15 #endif
链表队列：
1 #ifndef LINKEDQUEUE_H 2 #define LINKEDQUEUE_H 3 #include4 #include 5 #include "Node.h" 6 #include "exceptionerror.h" 7 8 template 9 class LinkedQueue 10 { 11 public: 12 LinkedQueue():front(0),rear(0){} 13 ~LinkedQueue(); 14 friend std::ostream& operator<<(std::ostream& output,const LinkedQueue & q) 15 { 16 if (q.IsEmpty()) 17 { 18 output << "empty queue" << std::endl; 19 } 20 else 21 { 22 Node * 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 & Add(const T& x);//添加元素 37 LinkedQueue & Delete(T& x);//删除元素 38 int Quantity()const;//返回元素个数 39 private: 40 Node *front; 41 Node *rear; 42 }; 43 44 template 45 LinkedQueue ::~LinkedQueue() 46 { 47 Node * next; 48 while (front) 49 { 50 next = front->next; 51 delete front; 52 front = next; 53 } 54 } 55 56 template 57 bool LinkedQueue ::IsFull()const 58 { 59 Node * p; 60 try 61 { 62 p = new Node ; 63 delete p; 64 return false; 65 } 66 catch (CMemoryException* e) 67 { 68 return true; 69 } 70 } 71 72 template 73 T LinkedQueue ::First()const 74 { 75 if (IsEmpty()) 76 { 77 throw OutofBounds(); 78 } 79 80 return front->data; 81 } 82 83 template 84 T LinkedQueue ::Last()const 85 { 86 if (IsEmpty()) 87 { 88 throw OutofBounds(); 89 } 90 91 return rear->data; 92 } 93 94 template 95 LinkedQueue & LinkedQueue ::Add(const T& x) 96 { 97 Node *p = new Node ; 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 111 LinkedQueue & LinkedQueue ::Delete(T& x)112 {113 if (IsEmpty())114 {115 throw OutofBounds();116 }117 x = front->data;118 Node * p = front;//为了释放front空间119 front = front->next;120 delete p;121 122 return *this;123 }124 125 template 126 int LinkedQueue ::Quantity()const127 {128 if (IsEmpty())129 {130 return 0;131 }132 int count = 0;133 Node * 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 Q; 6 std::cout << "Q is Empty? "< << 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 } 输出：
