首页 > 代码库 > 队列的链表方式实现
队列的链表方式实现
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 =http://www.mamicode.com/ 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()const127 {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 }
输出：
队列的链表方式实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。