栈与队列基本知识（面试中常考的堆）

「堆栈」作为计算机科学中的一个专有词语，在许多的面试和考试中会出现，一般在面试的过程中我们讨论的「堆栈」指的是数据结构中的堆栈，此外，计算机操作系统中也有关于堆栈的定义，我们需要明确操作系统中的堆、栈和数据结构堆、栈不是一个概念，它们除了名字一样没有什么必然的联系，本文主要介绍数据结构中的堆栈，有兴趣的同学可以去了解一下操作系统中的堆栈。

堆、栈和队列

在数据结构中，「堆栈」分别有着以下含义：

• 堆（heap）也被称为优先队列，队列中允许的操作是 先进先出（FIFO），在队尾插入元素，在队头取出元素。而堆也是一样，在堆底插入元素，在堆顶取出元素。二叉树的衍生，有最小堆最大堆的两个概念，将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
• 有一个比较有名的堆排序算法正是基于这个数据结构而来，在 视频｜手撕九大经典排序算法，看我就够了！ 中我们有所涉及，欢迎有兴趣的读者进行学习。

• 栈（Stack）又名堆栈，作为一个 先进后出 的数据结构。（注意：这里的堆栈本身就是栈，只是换了个抽象的名字。）

它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

• 其运行方式如下：

另外补充一个和堆栈比较相关的概念——队列

• 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
• 队列采用 先进先出 FIFO(first in first out)，新元素（等待进入队列的元素）总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。因而也不存在溢出等问题。由于链表由结构体间接而成，遍历也方便。

在了解了上面一些基本的概念后，我们来看看在实际的面试中有可能会遇到哪些相关的题目吧~

面试题

「一个栈来确认括号是否匹配」这类题目不仅会出现在面试当中，在许多高校的编程题目中也会有所出现。在力扣（LeetCode）上有这样一个题目：

20.有效的括号力扣

题目描述

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

有效字符串需满足：

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

注意：空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true

示例 2:

输入: "()[]{}" 输出: true

示例 3:

输入: "(]" 输出: false

示例 4:

输入: "([)]" 输出: false

示例 5:

输入: "{[]}" 输出: true

解题思路

对于没有学过「栈」这个数据结构的同学来说可能遇到这一类的问题咋一看可能有点没有头绪，但是其实只需要判断下一个元素是否在栈顶即可判断括号的匹配情况，即如果遇到一个左括号，我们将这个符号插入压栈，如果遇到一个右括号，我们判断一下栈顶的元素是否是对应的左括号，如果是（即与栈顶元素匹配），那么就一起出栈，否则的话直接返回 false 表示字符串无效。

我们来看一例子，假设字符串是 ( ) [ ]，栈的变化分别为：

1. ( 入栈
2. ) 入栈，发现与栈顶元素 ( 匹配，出栈，目前栈为空
3. [ 入栈
4. ] 入栈，发现和栈顶元素 [ 匹配，出栈，栈为空

而如果是：(]，栈的变化会是怎么样的呢？

1. ( 入栈
2. ] 入栈，栈顶元素为 (，不匹配，直接返回 false

C 代码实现如下：

class Solution { public: bool isValid (string const& s) { // 定义左右两边的括号序列 string left = "([{"; string right = ")]}"; stack<char> stk; ​ for (auto c : s) { // 判断每一个输入的字符是否为左括号，如果是就压栈 if (left.find(c) != string::npos) { stk.push (c); } else { // 如果不是左括号，且如果发现栈为空，或者栈顶元素不是匹配的左括号的话，就返回 false if (stk.empty () || stk.top () != left[right.find (c)]) return false; // 如果匹配的话，就把栈顶出栈 else stk.pop (); } } return stk.empty(); } };

有了栈的知识之后，另一个可以用栈来完成的操作是实现一个队列，比如在力扣（LeetCode）上有这样一个题目：

232.用栈实现队列

题目描述

使用栈实现队列的下列操作：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue(); ​ queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

解题思路

在上面的介绍中我们得知队列是一种先进先出（first in - first out， FIFO）的数据结构，队列中的元素都从后端（rear）入队（push），从前端（front）出队（pop）。 实现队列最直观的方法是用链表，但在这篇文章里我会介绍另一个方法 - 使用栈。 栈是一种 后进先出（last in - first out， LIFO）的数据结构，栈中元素从栈顶（top）压入（push)，也从栈顶弹出（pop）。 为了满足队列的 FIFO 的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。

C 实现如下：

class MyQueue { public: /** Initialize your data structure here. */ MyQueue() : s1(), s2(){ } /** Push element x to the back of queue. */ void push(int x) { s1.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } int ret = s2.top(); s2.pop(); return ret; } /** Get the front element. */ int peek() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } return s2.top(); } /** Returns whether the queue is empty. */ bool empty() { return s1.empty() && s2.empty(); } private: stack<int> s1; stack<int> s2; }; /** * Your MyQueue object will be instantiated and called as such: * MyQueue* obj = new MyQueue(); * obj->push(x); * int param_2 = obj->pop(); * int param_3 = obj->peek(); * bool param_4 = obj->empty(); */

下面来看一个考察「堆」的面试题：

​23.合并K个排序链表力扣

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->4->4->5->6

解题思路

一个最简单的想法是通过暴力的方法先遍历整个链表到一个数组中进行排序，然后将已经排序的新数组生成一个新的链表。

Python 实现如下：

class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ self.nodes = [] head = point = ListNode(0) for l in lists: while l: self.nodes.append(l.val) l = l.next for x in sorted(self.nodes): point.next = ListNode(x) point = point.next return head.next

但是这个方法仅仅是能用而已，由于需要遍历整个列表，必然会导致一个非常高的时间复杂度，且由于这个是堆相关的面试题，所以我们可以考虑使用 最小堆 的方法。

首先把 k 个链表的首元素都加入最小堆中，它们会自动排好序。然后我们每次取出最小的那个元素加入我们最终结果的链表中，然后把取出元素的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时 k 个链表也合并为了一个链表，返回首节点即可。

C 实现如下：

class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { auto cmp = [](ListNode*& a, ListNode*& b) { return a->val > b->val; }; priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp); for (auto node : lists) { if (node) q.push(node); } ListNode *dummy = new ListNode(-1), *cur = dummy; while (!q.empty()) { auto t = q.top(); q.pop(); cur->next = t; cur = cur->next; if (cur->next) q.push(cur->next); } return dummy->next; } };

拓展练习

看完这篇文章，不知道你对堆、栈和队列是否有了一些基本的了解。在力扣上有许多相关题目供大家练习。例如，

「堆」（共有 34 道）

• 接雨水 II
• 滑动窗口最大值
• 网络延迟时间

「栈」（共有 49 道）

• 接雨水
• 用队列实现栈
• 逆波兰表达式求值

「队列」（共有 9 道）

• 数据流中的移动平均值
• 贪吃蛇
• 任务调度器

你还可以搭配 探索队列 & 栈 - 力扣 (LeetCode)探索卡片进行针对性练习～

本文作者：Nova Kwok

声明：本文归 “力扣” 版权所有，如需转载请联系。

,