数据结构之栈和队列(下)

简介: 数据结构之栈和队列(下)

二.队列的概念

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

入队列:进行插入操作的一端称为队尾      出队列:进行删除操作的一端称为队头

入队列是进行尾插,出队列是进行头删。如果还用顺序表式结构头删的时候代价太大,所以这里用节点式结构来实现队列。

队列的模拟实现

queue.h

queue.h中包含队列的基本功能:入列、出列、获取队首数据、获取队尾数据、获取队列中有效数据个数。

queue.c

1. void IntiQueue(Queue* queue)//初始化队列
2. {
3.  assert(queue);
4.  queue->phead = NULL;
5.  queue->ptail = NULL;
6.  queue->size = 0;
7. }
8. void PushQueue(Queue* queue, DateType n)//入列,尾插
9. {
10.   assert(queue);
11.   Node* newnode = (Node*)malloc(sizeof(Node));//创建新节点
12.   assert(newnode);
13.   newnode->date = n;
14.   newnode->next = NULL;
15. 
16.   if (queue->ptail == NULL)//队列为空,相当于头插
17.   {
18.     assert(queue->phead==NULL);
19. 
20.     queue->phead = newnode;//头插
21.     queue->ptail = newnode;//迭代ptail,利于下次尾插入列
22.   }
23.   else//队列不为空,正常尾插
24.   {
25.     queue->ptail->next = newnode;//尾插
26.     queue->ptail = newnode;//迭代ptail
27.   }
28.   queue->size++;//有效数据加一
29. }
30. void PopQueue(Queue* queue)//头删出列
31. {
32.   assert(queue);
33.   assert(!QueueEmpty(queue));//保证队列不为空
34. 
35.   if (queue->phead->next == NULL)//一个节点,直接删
36.   {
37.     queue->phead = NULL;
38.     queue->ptail = NULL;
39.   }
40.   else//多个节点
41.   {
42.     Node* next = queue->phead->next;//先保存头节点的下一个节点地址
43.     free(queue->phead);//释放头节点空间
44.     queue->phead = next;//将头节点设为next
45.   }
46.   queue->size--;//有效数据减一
47. }
48. bool QueueEmpty(Queue* queue)//判断队列是否为空
49. {
50.   assert(queue);
51.   return queue->size == 0;//有效数据为0,队列为空,返回true
52. }
53. DateType QueueFront(Queue* queue)//获取队列头元素
54. {
55.   assert(queue);
56.   assert(!QueueEmpty(queue));//队列非空
57. 
58.   return queue->phead->date;//直接返回
59. }
60. DateType QueueBank(Queue* queue)//获取队列尾元素
61. {
62.   assert(queue);
63.   assert(!QueueEmpty(queue));//队列非空
64. 
65.   return queue->ptail->date;//直接返回
66. }
67. int QueueSize(Queue* queue)//获取有效数据个数
68. {
69.   assert(queue);
70.   return queue->size;//直接返回
71. }
72. void DestoryQueue(Queue* queue)//销毁队列
73. {
74.   assert(queue);
75.   Node* cur = queue->phead;
76.   while (cur)//循环销毁每一个节点
77.   {
78.     Node* next = cur->next;
79.     free(cur);
80.     cur = next;
81.   }
82.   queue->phead = NULL;//置空,防止野指针
83.   queue->ptail = NULL;//置空,防止野指针
84.   queue->size = 0;
85. }

总结:栈和队列只不过是顺序表与链表的子结构,关键在于实际问题中选取合适的数据结构,以及可以灵活应用数据结构解决问题。

相关文章
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
157 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
50 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
49 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
43 7
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
104 5
|
3月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
75 0
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
364 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
63 1
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
124 21
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等