-
Notifications
You must be signed in to change notification settings - Fork 0
/
queue.cpp
156 lines (136 loc) · 3.55 KB
/
queue.cpp
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
#include "queue.h"
#include<stdlib.h>
//初始化队列
Queue *InitQueue()
{
Queue *queue = NULL;
queue = new Queue;
queue->head = queue->tail = NULL;
return queue;
}
//向队列末尾插入一个元素
void InsertQueue(Queue *queue, QString element)
{
Node *new_node = NULL;
if(queue != NULL)//参数检查
{
//得到一个新节点
new_node = new Node;
new_node->dat = new QString(element);
new_node->next = NULL;
if(queue->tail == NULL)//如果队尾为空,表示队列为空
{
queue->head = new_node;
queue->tail = new_node;
}
else//非空队列,则将新节点添加到队列尾部
{
queue->tail->next = new_node;
queue->tail = new_node;
}
}
}
//从队首删除一个元素
void DelQueue(Queue *queue)
{
Node *p = NULL;
if(queue != NULL)//参数检查
{
if(GetQueueLength(queue) == 1)//只有一个元素
{
delete queue->head->dat;//释放QString *指向的空间
delete queue->head;//释放Node *指向的空间
queue->head = queue->tail = NULL;
}
else if(GetQueueLength(queue) > 1)//一个以上的元素
{
delete queue->head->dat;//释放QString *指向的空间
p = queue->head;//暂存节点地址
queue->head = queue->head->next;
delete p;
}
}
}
//获取队首元素
QString* GetQueueHead(Queue *queue)
{
if(queue)
{
if(queue->head)
return queue->head->dat;
}
return NULL;
}
//获取队列前i个元素
QStringList GetQueue_ahead_element(Queue *queue, int num)
{
Node *p = NULL;
p = queue->head;
QStringList arguments;
if(queue && GetQueueLength(queue) >= num)
{
for(int i = 0; i < num; i++)
{
arguments << *(p->dat);
p = p->next;
}
}
return arguments;
}
//清除队列中所有元素
void ClearQueue(Queue *queue)
{
if(queue)//参数检查
{
Node *p = NULL;
p = queue->head;
int len = GetQueueLength(queue);
//队列长度为0无需清理
if(len == 1)//只有一个元素
{
delete queue->head->dat;//释放QString *指向的空间
delete queue->head;//释放Node *指向的空间
queue->head = queue->tail = NULL;
}
else if(len > 1)//一个以上的元素
{
while(queue->head != queue->tail)
{
delete queue->head->dat;//释放QString *指向的空间
p = queue->head;//暂存节点地址
queue->head = queue->head->next;
delete p;
}
//还剩余一个节点
delete queue->head->dat;
delete queue->head;
queue->head = queue->tail = NULL;
}
}
}
//获取队列长度
int GetQueueLength(Queue *queue)
{
if(queue == NULL)
return -1;
int len = 0;
Node *p = queue->head;
if(queue->tail == NULL)//队列为空
{
return len;
}
else if(queue->head == queue->tail && queue->head != NULL)//队列只有一个元素
{
len = 1;
}
else//队列不止一个元素
{
len++;
while(p != queue->tail)
{
p = p->next;
len++;
}
}
return len;
}