亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

阿竺 · 更新于 2021-07-15

1. 前言

棧和隊列相關的題目是校招中出現頻率一般，但是是屬于相對基礎的題型。我們要關注兩類問題，棧和隊列的添加和刪除操作，以及棧和隊列之間的區別和聯系。

2. 棧和隊列

2.1 數據結構

首先我們給出棧和隊列的數據結構定義：

（1）棧（Stack）：允許在某一端插入元素（即push操作），以及刪除元素（即pop操作）的數據結構，必須滿足后進先出（LIFO：Last In First Out）的運算規則。
一個典型的棧數據結構如下圖所示：

圖片描述

棧結構

（2）隊列（Queue）：允許在某一端插入元素（即enqueue操作），以及在另一端刪除元素（即dequeue操作）的數據結構，必須滿足先進先出（FIFO：First In First Out）的運算規則。
一個典型的隊列數據結構如下圖所示：

圖片描述

隊列結構

2.2 用兩個棧實現一個隊列

面試官提問：能否用兩個棧實現一個隊列的數據結構？

題目解析：

反轉鏈表是來源于算法網站LeetCode的經典題目，題目鏈接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/。

本題是一道非常經典的面試題，我們不能直接使用語言自帶的Queue實現類，需要手動用兩個棧來模擬隊列的操作。

在解題之前，我們需要對棧和隊列有個前置理解，棧支持入棧和出棧操作，隊列支持入隊和出隊操作。并且從題目看，隊列還需要實現peek函數（返回隊列的頭部元素）和empty函數（判斷隊列是否為空）。舉例來說，我們假設實現的隊列類名是MockQueue，基礎的操作案例示例：

MockQueue queue = new MockQueue();
queue.push(100);  //將100放入隊列
queue.push(200);  //將200放入隊列
queue.empty();    //判斷隊列是否為空，return false
queue.pop();      //彈出隊列的一個元素
queue.peek();     //返回隊列的頭部元素，return 100

我們用 stack1、stack2 來表示兩個棧，還是以小規模數據作為案例開始分析，對于一個數組[1,2,3,4]，我們將其存放到第一個棧stack1中，那么出棧的順序是[4,3,2,1]，明顯不滿足隊列的要求。入棧和出棧的操作是將數組逆序排列了一遍，從幾何的角度可以看成旋轉了180度，如果連續兩次旋轉180度，那么數組就會回到原點，分析到這里解法就呼之欲出了。

從分工上看，stack1 負責 push，stack2 負責 pop。

（1）入隊的操作：我們直接把值放到 stack1；
（2）出隊的操作：首先判斷 stack2 是否為空，如果為空就把 stack1 中的元素全部壓入 stack2，最后彈出 stack2 的棧頂元素；
（3）返回隊列頭部元素的操作：peek 操作和 pop 操作類似，區別在于不會彈出 stack2 的棧頂元素；
（4）判斷隊列是否為空的操作：直接判斷 stack1 和 stack2 是否同時為空就行。

下面給出Java源碼的實現，示例：

class MockQueue {
    //首先我們需要定義兩個Stack數據結構
    Stack<Integer> s1;
    Stack<Integer> s2;

    public MockQueue() {
        // 初始化對象
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    public void push(int x) {
        //入隊操作
        s1.push(x);
    }
    
    public int pop() {
        //出隊操作
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
        //從隊列頭部獲取元素
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        //判斷隊列是否為空
        return s1.isEmpty() && s2.isEmpty();
    }
}

3. 小結

本章節我們介紹了最基礎的數據結構，棧和隊列，其中棧在動態規劃以及二叉樹問題中也經常出現。在使用棧和隊列解決算法問題時，需要特別注意容器為空的情況，防止拋出異常。這類邊界問題的判斷，在其他算法問題中也是注意點，例如二叉樹首先要判斷 root 是否為空，防止空指針訪問異常。