简单数据结构的实现之链队列

http://blog.csdn.net/qtyl1988/article/details/6790506

2011

[cpp] view plain copy

1. #include <iostream>  
2.   
3. using namespace std;  
4.   
5. #ifndef LINKQUEUE_H_INCLUDED  
6. #define LINKQUEUE_H_INCLUDED  
7.   
8. template <class ElemType>  
9. struct QNode  
10. {  
11.     ElemType data;  
12.     QNode* next;  
13. };  
14. template <class ElemType>  
15. class LinkQueue  
16. {  
17.     private:  
18.     QNode<ElemType>* front;  
19.     QNode<ElemType>* rear;  
20.     public:  
21.     LinkQueue();  
22.     ~LinkQueue();  
23.     void ClearQueue();  
24.     bool QueueEmpty(){return front==rear;}  
25.     int QueueLength();  
26.     QNode<ElemType>* Front(){return front;}  
27.     QNode<ElemType>* Rear(){return rear;}  
28.     bool GetHead(ElemType& e);  
29.     bool EnQueue(ElemType e);  
30.     bool DeQueue(ElemType& e);  
31. };  
32. template <class ElemType>  
33. LinkQueue<ElemType>::LinkQueue()  
34. {  
35.     front=rear=new QNode<ElemType>;  
36.     front->next=NULL;  
37. }  
38. template <class ElemType>  
39. LinkQueue<ElemType>::~LinkQueue()  
40. {  
41.     while(front)  
42.     {  
43.         rear=front->next;  
44.         delete front;  
45.         front=rear;  
46.     }  
47. }  
48. template <class ElemType>  
49. void LinkQueue<ElemType>::ClearQueue()  
50. {  
51.     QNode<ElemType>* p=front->next;  
52.     while(p)  
53.     {  
54.         rear=p->next;  
55.         delete p;  
56.         p=rear;  
57.     }  
58.     rear=front;  
59.     front->next=NULL;  
60. }  
61. template <class ElemType>  
62. int LinkQueue<ElemType>::QueueLength()  
63. {  
64.     int i=0;  
65.     QNode<ElemType>* p=front->next;  
66.     while(p)  
67.     {  
68.         i++;  
69.         p=p->next;  
70.     }  
71.     return i;  
72. }  
73. template <class ElemType>  
74. bool LinkQueue<ElemType>::GetHead(ElemType& e)  
75. {  
76.     if(front==rear)  
77.     {  
78.         return false;  
79.     }  
80.     else  
81.     {  
82.         e=front->next->data;  
83.         return true;  
84.     }  
85. }  
86. template <class ElemType>  
87. bool LinkQueue<ElemType>::EnQueue(ElemType e)  
88. {  
89.     QNode<ElemType>* p=new QNode<ElemType>;  
90.     if(!p)  
91.     {  
92.         return false;  
93.     }  
94.     else  
95.     {  
96.         p->data=e;  
97.         rear->next=p;  
98.         rear=p;  
99.         p->next=NULL;  
100.         return true;  
101.     }  
102. }  
103. template <class ElemType>  
104. bool LinkQueue<ElemType>::DeQueue(ElemType& e)  
105. {  
106.     if(front==rear)  
107.     {  
108.         return false;  
109.     }  
110.     else  
111.     {  
112.         QNode<ElemType>* p=front->next;  
113.         e=p->data;  
114.         front->next=p->next;  
115.         if(rear==p)  
116.         {  
117.             rear=front;  
118.         }  
119.         delete p;  
120.         return true;  
121.     }  
122. }  
123. #endif // LINKQUEUE_H_INCLUDED