用兩個棧實作隊列

題目連結

牛客網

題目描述

描述

用兩個棧來實作一個隊列，使用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());

    }
}