前言：我之前有看过一些博主说，他们工作时要求做一个银行排队系统；
当然实现的方法各种各样，今天介绍的是我们数据结构中的队列queue,当然c++里面有现成的可以用，甚至还有优先队列，但了解原理也很重要啊！
依旧是我百度copy 的图
当然除了线性队列还有循环队列，之前刷过的题里面就涉及到了，依旧上图
1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列； 2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；
3、void AddQ( Queue Q, ElementType item ) 将数据元素item插入队列Q中；
4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；
5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。
文章目录
- 顺序表
- 创建
- 对首&队尾
- 判断队列是否已满
- 插入
- 判断是否为空
- 删除
- 链式表
- 创建
- 队首&队尾
- 是否为空
- 删除
- 插入
顺序表
创建
同样因为是顺序表，需要提前给出容量
1
2
3
4
5
6
7
8typedef int Position; struct QNode { ElementType* Data; /* 存储元素的数组 */ Position Front, Rear; /* 队列的头、尾指针 */ int MaxSize; /* 队列最大容量 */ }; typedef struct QNode* Queue;
对首&队尾
队首和队尾本身是不给值的
1
2
3
4
5
6
7
8
9Queue CreateQueue(int MaxSize) { Queue Q = (Queue)malloc(sizeof(struct QNode)); Q->Data = (ElementType*)malloc(MaxSize * sizeof(ElementType)); Q->Front = Q->Rear = 0; Q->MaxSize = MaxSize; return Q; }
判断队列是否已满
1
2
3
4
5bool IsFull(Queue Q) { return ((Q->Rear + 1) % Q->MaxSize == Q->Front); }
Front和rear 指针的移动 采用“加1取 余”法，体 现了顺序存 储的“循环 使用”。
插入
插入肯定插在尾巴处嘛
你排队也是先来后到 先进先出不是
1
2
3
4
5
6
7
8
9
10
11
12
13bool AddQ(Queue Q, ElementType X) { if (IsFull(Q)) { printf("队列满"); return false; } else { Q->Rear = (Q->Rear + 1) % Q->MaxSize; Q->Data[Q->Rear] = X; return true; } }
判断是否为空
是否为空只要看头和尾是不是在一起
1
2
3
4
5bool IsEmpty(Queue Q) { return (Q->Front == Q->Rear); }
删除
删除你就头指针往后挪一个呗
1
2
3
4
5
6
7
8
9
10
11
12ElementType DeleteQ(Queue Q) { if (IsEmpty(Q)) { printf("队列空"); return ERROR; } else { Q->Front = (Q->Front + 1) % Q->MaxSize; return Q->Data[Q->Front]; } }
链式表
创建
1
2
3
4
5
6
7typedef struct Node* PtrToNode; struct Node { /* 队列中的结点 */ ElementType Data; PtrToNode Next; }; typedef PtrToNode Position;
队首&队尾
此时你的容量是可以随队列的长度而更改的
1
2
3
4
5
6struct QNode { Position Front, Rear; /* 队列的头、尾指针 */ int MaxSize; /* 队列最大容量 */ }; typedef struct QNode* Queue;
是否为空
看队首有没有值呗
1
2
3
4
5bool IsEmpty(Queue Q) { return (Q->Front == NULL); }
删除
先声明定义指针和元素
删除的话就要考虑两种情况
只有一个元素和有多个元素
毕竟只有一个元素的时候队首也没有下一个结点给你☞了呀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22ElementType DeleteQ(Queue Q) { Position FrontCell; ElementType FrontElem; if (IsEmpty(Q)) { printf("队列空"); return ERROR; } else { FrontCell = Q->Front; if (Q->Front == Q->Rear) /* 若队列只有一个元素 */ Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */ else Q->Front = Q->Front->Next; FrontElem = FrontCell->Data; free(FrontCell); /* 释放被删除结点空间 */ return FrontElem; } }
插入
和之前那些差不多啦
相信认真看到这
插入估计自己也会了！
只需要让它指向队尾所指的元素，再让队尾指向它就好了。
自己动手尝试一下吧！
最后
以上就是光亮宝马最近收集整理的关于坚持代码实现数据结构DAY04——队列顺序表链式表的全部内容，更多相关坚持代码实现数据结构DAY04——队列顺序表链式表内容请搜索靠谱客的其他文章。
发表评论 取消回复