用C實作Queue
以下是我用C++實作Queue的code，因為用讀書的常常讀到忘記，所以乾脆做出來加深印象，分別是用Array和linkedlist做的，Array的部分前者是只能用到n-1格的，後者是能用到n格的，最下方附上程式結果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<iostream>
#include<stdio.h>
using namespace std;
//===================================只能用array n-1格
int q[5];
int rear=0;
int front=0;
void enqueue1(int* q,int item){
int prerear=rear;
rear=(rear+1)%5;
if(rear==front){
rear=prerear;
cout<<"queue is full"<<endl;
}else{
q[rear] = item;
}
}
void dequeue1(int* q){
if(front==rear){
cout<<"queue is empty"<<endl;
}else{
front=(front+1)%5;
int item=q[front];
cout<<"dequeued item is "<<item<<endl;
}
}
//===================================可以用n格
int tag=0;
void enqueue2(int* q,int item){
if(rear==front && tag==1){
cout<<"queue is full"<<endl;
}else{
rear=(rear+1)%5;
q[rear]=item;
if(rear==front) tag=1;
}
}
void dequeue2(int* q){
if(front==rear && tag==0){
cout<<"queue is empty"<<endl;
}else{
front=(front+1)%5;
int item=q[front];
if(front==rear) tag=0;
cout<<"dequeued item is "<<item<<endl;
}
}
void printqueue(int* q){
cout<<"front is "<<front<<" rear is "<<rear<<endl;
cout<< "queue content is ";
for(int i=0;i<5;i++){
cout << q[front] << " ";
front=(front+1)%5;
}
cout<<endl;
}
//===================================linkedlist array
struct Node{
int value;
struct Node* next;
Node(int data){
this->value=data;
this->next=NULL;
}
};
Node* rearlist=NULL;
Node* frontlist=NULL;
Node* qlist=NULL;
void enqueuelist(Node* qlist,int item){
Node* t=new Node(item);
t->value=item;
t->next=NULL;
if(frontlist==NULL){
frontlist=t;
}else{
rearlist->next=t;
}
rearlist=t;
}
void dequeuelist(Node* qlist){
if(frontlist==NULL){
cout<<"queue is empty"<<endl;
}else{
Node* t=frontlist;
int item=frontlist->value;
frontlist=frontlist->next;
free(t);
cout<<"dequeued item is "<<item<<endl;
}
}
void printlist(Node* qlist){
cout<<"List content is : ";
Node* s=frontlist;
while(s!=NULL){
cout<<s->value<<" ";
s=s->next;
}
cout<<endl;
}
int main(){
cout<<"========================"<<endl;
cout<<"use n-1 size of array to implemnet queue: "<<endl;
enqueue1(q,1);
enqueue1(q,2);
enqueue1(q,3);
enqueue1(q,4);
enqueue1(q,5);
printqueue(q);
dequeue1(q);
dequeue1(q);
dequeue1(q);
printqueue(q);
cout<<"========================"<<endl;
cout<<"use n size of array to implemnet queue: "<<endl;
front=0;
rear=0;
enqueue2(q,1);
enqueue2(q,2);
enqueue2(q,3);
enqueue2(q,4);
enqueue2(q,5);
printqueue(q);
dequeue2(q);
dequeue2(q);
dequeue2(q);
printqueue(q);
cout<<"========================"<<endl;
cout<<"use linkedlist to implemnet queue: "<<endl;
enqueuelist(qlist,1);
enqueuelist(qlist,2);
enqueuelist(qlist,3);
enqueuelist(qlist,4);
dequeuelist(qlist);
dequeuelist(qlist);
printlist(qlist);
return 0;
}
result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
========================
use n-1 size of array to implemnet queue:
queue is full
front is 0 rear is 4
queue content is 0 1 2 3 4
dequeued item is 1
dequeued item is 2
dequeued item is 3
front is 3 rear is 4
queue content is 3 4 0 1 2
========================
use n size of array to implemnet queue:
front is 0 rear is 0
queue content is 5 1 2 3 4
dequeued item is 1
dequeued item is 2
dequeued item is 3
front is 3 rear is 0
queue content is 3 4 5 1 2
========================
use linkedlist to implemnet queue:
dequeued item is 1
dequeued item is 2
List content is : 3 4
留言