用兩個棧實現隊列

• 2022 年 1 月 6 日
• 筆記
• LeetCode刷題

用兩個棧實現隊列

題目鏈接

牛客網

題目描述

描述

用兩個棧來實現一個隊列，使用n個元素來完成 n 次在隊列尾部插入整數(push)和n次在隊列頭部刪除整數(pop)的功能。 隊列中的元素為int類型。保證操作合法，即保證pop操作時隊列內已有元素。

數據範圍： n≤1000

要求：存儲n個元素的空間複雜度為 O(n) ，插入與刪除的時間複雜度都是 O(1)

示例

輸入：

[“PSH1″,”PSH2″,”POP”,”POP”]

返回值：

1,2

說明：

“PSH1”:代表將1插入隊列尾部
“PSH2”:代表將2插入隊列尾部
“POP「:代表刪除一個元素，先進先出=>返回1
“POP「:代表刪除一個元素，先進先出=>返回2

示例2

輸入：

[“PSH2″,”POP”,”PSH1″,”POP”]

返回值：

2,1

解題思路

藉助棧的先進後出規則模擬實現隊列的先進先出

1、當插入時，直接插入 stack1

2、當彈出時，當 stack2 不為空，彈出 stack2 棧頂元素，如果 stack2 為空，將 stack1 中的全部數逐個出棧入棧 stack2，再彈出 stack2 棧頂元素

程式碼

package com.huang.datastructure;

import java.util.Stack;

/**
 * @Author hxc
 * @Date 2022/1/6
 */
public class DoubleStackToQueue {
    /**
     * 用兩個棧來實現隊列
     */
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

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

    public int pop() throws Exception {
        //第二個棧要是空的
        if(stack2.isEmpty()) {
            while (!stack1.isEmpty()){
                //把第一個棧中的數字取出來放進第二個棧中，這樣數就相反了
                stack2.push(stack1.pop());
            }
        }
        if(stack2.isEmpty()) {
            throw new Exception("queue is Empty");
        }
        //輸出棧
        return stack2.pop();
    }

    public static void main(String[] args) throws Exception {
        DoubleStackToQueue queue = new DoubleStackToQueue();
        queue.push(1);
        System.out.println(queue.pop());
        queue.push(2);
        System.out.println(queue.pop());

    }
}