阿竺 ·1. 前言
棧和隊(duì)列相關(guān)的題目是校招中出現(xiàn)頻率一般，但是是屬于相對(duì)基礎(chǔ)的題型。我們要關(guān)注兩類問題，棧和隊(duì)列的添加和刪除操作，以及棧和隊(duì)列之間的區(qū)別和聯(lián)系。
2. 棧和隊(duì)列
2.1 數(shù)據(jù)結(jié)構(gòu)
首先我們給出棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)定義：
（1）棧（Stack）：允許在某一端插入元素（即push操作），以及刪除元素（即pop操作）的數(shù)據(jù)結(jié)構(gòu)，必須滿足后進(jìn)先出（LIFO：Last In First Out）的運(yùn)算規(guī)則。
一個(gè)典型的棧數(shù)據(jù)結(jié)構(gòu)如下圖所示：
（2）隊(duì)列（Queue）：允許在某一端插入元素（即enqueue操作），以及在另一端刪除元素（即dequeue操作）的數(shù)據(jù)結(jié)構(gòu)，必須滿足先進(jìn)先出（FIFO：First In First Out）的運(yùn)算規(guī)則。
一個(gè)典型的隊(duì)列數(shù)據(jù)結(jié)構(gòu)如下圖所示：
2.2 用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
面試官提問：能否用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)？
題目解析：
反轉(zhuǎn)鏈表是來源于算法網(wǎng)站LeetCode的經(jīng)典題目，題目鏈接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/。
本題是一道非常經(jīng)典的面試題，我們不能直接使用語言自帶的Queue實(shí)現(xiàn)類，需要手動(dòng)用兩個(gè)棧來模擬隊(duì)列的操作。
在解題之前，我們需要對(duì)棧和隊(duì)列有個(gè)前置理解，棧支持入棧和出棧操作，隊(duì)列支持入隊(duì)和出隊(duì)操作。并且從題目看，隊(duì)列還需要實(shí)現(xiàn)peek函數(shù)（返回隊(duì)列的頭部元素）和empty函數(shù)（判斷隊(duì)列是否為空）。舉例來說，我們假設(shè)實(shí)現(xiàn)的隊(duì)列類名是MockQueue，基礎(chǔ)的操作案例示例：
MockQueue queue = new MockQueue();
queue.push(100); //將100放入隊(duì)列
queue.push(200); //將200放入隊(duì)列
queue.empty(); //判斷隊(duì)列是否為空，return false
queue.pop(); //彈出隊(duì)列的一個(gè)元素
queue.peek(); //返回隊(duì)列的頭部元素，return 100
我們用 stack1、stack2 來表示兩個(gè)棧，還是以小規(guī)模數(shù)據(jù)作為案例開始分析，對(duì)于一個(gè)數(shù)組[1,2,3,4]，我們將其存放到第一個(gè)棧stack1中，那么出棧的順序是[4,3,2,1]，明顯不滿足隊(duì)列的要求。入棧和出棧的操作是將數(shù)組逆序排列了一遍，從幾何的角度可以看成旋轉(zhuǎn)了180度，如果連續(xù)兩次旋轉(zhuǎn)180度，那么數(shù)組就會(huì)回到原點(diǎn)，分析到這里解法就呼之欲出了。
從分工上看，stack1 負(fù)責(zé) push，stack2 負(fù)責(zé) pop。
（1）入隊(duì)的操作：我們直接把值放到 stack1；
（2）出隊(duì)的操作：首先判斷 stack2 是否為空，如果為空就把 stack1 中的元素全部壓入 stack2，最后彈出 stack2 的棧頂元素；
（3）返回隊(duì)列頭部元素的操作：peek 操作和 pop 操作類似，區(qū)別在于不會(huì)彈出 stack2 的棧頂元素；
（4）判斷隊(duì)列是否為空的操作：直接判斷 stack1 和 stack2 是否同時(shí)為空就行。
下面給出Java源碼的實(shí)現(xiàn)，示例：
class MockQueue {
//首先我們需要定義兩個(gè)Stack數(shù)據(jù)結(jié)構(gòu)
Stack<Integer> s1;
Stack<Integer> s2;
public MockQueue() {
// 初始化對(duì)象
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
//入隊(duì)操作
s1.push(x);
}
public int pop() {
//出隊(duì)操作
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
//從隊(duì)列頭部獲取元素
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
//判斷隊(duì)列是否為空
return s1.isEmpty() && s2.isEmpty();
}
}
3. 小結(jié)
本章節(jié)我們介紹了最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，棧和隊(duì)列，其中棧在動(dòng)態(tài)規(guī)劃以及二叉樹問題中也經(jīng)常出現(xiàn)。在使用棧和隊(duì)列解決算法問題時(shí)，需要特別注意容器為空的情況，防止拋出異常。這類邊界問題的判斷，在其他算法問題中也是注意點(diǎn)，例如二叉樹首先要判斷 root 是否為空，防止空指針訪問異常。
2025 imooc.com All Rights Reserved |