「堆栈」作为计算机科学中的一个专有词语，在许多的面试和考试中会出现，一般在面试的过程中我们讨论的「堆栈」指的是数据结构中的堆栈，此外，计算机操作系统中也有关于堆栈的定义，我们需要明确操作系统中的堆、栈和数据结构堆、栈不是一个概念，它们除了名字一样没有什么必然的联系，本文主要介绍数据结构中的堆栈，有兴趣的同学可以去了解一下操作系统中的堆栈。
堆、栈和队列
在数据结构中，「堆栈」分别有着以下含义：
- 栈（Stack）又名堆栈，作为一个 先进后出 的数据结构。（注意：这里的堆栈本身就是栈，只是换了个抽象的名字。）
它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
其运行方式如下：
另外补充一个和堆栈比较相关的概念——队列
- 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
- 队列采用 先进先出 FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。
在了解了上面一些基本的概念后，我们来看看在实际的面试中有可能会遇到哪些相关的题目吧~
面试题
「一个栈来确认括号是否匹配」这类题目不仅会出现在面试当中，在许多高校的编程题目中也会有所出现。在力扣（LeetCode）上有这样一个题目：
题目描述
'('')''{''}''['']'有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意：空字符串可被认为是有效字符串。
示例 1:
示例 2:
示例 3:
示例 4:
示例 5:
解题思路
false( ) [ ]()([][(](](falseC++ 代码实现如下：
有了栈的知识之后，另一个可以用栈来完成的操作是实现一个队列，比如在力扣（LeetCode）上有这样一个题目：
232.用栈实现队列
题目描述
使用栈实现队列的下列操作：
- push(x) -- 将一个元素放入队列的尾部。
- pop() -- 从队列首部移除元素。
- peek() -- 返回队列首部的元素。
- empty() -- 返回队列是否为空。
示例:
说明:
push to toppeek/pop from topsizeis empty解题思路
在上面的介绍中我们得知队列是一种先进先出（first in - first out， FIFO）的数据结构，队列中的元素都从后端（rear）入队（push），从前端（front）出队（pop）。 实现队列最直观的方法是用链表，但在这篇文章里我会介绍另一个方法 - 使用栈。 栈是一种 后进先出（last in - first out， LIFO）的数据结构，栈中元素从栈顶（top）压入（push)，也从栈顶弹出（pop）。 为了满足队列的 FIFO 的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。
C++ 实现如下：
下面来看一个考察「堆」的面试题：
题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
解题思路
一个最简单的想法是通过暴力的方法先遍历整个链表到一个数组中进行排序，然后将已经排序的新数组生成一个新的链表。
Python 实现如下：
但是这个方法仅仅是能用而已，由于需要遍历整个列表，必然会导致一个非常高的时间复杂度，且由于这个是堆相关的面试题，所以我们可以考虑使用 最小堆 的方法。
首先把 k 个链表的首元素都加入最小堆中，它们会自动排好序。然后我们每次取出最小的那个元素加入我们最终结果的链表中，然后把取出元素的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时 k 个链表也合并为了一个链表，返回首节点即可。
C++ 实现如下：
拓展练习
看完这篇文章，不知道你对堆、栈和队列是否有了一些基本的了解。在力扣上有许多相关题目供大家练习。例如，
「堆」（共有 34 道）
「栈」（共有 49 道）
「队列」（共有 9 道）
你还可以搭配 探索卡片进行针对性练习～