第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

1. 前言

棧和隊列相關(guān)的題目是校招中出現(xiàn)頻率一般，但是是屬于相對基礎(chǔ)的題型。我們要關(guān)注兩類問題，棧和隊列的添加和刪除操作，以及棧和隊列之間的區(qū)別和聯(lián)系。

2. 棧和隊列

2.1 數(shù)據(jù)結(jié)構(gòu)

首先我們給出棧和隊列的數(shù)據(jù)結(jié)構(gòu)定義：

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

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

2.2 用兩個棧實現(xiàn)一個隊列

面試官提問：能否用兩個棧實現(xiàn)一個隊列的數(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實現(xiàn)類，需要手動用兩個棧來模擬隊列的操作。

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

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

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

從分工上看，stack1 負責(zé) push，stack2 負責(zé) pop。

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

下面給出Java源碼的實現(xiàn)，示例：

class MockQueue {
    //首先我們需要定義兩個Stack數(shù)據(jù)結(jié)構(gòu)
    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. 小結(jié)

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