「堆棧」作為計算機科學中的一個專有詞語，在許多的面試和考試中會出現，一般在面試的過程中我們讨論的「堆棧」指的是數據結構中的堆棧，此外，計算機操作系統中也有關于堆棧的定義，我們需要明确操作系統中的堆、棧和數據結構堆、棧不是一個概念，它們除了名字一樣沒有什麼必然的聯系，本文主要介紹數據結構中的堆棧，有興趣的同學可以去了解一下操作系統中的堆棧。

堆、棧和隊列

在數據結構中，「堆棧」分别有着以下含義：

• 堆（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

聲明：本文歸 “力扣” 版權所有，如需轉載請聯系。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部