队列的实现(上)

简介: 队列的实现(上)

一、 队列的概念以及结构

队列:只允许在 一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为 队尾 出队列:进行删除操作的一端称为 队头          【一端插入,一端删除,尾插,头删】

栈的使用场景:括号匹配、逆波兰表达式求解等的一些问题。还有把递归改为非递归(第一种方法,循环;第二种方法:栈)

队列的使用场景:公平排队;广度优先遍历;抽号机;

二、 队列的实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。    涉及头删、尾插。所以可以用单链表。但是尾插又需要遍历单链表,可以用一个尾指针来解决这个问题。

 

Queue.h

1. #pragma once
2. #include <stdio.h>
3. #include <assert.h>
4. #include <stdlib.h>
5. #include <stdbool.h>
6. 
7. 
8. typedef int QDataType;
9. 
10. typedef struct QueueNode
11. {
12.   struct QueueNode* next;
13.   QDataType data;
14. }QNode;
15. 
16. typedef struct Queue
17. {
18.   QNode* head;
19.   QNode* tail;
20. }Queue;
21. 
22. void QueueInit(Queue* pq);
23. void QueueDestory(Queue* pq);
24. void QueuePush(Queue* pq, QDataType x);
25. void QueuePop(Queue* pq);
26. bool QueueEmpty(Queue* pq);
27. size_t QueueSize(Queue* pq);
28. QDataType QueueFront(Queue* pq);
29. QDataType QueueBack(Queue* pq);

Queue.c

1. #define _CRT_SECURE_NO_WARNINGS 1
2. #include "queue.h"
3. 
4. void QueueInit(Queue* pq)
5. {
6.  assert(pq);
7.  pq->head = pq->tail = NULL;
8. }
9. void QueueDestory(Queue* pq)
10. {
11.   assert(pq);
12.   QNode* cur = pq->head;
13.   while (cur)
14.   {
15.     QNode* next = cur->next;
16.     free(cur);
17.     cur = next;
18.   }
19.   pq->head = pq->tail = NULL;
20. }
21. void QueuePush(Queue* pq, QDataType x)
22. {
23.   assert(pq);
24.   QNode* newnode = (QNode*)malloc(sizeof(QNode));
25.   assert(newnode);
26.   newnode->next = NULL;
27.   newnode->data = x;
28.   if (pq->tail == NULL)//链表为空的情况
29.   {
30.     assert(pq->head == NULL);//双重保证链表为空
31.     pq->head = pq->tail = newnode;
32.   }
33.   else
34.   {
35.     QNode* prev = pq->tail;
36.     prev->next = newnode;
37.     pq->tail = newnode;
38.   }
39. }
40. //错误删除代码
41. //void QueuePop(Queue* pq)
42. //{
43. //  assert(pq);
44. //  assert(pq->head && pq->tail);
45. //  QNode* next = pq->head->next;
46. //  free(pq->head);//在这里,如果删除最后一个元素的时候,tail指向的空间释放,tail就会成为野指针
47. //  pq->head = next;
48. //}
49. void QueuePop(Queue* pq)
50. {
51.   assert(pq);
52.   assert(pq->head && pq->tail);
53.   QNode* next = pq->head->next;
54.   if (next == NULL)
55.   {
56.     free(pq->head);
57.     pq->head =pq->tail = next;
58.   }
59.   else
60.   {
61.     free(pq->head);
62.     pq->head = next;
63.   }
64. }
65. 
66. 
67. bool QueueEmpty(Queue* pq)
68. {
69.   assert(pq);
70.   return pq->head == NULL;
71. }
72. 
73. size_t QueueSize(Queue* pq)
74. {
75.   assert(pq);
76.   QNode* cur = pq->head;
77.   size_t size = 0;
78.   while (cur)
79.   {
80.     size++;
81.     cur = cur->next;
82.   }
83. return size;
84. }
85. QDataType QueueFront(Queue* pq)
86. {
87.   assert(pq);
88.   assert(pq->head);
89.   return pq->head->data;
90. }
91. QDataType QueueBack(Queue* pq)
92. {
93.   assert(pq);
94.   assert(pq->tail);
95.   return pq->tail->data;
96. }

 

注意:(1)size_t 就是unsigned int

(2)当出现a->b->c的时候,就要注意最后面的时候,是否会出现野指针。

三、习题

3.1 选择题

1.循环队列的存储空间为 Q(1:100) ,初始状态为 front=rear=100 。经过一系列正常的入队与退队操作 后, front=rear=99 ,则循环队列中的元素个数为( D)

A 1

B 2

C 99

D 0

2.以下( B)不是队列的基本运算?

A 从队尾插入一个新元素

B 从队列中删除第i个元素

C 判断一个队列是否为空

D 读取队头元素的值

3.现有一循环队列,其队头指针为front,队尾指针为rear;循环队列长度为N,实际最多可存储N-1个数据。其队内有效长度为?(假设队头不存放数据)(B)

A (rear - front + N) % N + 1

B (rear - front + N) % N    因为rear指向的内容是空

C (rear - front) % (N + 1)

D (rear - front + N) % (N - 1)

 

3.2 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

代码如下:

