前言
队列(queue)是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
入队（push）：线性表中，入队数据存储在last+1（last为未入队时栈顶元素的下标）的位置；链式表中，表中的最后一个结点指向待入队结点，待入队结点指向空(NULL)；
出队（pop）：线性表中，数据依次左移一个单位；链式栈中，head指向它后继节点的后继节点（head->next = head->next->next）；
取队列顶（front）：线性表中，返回下标为0的一个数据；链式表中，返回 head 的后继节点的数据。
队列的操作接口
| 操作接口 |
功能 |
| void push(T p) |
将元素p插入队尾（入队） |
| void pop() |
删除队首元素 |
| bool front(T &p) |
成功得到队列顶元素返回true，并得到队列顶数据p |
| bool isEmpty() |
判断队列是否为空 |
| int size() |
得到队列的大小 |
线性队列
使用线性结构数组来实现栈的操作。
线性队列的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| template<class T>
class SeqQueue {
public:
T *data;
int maxSize{};
int last{};
public:
SeqQueue();
SeqQueue(SeqQueue<T> &list);
~SeqQueue();
void reSize();
void push(T p);
void pop();
bool front(T &p);
bool isEmpty();
int size();
void print();
void clear();
void delete_link();
};
|
基本函数
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
|
template<class T>
SeqQueue<T>::SeqQueue() {
maxSize = 50;
last = 0;
data = new T[maxSize];
if (data == NULL)
{
cerr << "存储分配错误！" << endl;
exit(1);
}
}
template<class T>
SeqQueue<T>::SeqQueue(SeqQueue<T> &list) {
maxSize = list.maxSize;
last = list.last;
data = new T[maxSize];
if (data == NULL)
{
cerr << "存储分配错误！" << endl;
exit(1);
}
for (int i = 0; i < maxSize; i++)
data[i] = list.data[i];
}
template<class T>
SeqQueue<T>::~SeqQueue() {
delete_link();
}
template<class T>
bool SeqQueue<T>::isEmpty() {
return last == 0;
}
template<class T>
void SeqQueue<T>::clear() {
delete data;
maxSize = 50;
last = 0;
data = new T[maxSize];
}
template<class T>
void SeqQueue<T>::delete_link() {
delete data;
}
|
增加空间大小
线性表的空间是连续的，入队时若队列的空间不够，则需要增加空间的大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
template<class T>
void SeqQueue<T>::reSize() {
maxSize += 10;
T *temp = new T[maxSize];
if (data == NULL)
{
cerr << "存储分配错误！" << endl;
exit(1);
}
for (int i = 0; i < maxSize; i++)
temp[i] = data[i];
delete data;
data = temp;
}
|
入队
入队数据存储在last+1（last为未入队时队尾元素的下标）的位置。
1
2
3
4
5
6
7
|
template<class T>
void SeqQueue<T>::push(T p) {
if (last + 1 > maxSize)
reSize();
data[last++] = p;
}
|
出队
队列元素依次左移一个单位
1
2
3
4
5
6
7
8
9
|
template<class T>
void SeqQueue<T>::pop() {
if (isEmpty())
return;
for(int i=0;i<last;i++)
data[i] = data[i+1];
last--;
}
|
取队列顶元素
返回下标为0的一个数据
1
2
3
4
5
6
7
8
|
template<class T>
bool SeqQueue<T>::front(T &p) {
if (isEmpty())
return false;
p = data[0];
return true;
}
|
队列的大小
1
2
3
4
5
|
template<class T>
int SeqQueue<T>::size() {
return last;
}
|
打印队列
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
|
template<class T>
void SeqQueue<T>::print() {
if (isEmpty())
return;
cout << "顺序队列中的数据为： "<<endl;
for(int i=0;i<3;i++)
{
if(i==0||i==2)
{
cout<<"──────────┼";
for(int j=0;j<last;j++)
cout<<"──────┼";
cout<<"──────────"<<endl;
if(i==0)
cout<<"顺序队列首 ";
}
else
{
cout<<"|";
for (int j = 0; j <= last-1; j++)
cout <<setw(6)<< data[j] << "|";
cout<<"顺序队列尾 "<<endl;
}
}
}
|
运行结果
链式队列
通过单链表的方式来实现，使用链式结构的优点在于它能够克服用数组实现的顺序结构空间利用率不高的特点，但是需要为每个结点元素分配额外的指针空间用来存放指针域。
结点类的定义
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
| template<class T>
class LinkQueue;
template<class T>
class LinkNode {
friend class LinkQueue<T>;
private:
T data;
LinkNode<T> *next;
public:
LinkNode() {
next = NULL;
}
explicit LinkNode(T p) {
data = p;
next = NULL;
}
LinkNode<T> &operator=(const LinkNode<T> *p) {
data = p->data;
next = p->next;
return *this;
}
};
|
链式队列的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| template<class T>
class LinkQueue {
private:
LinkNode<T> *head;
public:
LinkQueue();
~LinkQueue();
void push(T p);
void pop();
bool front(T &p);
bool isEmpty();
int size();
void print();
void clear();
};
|
基本函数
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
|
template<class T>
inline LinkQueue<T>::LinkQueue() {
head = new LinkNode<T>();
}
template<class T>
inline LinkQueue<T>::~LinkQueue() {
clear();
}
template<class T>
bool LinkQueue<T>::isEmpty() {
return head->next == NULL;
}
template<class T>
void LinkQueue<T>::clear() {
LinkNode<T> *temp;
while(head->next != NULL) {
temp = head->next;
head->next = temp->next;
delete temp;
}
}
|
入队
表中的最后一个结点指向待入队结点，待入队结点指向空(NULL)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
template<class T>
void LinkQueue<T>::push(T p) {
LinkNode<T> *temp;
temp = new LinkNode<T>(p);
LinkNode<T> *q = head;
while (q) {
if (q->next == NULL) {
q->next = temp;
temp->next = NULL;
break;
}
q = q->next;
}
}
|
出队
head指向它后继节点的后继节点（head->next = head->next->next）。
1
2
3
4
5
6
7
8
9
10
11
|
template<class T>
void LinkQueue<T>::pop() {
LinkNode<T> *temp = NULL;
if (head->next != NULL) {
temp = head->next;
head->next = head->next->next;
}
delete temp;
}
|
取队列顶元素
返回 head 的后继节点的数据。
1
2
3
4
5
6
7
8
|
template<class T>
bool LinkQueue<T>::front(T &p) {
if(isEmpty())
return false;
p = head->next->data;
return true;
}
|
队列的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
|
template<class T>
int LinkQueue<T>::size() {
int len = 0;
LinkNode<T> *q = head;
while (q->next != NULL) {
len++;
q = q->next;
}
return len;
}
|
打印队列
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
|
template<class T>
void LinkQueue<T>::print() {
LinkNode<T> *p = head->next;
if (p == NULL)
return;
cout << "顺序队列中的数据为： "<<endl;
int len = size();
for(int i=0;i<3;i++)
{
if(i==0||i==2)
{
cout<<"──────────┼";
for(int j=0;j<len;j++)
cout<<"──────┼";
cout<<"──────────"<<endl;
if(i==0)
cout<<"顺序队列首 ";
}
else
{
cout<<"|";
while(p!=NULL)
{
cout <<setw(6)<< p->data << "|";
p=p->next;
}
cout<<"顺序队列尾 "<<endl;
}
}
}
|
运行结果
总结
附上源码链接：
github：
C++实现线性队列源码
C++实现链式队列源码
gitee：
C++实现链式队列源码
C++实现线性队列源码
