leetcode【棧與隊列—簡單】 232. 棧實作隊列

文章目錄

• 前言
• 題目
• 題解
• • NO1：雙棧實作隊列
• 參考文章

前言

哈喽，我是長路，目前剛剛大三，方向是後端也偶爾搗鼓下前端，現在的主語言是Java。之前一大段時間都是在學習web開發的一些技術，就很久沒有進行類似于資料結構、算法之類的學習與刷題，打算這段時間拾起來好好學一學、搞一搞。

這段時間也是機緣巧合看到草帽路飛的部落格，加了自學群，正巧看到部落客組織在群裡組織了leetcode刷題打卡活動，我也就參與進來，為期一個月，打算堅持每天都花一些時間做一些題目，并通過部落格的方式來進行記錄。

目前跟着一個Github倉庫刷題(leetcode)：代碼随想錄leetcode刷題，目前為棧與隊列專題。

題目來源leetcode

leetcode位址：232. 用棧實作隊列，難度：簡單。

題目描述(摘自leetcode)：

請你僅使用兩個棧實作先入先出隊列。隊列應當支援一般隊列支援的所有操作（push、pop、peek、empty）：

實作 MyQueue 類：
void push(int x) 将元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并傳回元素
int peek() 傳回隊列開頭的元素
boolean empty() 如果隊列為空，傳回 true ；否則，傳回 false
 
說明：
你隻能使用标準的棧操作 —— 也就是隻有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支援棧。你可以使用 list 或者 deque（雙端隊列）來模拟一個棧，隻要是标準的棧操作即可。
 
進階：
你能否實作每個操作均攤時間複雜度為 O(1) 的隊列？換句話說，執行 n 個操作的總時間複雜度為 O(n) ，即使其中一個操作可能花費較長時間。
 
示例：
輸入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 1, 1, false]

解釋：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
 
提示：
1 <= x <= 9
最多調用 100 次 push、pop、peek 和 empty
假設所有操作都是有效的 （例如，一個空的隊列不會調用 pop 或者 peek 操作）
           

本地調試代碼：

class MyQueue {
	public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        System.out.println(queue.pop());
        queue.push(5);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
    }
}
           

思路： 一個棧用來進行進棧(棧1)，另一個棧用來出棧(棧2)。出棧的時候，先判斷棧2是否為空，為空了統一将棧1中的元素依次出棧進棧2，不為空不進行該操作，避免有些後進的之後被pop出去。

代碼：

class MyQueue {

    private Stack<Integer> stack1;//負責進棧
    private Stack<Integer> stack2;//負責出棧

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        dumpStack1();
        return stack2.pop();
    }

    public int peek() {
        dumpStack1();
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

    public void dumpStack1(){
        //判斷棧2是否為空，空了才會将stack1的元素壓入(避免後進的元素入了棧2)
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
    }
}