【数据结构】栈和队列专题

前言

上篇博客我们讨论了栈和队列的有关结构，本篇博客我们继续来讨论有关栈和队列习题

这些题算是经典了

💓 个人主页：小张同学zkf

⏩ 文章专栏：数据结构

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章 ​

 

 

目录

1. 括号匹配问题 

2.用队列实现栈

3.用栈实现队列

4.设计循环队列

---

 

1. 括号匹配问题 

由题可知我们需要判断一对括号是否成立，成立的话，就返回true，失败的话就返回false，这道题乍一看不好判断，其实我们可以用栈来解决，栈是后进先出的原则，我们可以判断如果是左括号的话让这个括号进栈，如果是右括号的话，让栈里的括号出栈与右括号匹对，若匹对成功，则继续判断下一个括号，这里我们需要考虑极端情况，假如括号都遍历完了，栈内还有左括号，代表此时左括号多，不匹配，所以还需要判断栈是否为空，还有如果第一个入栈的括号若是右括号，必定不匹配，直接false。

思路已给出，代码如下

对于c语言来说，注意先把栈写好，写好后再调用栈的函数，后续c++就不用这么麻烦了

---

2.用队列实现栈

 

这道题就是给你两个队列，通过队列实现一个栈，我们都知道栈是后进先出的原则，而队列是先进先出的原则，那如何用两个队列实现栈那？

 

首先我们思考，假如现在有两个队列q1和q2，我们画图分析

根据图上操作要想实现栈的后进先出的原则，我们在入栈时先用一个队列q1来做入栈操作，若出栈，由于后进先出的原则，我们可以先把除最后一个元素，剩下的元素全部导入q2，然后再将还在q1的元素通过出队的方式实现出栈，若继续入栈，此刻元素都在q2那么就用q2实现入栈操作，然后出栈时，按照上面的操作来回导入就可以了。 

所以出栈比较难，其他操作都是常规的，我们说一下出栈，我们可以用假设法，分为空的队列和非空的队列，非空的队列前size-1的元素，pop出来再push进空的队列，再pop最后一个元素

对了，判空条件是两个队里都没元素时，此刻栈为空

代码如下

---

3.用栈实现队列

 

 两个队列可以实现栈，那两个栈如何实现队列那

队列是先进先出原则，那对于栈来说，后进先出，若两个栈，将第一个栈的所有元素全部导入第二个栈，此刻我们想想比如第一个栈原本1,2,3,4，现在导入第二个栈此刻是不是就是4,3,2,1，此刻第二个栈若出栈的话正好符合了队列的先进先出

我们可以在画图看一下

其实对于两个栈，将第一个栈导入另一个栈，原本第一个栈的元素是后进先出的原则，导入第二个栈就变成现进先出了

代码如下

 

---

4.设计循环队列

重头戏来了

循环队列，就是在一个有限空间里重复利用，如图

 

如图，我们用两个指针指向数组头，一个是队头指针head，一个是队尾指针tail，push数据时，tail++，相当于Tail指向的是最后一个元素的下一个位置·，这一点跟栈栈顶元素有点类似，当初始化为0时， 指针指向最后一个元素的下一个位置，pop的话移动头元素head就行了，不过上面的图不现实，因为队列空和满时对应的条件都一样，都是head=Tail，所以我们得找一个办法让这个条件不一样，才能判空

一种是用一个size变量加加，记录数据，这是一种方法。

其实还有另一种方法，我们可以多一个空间,开k+1个空间，但只能放k个元素

如图，此刻若放满正好是第四个图，相当于tail的下一个位置就是head，那么我们是不是可以根据取模得到关系（tail+1）%(k+1)==head达到这个条件就是满，空的条件就很简单，head==Tail

 

如果是返回尾元素，就是tail指针指向的上一个位置，tail-1，但是我们得考虑如上图这种情况，Tail回到前面，但是此刻tail－1越界了，所以这时我们可以根据取模，(Tail-1+k+1)%(k+1) 就得到了尾元素的位置

头元素就是head指向的元素

OK，剩下的操作就是常规操作，代码如下

---

 结束语

栈与队列经典习题就结束了，有什么问题可私聊我，里面的满足条件多想一想就能想明白，特别是最后一道题

OK,本篇博客结束！！！