栈和队列详解（附相关面试题）

目录

一、栈

栈的概念及结构

栈的实现

oj ->括号匹配问题：20. 有效的括号 - 力扣（LeetCode）

二、队列

队列的概念及结构

队列的实现

oj->设计循环队列

三、两道面试题

用队列实现栈

用栈实现队列

1、栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 栈的实现

1.2.1 栈创建：栈可以用链表也可以用数组来创建，但一般是用数组，因为在数组尾上插入数据，其代价比较小。

1.2.2：栈的入栈，也叫压栈：在实现压栈之前，我们必须定义一下，指向栈顶的top，是指向元素的下一个位置还是元素的位置。我们这里使用的是top==0，指向元素下一个位置的方法。

压栈的时候，只需要将数据插入到top的位置，然后让top移动到下一个位置即可。

1.2.3 栈的出栈 由于遵循后进先出，自然是从数组的尾部进行出栈。也就是top--的这个位置开始出栈。

完整代码放在gitee仓库中：Stack List: 数据结构之栈的操作

 1.3 括号匹配问题        链接：20. 有效的括号 - 力扣（LeetCode）

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

思路：使用栈来进行判断，将字符串中的左括号入栈，然后提取栈顶中的字符，和没入栈的右括号进行匹配。

 但是要注意，如'( ( ) '这样的例子，奇数个的时候，匹配成功了一次，剩下的没得匹配，在最后返回的bool值的时候，要进行栈的判空。以下是使用c语言实现的代码：

 2、队列

2.1 队列的概念及结构

        队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。可以将队列的增删操作想象成打饭排队，在队尾排队，在队头的窗口打饭，然后离开，而且不允许插队！

2.2 队列的实现

        队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，因为要挪动数据。

 代码实现：

 2.3 设计循环队列  题目链接：622. 设计循环队列 - 力扣（LeetCode）

 思路：对于循环队列，我们使用数组的形式来实现循环队列。为什么呢？因为在出队尾元素的时候，链式结构需要遍历一边，找出队尾的上一个元素，而在数组中，只需要根据下标找出即可。循环队列最主要的问题是，如何判断队满和队空？

队空：rear == front，即头尾的相等。

队满：如果我们将队满的条件也设为rear==front，这显然很不对。因此，我们可以在在原本的数组长度，即队列长度n的基础上，再增加一个空间，这个空间是不放数据的，让rear指向它。于是，判满的条件是（rear+1）%(n+1),这样，就能判断队满。

 另外：计算循环队列中的有效长度：现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？（其中的n，n-1放了数据）：（rear-front+n）%n

题目的代码：

 3.两道面试题：

3.1 用队列实现栈  题目链接：225. 用队列实现栈 - 力扣（LeetCode）

解题思路：由于队列遵循先进先出，也就是在饭堂打饭的时候，先排队的先打完饭。而栈，是后进先出，那么我们可以使用两个队列，始终留一条空的队列来存放另外一条队列的元素，然后剩下最后一个元素直接出队。

以下是代码：（是使用c语言来写，队列的实现需要自己来实现）

 3.2 用栈实现队列 题目链接：232. 用栈实现队列 - 力扣（LeetCode）

解题思路：本题也使用两个栈来实现队列，因为栈是后进先出的，通过画图，就可以发现，只要把一条栈上的元素放到另外一条栈上，那么元素都会颠倒过来，然后对这一条栈进行出栈，就是出队的顺序了！

 以上，就是栈和队列的实现，还有其相关的题目的思路啦！如果有哪里不对的，恳请大伙指出！