链式存储的队列的实现

2013-08-18 20:07:25

链式存储的队列的实现，包括队列的初始化、销毁、入队、出队、测长、获取队首元素等基本操作。

注意几点：

队列结构,包含一个头指针、一个尾指针，初始化为空队列，空队列的队首指针与队尾指针相同；
链表包含头结点，否则在队列为空以及队列只有一个元素时都是队尾至真与队首指针相等，无法区分
有动态分配空间，就要释放，本实现中用DestoryQueue释放动态内存；
带有头结点，队列的第一个元素在头指针指向的结点中，对非空队列，队列中第一个元素为q.front->next->data; 而非q.front->data;
在出队以及获取队首元素时，要考虑队列空否，本实现中用assert( !IsQueueEmpty(q) ); 检查。

代码（测试暂未发现错误，欢迎交流指正！）：

  1 #include <iostream>
  2 #include <cassert>
  3 using namespace std;
  4 
  5 typedef int DataType; 
  6 
  7 typedef struct node
  8 {
  9     DataType data;
 10     struct node *next;
 11 }LNode,*PLNode;
 12 
 13 //队列结构,包含一个头指针、一个尾指针
 14 typedef struct queue
 15 {
 16     PLNode front;
 17     PLNode rear;
 18 }Queue;
 19 
 20 //初始化队列,链表包含头结点，
 21 //否则在队列为空以及队列只有一个元素时都是队尾至真与队首指针相等，无法区分
 22 void InitQueue(Queue &q)
 23 {
 24     q.front = new LNode;
 25     q.front->next = NULL;
 26     q.rear = q.front;
 27 }
 28 
 29 //队列销毁，即两个栈的销毁
 30 void DestoryQueue(Queue &q)
 31 {
 32     PLNode pCur = q.front;
 33     PLNode pPre = NULL;
 34 
 35     while (pCur != NULL)
 36     {
 37         pPre = pCur;
 38         pCur = pCur->next;
 39         delete pPre;
 40     }
 41 }
 42 
 43 //判断队列空否
 44 bool IsQueueEmpty(Queue &q)
 45 {
 46     return ( (q.front == q.rear) ? true : false);
 47 }
 48 
 49 //出队，从队首删除
 50 DataType DeQueue(Queue &q)
 51 {
 52     assert( !IsQueueEmpty(q) );
 53 
 54     DataType frontData = q.front->next->data;
 55     PLNode pNodeToDelete = q.front->next;
 56 
 57     if (q.front->next == q.rear)  //队列中只有一个元素时，删除的是队尾结点，需同时更新队尾指针
 58     {
 59         q.rear = q.front;   
 60     }
 61 
 62     //q.front = q.front->next->next;  //错误的更新，带有头结点，队列的第一个元素在头指针指向的结点中
 63     q.front->next = q.front->next->next;  //更新队首
 64     delete pNodeToDelete;            //删除旧的队首结点
 65 
 66     return frontData;
 67 }
 68 
 69 //入队，从队尾插入
 70 void EnQueue(Queue &q,DataType data)
 71 {
 72     PLNode pNew = new LNode;
 73     pNew->data = data;
 74     pNew->next = NULL;
 75     
 76     q.rear->next = pNew;   
 77     q.rear = pNew;            //更新队尾
 78 }
 79 
 80 //获取队首元素
 81 DataType GetHeadOfQueue(Queue &q)
 82 {
 83     assert( !IsQueueEmpty(q) );
 84     //return q.front->data;    //带有头结点，队列的第一个元素在头指针指向的结点中
 85     return q.front->next->data;  
 86 }
 87 
 88 //队列测长
 89 size_t GetLengthOfQueue(Queue &q)
 90 {
 91     PLNode pCur = q.front->next;
 92     size_t lengthOfQueue = 0;
 93 
 94     while (pCur != NULL)
 95     {
 96         ++lengthOfQueue;
 97         pCur = pCur->next;
 98     }
 99 
100     return lengthOfQueue;
101 }
102 
103 //从队首到队尾显示队列元素
104 void DisplayQueue(Queue &q)
105 {
106     PLNode pCur = q.front->next;
107     
108     while (pCur != NULL)
109     {
110         cout<<pCur->data<<"	";
111         pCur = pCur->next;
112     }
113 
114     cout<<endl;
115 }
116 
117 //队列测试
118 void TestQueue()
119 {
120     Queue q;
121     InitQueue(q);  //初始化队列
122     size_t command = 0;
123 
124     const size_t PUSH = 0;
125     const size_t POP = 1;
126     const size_t GETLENGTH = 2;
127     const size_t GETHEAD = 3;
128     const size_t ISEMPTY = 4;
129 
130     DataType data;
131 
132     cout<<"Please enter the command ,end with ctrl+z : "<<endl;
133     while (cin>>command)
134     {
135         switch(command)
136         {
137         case(PUSH):
138             {
139                 cout<<"Please enter z data to push : "<<endl;
140                 cin>>data;
141                 cout<<"enqueue "<<data<<endl;
142 
143                 cout<<"the queue before enqueue : "<<endl;
144                 DisplayQueue(q);
145 
146                 EnQueue(q,data);
147 
148                 cout<<"the queue after enqueue : "<<endl;
149                 DisplayQueue(q);
150 
151                 break;
152             }
153 
154         case(POP):
155             {
156                 cout<<"the queue before dequeue : "<<endl;
157                 DisplayQueue(q);
158 
159                 DeQueue(q);
160 
161                 cout<<"the queue after dequeue : "<<endl;
162                 DisplayQueue(q);
163 
164                 break;
165             }
166 
167         case(GETLENGTH):
168             {
169                 cout<<"the length of queue is : "<<GetLengthOfQueue(q)<<endl;
170 
171                 break;
172             }
173 
174         case(GETHEAD):
175             {
176                 cout<<"the top element of stack is : "<<GetHeadOfQueue(q)<<endl;
177 
178                 break;
179             }
180         case(ISEMPTY):
181             {
182                 cout<<"the queue is empty or not: "<<IsQueueEmpty(q)<<endl;
183 
184                 break;
185             }
186         default:
187             break;
188         }
189         cout<<"Please enter the command ,end with ctrl+z : "<<endl;
190     }
191 
192     DestoryQueue(q); //销毁队列
193 }
194 
195 int main()
196 {
197     TestQueue();
198     return 0;
199 }