1. //定义一个栈的结构体,栈里面是两个队列
2. typedef struct {
3.     Queue q1;//q1和q2分别是结构体
4.     Queue q2;
5. } MyStack;
6. 
7. //相当于初始化,由于需要返回的是结构体指针,所以不能在函数里创建一个结构体,返回结构体的地址,因为出了这个函数,又被销毁了。所以应该malloc一个结构体。
8. MyStack* myStackCreate() {
9.     MyStack* pst = (MyStack*)malloc(sizeof(MyStack));//结构体的地址
10. assert(pst);
11. QueueInit(&pst->q1);//->的优先级>&的优先级
12. QueueInit(&pst->q2);//两个队列初始化完成,就表示栈也初始化完成
13. return pst;
14. }
15. 
16. void myStackPush(MyStack* obj, int x) {
17. assert(obj);
18. //在不为空的队列里面插入数,
19. if (!QueueEmpty(&obj->q1))
20.     {
21. QueuePush(&obj->q1,x);
22.     }
23. else
24.     {
25. QueuePush(&obj->q2,x);
26.     }
27. }
28. //删除栈顶的数据,并返回栈顶的数据
29. int myStackPop(MyStack* obj) {
30. assert(obj);
31.     Queue* emptyQ = &obj->q1;
32.     Queue* nonEmptyQ = &obj->q2;
33. if (!QueueEmpty(&obj->q1))
34.     {
35.         emptyQ = &obj->q2;
36.         nonEmptyQ = &obj->q1;
37.     }
38. while (QueueSize(nonEmptyQ) > 1)
39.     {
40. int front = QueueFront(nonEmptyQ);
41. QueuePush(emptyQ, front);
42. QueuePop(nonEmptyQ);
43.     }
44. int top = QueueFront(nonEmptyQ);
45. QueuePop(nonEmptyQ);
46. return top;
47. }
48. //栈顶的数据,就是队列的队尾的数据
49. int myStackTop(MyStack* obj) {
50. assert(obj);
51. if (!QueueEmpty(&obj->q1))
52.     {
53. return QueueBack(&obj->q1);
54.     }
55. else
56.     {
57. return QueueBack(&obj->q2);
58.     }
59. }
60. //两个队列都为空,才能证明栈为空
61. bool myStackEmpty(MyStack* obj) {
62. assert(obj);
63. return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
64. }
65. 
66. void myStackFree(MyStack* obj) {
67. assert(obj);
68. QueueDestory(&obj->q1);
69. QueueDestory(&obj->q2);
70. free(obj);
71. }

思路:入栈:push数据到不为空的队列;出栈:把不为空的队列数据前N-1导入另一个空队列,把最后一个剩下的删掉。【本质是保持一个队列存储数据,另外一个队列空着,要出栈时,空队列用来导数据】


相关文章
|
自然语言处理 算法 知识图谱
DEGREE: A Data-Efficient Generation-Based Event Extraction Model论文解读
事件抽取需要专家进行高质量的人工标注,这通常很昂贵。因此,学习一个仅用少数标记示例就能训练的数据高效事件抽取模型已成为一个至关重要的挑战。
385 0
|
JSON 开发工具 Android开发
通知消息和透传消息
通知消息和透传消息
1088 0
通知消息和透传消息
|
Java
Java:SpringBoot整合hutool-captcha实现图片验证码功能
Java:SpringBoot整合hutool-captcha实现图片验证码功能
1207 0
Java:SpringBoot整合hutool-captcha实现图片验证码功能
|
弹性计算 监控 JavaScript
关于一个大三学生做项目新手入坑的经验之谈
通过阿里云的实验简单的知道了云服务器的认识和了解,大概知道了云服务器的作用,他给我们带来了许多便利。
|
算法 缓存 测试技术
去除字符串中重复字符
题目 设计算法并写出代码移除字符串中重复的字符,不能使用额外的缓存空间。注意: 可以使用额外的一个或两个变量,但不允许额外再开一个数组拷贝。 进一步地, 为你的程序写测试用例。 解答 这道题目其实是要你就地(in place)将字符串中重复字符移除。
840 0
|
3天前
|
人工智能 JavaScript 测试技术
Qwen3-Coder入门教程|10分钟搞定安装配置
Qwen3-Coder 挑战赛简介:无论你是编程小白还是办公达人,都能通过本教程快速上手 Qwen-Code CLI,利用 AI 轻松实现代码编写、文档处理等任务。内容涵盖 API 配置、CLI 安装及多种实用案例,助你提升效率,体验智能编码的乐趣。
301 100
|
4天前
|
JSON fastjson Java
FastJson 完全学习指南(初学者从零入门)
摘要:本文是FastJson的入门学习指南,主要内容包括: JSON基础:介绍JSON格式特点、键值对规则、数组和对象格式,以及嵌套结构的访问方式。FastJson是阿里巴巴开源的高性能JSON解析库,具有速度快、功能全、使用简单等优势,并介绍如何引入依赖,如何替换Springboot默认的JackJson。 核心API: 序列化:将Java对象转换为JSON字符串,演示对象、List和Map的序列化方法; 反序列化:将JSON字符串转回Java对象,展示基本对象转换方法;