Queue實作
在日常生活中，我們經常需要排隊做事，如:看電影前要排隊買票。
排隊最基本的規矩就是後到的人要排在隊伍的最後面，而先到的人可以接受服務。
新增在尾部
Queue是新增節點在尾部。
以下是新增節點的過程。
刪除在頭部
Queue是刪除節點在頭部。
以下是刪除節點的過程。
結構定義
Queue會定義頭節點與尾節點。
1
2
3
4
5
6
7
8
9
10
typedef int ElemType;
//定義節點
struct Node {
ElemType data;
Node *next;
};
struct queue {
//定義頭節點與尾節點
Node *head,*tail;
};
初始化頭節點與尾節點
一開始頭節點與尾節點都指向頭節點
1
2
3
4
5
6
7
8
9
10
11
12
/**
初始化Queue
*/
bool initQueue(queue& que) {
//頭節點
que.head = new (std::nothrow)Node;
//頭節點記憶體分配失敗
if(que.head == nullptr) return false;
que.head->next = nullptr;//queue的下一個節點為null
que.tail = que.head;//一開始頭節點與尾節點指向同一個記憶體位址
return true;
}
新增
完全沒任何節點
在沒有任何節點的狀況下，新節點新增在tail尾節點後面。
步驟如下
- 建立新節點
- 新節點的next指向nullptr
- 新節點新增在tail尾節點後面
- tail尾節點指向新節點
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool inQueue(queue& que, const ElemType& ee) {
if(que.head == nullptr) {
cout << "鏈結串列不存在" << endl;
return false;
}
//建立新節點
Node* temp = new (std::nothrow)Node;
if(temp == nullptr) return false;
//新節點設定傳進來的資料
temp->data = ee;
temp->next = nullptr;
//將新節點插入到tail之後
que.tail->next = temp;
//把tail指向temp
que.tail = temp;
return true;
}
有節點
尾節點指向鏈結串列中最後一個節點(不是nullptr)。
在有節點的狀況下，新節點新增在tail尾節點後面。
程式步驟跟沒任何節點的步驟一模一樣。
刪除節點
刪除的方式跟鏈結串列removeFirst()一樣，從鏈結串列第一個節點刪除。
如果刪的節點是尾節點，刪除完節點後，要把尾節點指向頭節點，回到初始的狀況下。
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
bool deQueue(queue& que, ElemType& e) {
if(que.head == nullptr) {
cout << "鏈結串列不存在" << endl;
return false;
}
//只有頭節點，沒有後面的資料
if(que.head->next == nullptr) {
cout << "沒有任何節點" << endl;
return false;
}
//鏈結串列中第一個節點，不包含頭節點
Node* first = que.head->next;
//將第一個節點的值存在e，作為返回
e = first->data;
//將第一個節點(不包含頭節點)指向first的下個節點
que.head->next = first->next;
//如果刪的節點是tail節點
if(first == que.tail)
//將tail指向head
que.tail = que.head;
//將第一個節點刪除
delete first;
return true;
}
完整程式碼
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
using namespace std;
typedef int ElemType;
//定義節點
struct Node {
ElemType data;
Node *next;
};
struct queue {
Node *head,*tail;
};
/**
初始化Queue
*/
bool initQueue(queue& que) {
//頭節點
que.head = new (std::nothrow)Node;
//頭節點記憶體分配失敗
if(que.head == nullptr) return false;
que.head->next = nullptr;//queue的下一個節點為null
que.tail = que.head;//一開始頭節點與尾節點指向同一個記憶體位址
return true;
}
/**
摧毀Queue
參數為頭節點
*/
void destroyQueue(queue& que){
//暫存節點
Node* temp;
while(que.head != nullptr) {
//先暫存下一個節點
temp = que.head->next;
//刪掉目前頭節點
delete que.head;
//頭節點換成下一個節點
que.head = temp;
}
}
bool inQueue(queue& que, const ElemType& ee) {
if(que.head == nullptr) {
cout << "鏈結串列不存在" << endl;
return false;
}
//建立新節點
Node* temp = new (std::nothrow)Node;
if(temp == nullptr) return false;
//新節點設定傳進來的資料
temp->data = ee;
temp->next = nullptr;
//將新節點插入到tail之後
que.tail->next = temp;
//把tail指向temp
que.tail = temp;
return true;
}
bool deQueue(queue& que, ElemType& e) {
if(que.head == nullptr) {
cout << "鏈結串列不存在" << endl;
return false;
}
//只有頭節點，沒有後面的資料
if(que.head->next == nullptr) {
cout << "沒有任何節點" << endl;
return false;
}
//鏈結串列中第一個節點，不包含頭節點
Node* first = que.head->next;
//將第一個節點的值存在e，作為返回
e = first->data;
//將第一個節點(不包含頭節點)指向first的下個節點
que.head->next = first->next;
//如果刪的節點是tail節點
if(first == que.tail)
//將tail指向head
que.tail = que.head;
//將第一個節點刪除
delete first;
return true;
}
void printQueue(queue& que) {
if(que.head == nullptr) {
cout << "鏈結串列不存在" << endl;
return;
}
//從head的下一個節點開始
//head不存在值
Node *p = que.head->next;
while(p != nullptr) {
cout << p->data << ",";
//節點p換成下一個節點
p = p->next;
}
cout << endl;
}
size_t size(queue& que) {
if(que.head == nullptr) {
cout << "鏈結串列不存在" << endl;
return 0;
}
//不包含頭節點
Node* p = que.head->next;
size_t size = 0;
//繞行到null
while(p != nullptr) {
p = p->next;
size++;
}
return size;
//遞迴方式
//if(head == nullptr) return 0;
//return size(head->next) + 1;
}
/**
清空鏈表，除了頭節點
*/
void clear(queue& que) {
if(que.head == nullptr) {
cout << "鏈結串列不存在" << endl;
return;
}
//移到頭節點的下一個節點(清空不包含頭節點)
Node* tmp = que.head->next,*tmpnext;
//繞行所有節點
while(tmp != nullptr) {
//把節點的下一個節點暫存
tmpnext = tmp->next;
//刪除目前節點
delete tmp;
//將下一個節點作為目前節點
tmp = tmpnext;
}
//頭節點的下一個設null
que.head->next = nullptr;
//尾節點與頭節點指向相同
que.tail = que.head;
}
int main() {
//建立queue
queue que;
//清空
memset(&que, 0, sizeof(que));
//初始化
initQueue(que);
inQueue(que, 1);
inQueue(que, 2);
inQueue(que, 3);
inQueue(que, 4);
inQueue(que, 5);
cout << "大小:" << size(que) << endl;
cout << "queue的內容:" << endl;
printQueue(que);
ElemType e;
while(deQueue(que, e))
cout << e << endl;
inQueue(que, 6);
inQueue(que, 7);
inQueue(que, 8);
inQueue(que, 9);
inQueue(que, 10);
cout << "大小:" << size(que) << endl;
cout << "queue的內容:" << endl;
printQueue(que);
destroyQueue(que);
return 0;
}