测试结果：

 1 Please enter the command ,end with ctrl+z :
 2 2
 3 the length of queue is : 0
 4 Please enter the command ,end with ctrl+z :
 5 0
 6 Please enter z data to push :
 7 1
 8 enqueue 1
 9 the queue before enqueue :
10 
11 the queue after enqueue :
12 1
13 Please enter the command ,end with ctrl+z :
14 0
15 Please enter z data to push :
16 2
17 enqueue 2
18 the queue before enqueue :
19 1
20 the queue after enqueue :
21 1       2
22 Please enter the command ,end with ctrl+z :
23 0
24 Please enter z data to push :
25 3
26 enqueue 3
27 the queue before enqueue :
28 1       2
29 the queue after enqueue :
30 1       2       3
31 Please enter the command ,end with ctrl+z :
32 2
33 the length of queue is : 3
34 Please enter the command ,end with ctrl+z :
35 3
36 the top element of stack is : 1
37 Please enter the command ,end with ctrl+z :
38 1
39 the queue before dequeue :
40 1       2       3
41 the queue after dequeue :
42 2       3
43 Please enter the command ,end with ctrl+z :
44 3
45 the top element of stack is : 2
46 Please enter the command ,end with ctrl+z :
47 1
48 the queue before dequeue :
49 2       3
50 the queue after dequeue :
51 3
52 Please enter the command ,end with ctrl+z :
53 1
54 the queue before dequeue :
55 3
56 the queue after dequeue :
57 
58 Please enter the command ,end with ctrl+z :
59 1
60 the queue before dequeue :
61 
62 Assertion failed: !IsQueueEmpty(q), file e:visual studio 2010_projectslink_que
63 ue_2013_08_18link_queue_2013_08_18link_queue.cpp, line 53
64 请按任意键继续. . .