栈和队列经典OJ

简介: 栈和队列经典OJ

栈和队列相关代码在前面已经实现过了,接下来就手撕几道有关栈和队列的几道高频经典OJ,让大家更加深刻的理解栈和队列这两种数据结构。




第一题:用栈实现队列

OJ链接:

232. 用栈实现队列 - 力扣(LeetCode)


题目要求用两个栈实现一个队列,要求具备队列基本接口:入列,出列,返回队列头元素,判断队列是否为空。接下来我们按照 ” 一定能写出来四步流程 “,来完成这个题目。

一.思路分析:

我们知道,队列有先进先出(FIFO)的原则,所以要想用两个栈实现队列,就必须用这两个栈使得数据先进先出。因为栈是先进后出的原则,会使得出数据顺序相反,所以用两个栈就刚好可以把顺序摆正。例如 1 2 3 4进入第一个栈---->4 3 2 1进入第二个栈---->1 2 3 4

二.细节分析

我们把两个栈分别取名为pushstack、popstack。即一个栈专门用来入队列,一个栈专门用来出队列。

1.当有元素要入队列:只需要把这个元素入栈到pushstack。

2.当有元素要出队列:如果popstack栈中有元素,直接出栈即可。如果popstack栈中没有元素,需要将pushstack栈中的元素捯入popstack栈。再出popstack栈。

3.返回队首元素:如果popstack栈中有元素,直接返回栈顶元素即可。如果popstack栈中没有元素,需要将pushstack栈中的元素捯入popstack栈。再返回popstack栈顶元素。

4.判断队列是否为空:若两个栈都为空,则队列为空。

三.代码实现

1. //栈的实现
2. typedef int DateType;
3. typedef struct Stack//栈的总架构(这里是动态栈)
4. {
5.  DateType* arr;
6.  int top;//栈顶下标
7.  int capcity;//栈的容量
8. }Stack;
9. //下面对栈的操作都是改变结构体内部的属性,参数列表传结构体一级指针
10. void IntiStack(Stack* stack);//初始化栈
11. void PushStack(Stack* stack, DateType n);//进栈,尾插
12. void PopStack(Stack* stack);//出栈,尾删
13. bool StackEmpty(Stack* stack);//检测栈是否为空
14. int StackSize(Stack* stack);//获取栈中有效数据个数
15. DateType TopStack(Stack* stack);//获取栈顶数据
16. void DestoryStack(Stack* stack);//销毁栈
17. 
18. void IntiStack(Stack* stack)
19. {
20.   DateType* tmp = (DateType*)malloc(4*sizeof(DateType));
21.   assert(tmp);
22.   stack->arr = tmp;
23.   stack->top = 0;
24.   stack->capcity = 4;
25. }
26. void PushStack(Stack* stack, DateType n)
27. {
28.   assert(stack);
29.   if (stack->top == stack->capcity)
30.   {
31.     //扩容
32.     DateType* tmp = realloc(stack->arr,2 * stack->capcity * sizeof(DateType));
33.     assert(tmp);
34.     stack->arr = tmp;
35.     stack->capcity *= 2;
36.   }
37.   stack->arr[stack->top] = n;
38.   stack->top++;
39. }
40. void PopStack(Stack* stack)
41. {
42.   assert(stack);
43.   assert(!StackEmpty(stack));
44.   stack->top--;
45. }
46. bool StackEmpty(Stack* stack)
47. {
48.   assert(stack);
49.   return stack->top == 0;
50. }
51. int StackSize(Stack* stack)
52. {
53.   assert(stack);
54.   return stack->top;
55. }
56. DateType TopStack(Stack* stack)
57. {
58.   assert(stack);
59.   assert(!StackEmpty(stack));
60.   return stack->arr[stack->top - 1];
61. }
62. void DestoryStack(Stack* stack)
63. {
64.   assert(stack);
65.   free(stack->arr);
66.   stack->arr = NULL;
67.   stack->capcity = 0;
68.   stack->top = 0;
69. }
70. 
71. //开始解题
72. typedef struct//定义队列
73. {
74.     Stack pushstack;//定义两个栈
75.     Stack popstack;
76. } MyQueue;
77. MyQueue* myQueueCreate()//初始化队列
78. {
79.     MyQueue* queue=(MyQueue*)malloc(sizeof(MyQueue));//为队列分配空间,顺便为两个栈分配空间
80. IntiStack(&queue->pushstack);//初始化两个栈
81. IntiStack(&queue->popstack);
82. return queue;
83. }
84. void myQueuePush(MyQueue* obj, int x)//入列
85. {
86. PushStack(&obj->pushstack,x);//把这个元素入栈到pushstack
87. }
88. 
89. int myQueuePop(MyQueue* obj)//出列
90. {
91. int tmp=myQueuePeek(obj);//获取队列头元素(popstack栈顶元素)
92. PopStack(&obj->popstack);//删除popstack栈顶元素
93. return tmp;//返回队列头元素
94. }
95. int myQueuePeek(MyQueue* obj)//获取队首元素
96. {
97. if(StackEmpty(&obj->popstack))//如果popstack栈为空
98.     {
99. //导pushstack栈的数据->popstack栈
100. while(!StackEmpty(&obj->pushstack))//循环条件:pushstack栈不为空
101.         {
102. //将pushstack栈顶元素入栈到popstack栈
103. PushStack(&obj->popstack,TopStack(&obj->pushstack));
104. //删除pushstack栈顶元素
105. PopStack(&obj->pushstack);
106.         }
107.     }
108. return TopStack(&obj->popstack);//返回popstack栈顶元素
109. }
110. bool myQueueEmpty(MyQueue* obj)//判断队列是否为空
111. {
112. //两个栈都为空,队列为空,返回true
113. return StackEmpty(&obj->pushstack)&&StackEmpty(&obj->popstack);
114. }
115. void myQueueFree(MyQueue* obj)//销毁队列
116. {
117. DestoryStack(&obj->pushstack);//先销毁里面两个栈中的顺序表空间
118. DestoryStack(&obj->popstack);
119. free(obj);//再释放队列空间(可以释放两个栈的空间,但是无法是释放栈里面的顺序表空间!)
120. }

四.总结

用栈实现队列本质需要了解栈与队列的区别,知道二者数据处理的差异,并灵活应用。

 

目录
打赏
0
0
0
0
0
分享
相关文章
|
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++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
43 7
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
364 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
63 1
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
49 9
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
104 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
124 21
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
AI助理

你好,我是AI助理

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