C++ OOP方法实现链式队列
队列
队列（Queue）是一个先进先出（First In First Out, FIFO）的数据结构，即先入队的元素先出队。队列有两种存储形式：顺序存储和链式存储，采用顺序存储方式的队列称为顺序队列，采用链式存储的队列称为链式队列。顺序队列采用数组存储队列中的元素，由队头指针head和队尾指针tail表示队列的头尾。链式队列采用链表实现，由头结点和若干个队列元素节点组成，头结点包括队头指针head、队尾指针和队列大小size三个域，head指针指向队头，tail指针指向队尾，队列元素节点由值域val和指针域next组成，val代表队列元素的值，next代表指向下一个队列结点的指针。其中，较为常用的是链式队列，下面将详细介绍链式队列的属性、方法以及C++代码实现。
队列属性和方法介绍
对队列进行抽象，可将其表示为包括队头指针、队尾指针和队列大小三个属性的数据结构。队列的基本操作包括入队、出队、队列判空、队列销毁、队列元素输出等，其伪代码如下：
1
2
3
4
5
6
7
8//队列定义
queue：
head, tail, size//head:队头指针、tail：队尾指针、size：队列大小
enqueue(elem)//入队
dequeue()//出队
is_empty()//队列判空
destory()//队列销毁
traverse()//队列元素输出链式队列C++实现
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
using namespace std;
//队列中的元素结点
class QueueNode{
public:
int val;//值域
QueueNode *next;//指针域，指向下一个队列元素
};
//队列
class Queue{
private:
int size;//队列大小
public:
QueueNode *head;//队头指针
QueueNode *tail;//队尾指针
Queue();//构造函数，完成对象初始化工作
~Queue();//析构函数
void enqueue(int val);//入队
int dequeue();//出队
bool is_empty();//队列判空
void destory();//销毁队列
void traverse();//输出队列中的所有元素
int get_size();//获取队列大小
};
//获取队列大小
int Queue::get_size(){
return this->size;
}
//构造函数
Queue::Queue(){
this->head = this->tail = NULL;
this->size = 0;
}
//析构函数
Queue::~Queue(){
}
//入队
void Queue::enqueue(int val){
QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
node->val = val;
node->next = NULL;
if(this->head == NULL){
this->head = node;
this->tail = node;
}
else{
this->tail->next = node;
this->tail = node;
}
this->size += 1;
};
//出队
int Queue::dequeue(){
if(this->is_empty() == 1){
cout << "队列为空，没有元素可以出队，请先向队列中添加元素！" << endl;
return -1;
}
int val = this->head->val;
this->head = this->head->next;
this->size -= 1;
return val;
}
//队列判空
bool Queue::is_empty(){
if(this->size == 0){
return true;
}
else
{
return false;
}
}
//输出所有队列元素
void Queue::traverse(){
if(this->is_empty() == 1){
cout << "队列为空！" << endl;
return;
}
cout << "队列所有元素如下：" << endl;
QueueNode *p_node = this->head;
while(p_node != NULL)
{
cout << p_node->val << endl;
p_node = p_node->next;
}
}
//销毁队列
void Queue::destory(){
if(this->is_empty() == 1){
cout << "队列中没有元素！" << endl;
return;
}
int val = this->dequeue();
while(val != -1){
val = this->dequeue();
}
cout << "queue is destroyed!" << endl;
}
//主函数
int main(){
//队列定义
Queue queue;
//操作队列
queue.enqueue(1);//元素入队列
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
int val = queue.dequeue();//元素出队列
cout << "出队元素为：" << val << endl;
queue.traverse();//输出所有队列元素
queue.destory();//销毁队列
queue.traverse();
cout << "queue.size:" << queue.get_size() << endl;//输出队列大小
cout << queue.is_empty() << endl;//队列判空
return 0;
}