加载中...
avatar

C++实现链式队列和线性队列

前言

   队列(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; //初始最大存储量为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--; //数据个数-1
}

取队列顶元素

返回下标为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++实现线性队列源码

文章作者: 云开、见月明
文章链接: https://chenyunxin.cn/posts/3058917998.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 云开の博客
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论