劍指offer - 用兩個棧實作隊列

7.用兩個棧實作隊列

題目描述

用兩個棧來實作一個隊列，完成隊列的Push和Pop操作。 隊列中的元素為int類型。

• 思路：
  • 通過兩個棧中元素之間的複制交換實作了隊列，棧一負責接收節點資料
  • 棧二負責彈出資料，由棧的特性可知棧彈出的資料即為棧一中順序輸入的順序
• 複雜度
  • push時間複雜度：O(1)
  • pop空間複雜度：O(1)

import java.util.Stack;

public class Title5 {
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    public void push (int node){
        stack1.push(node);//棧一負責接收節點資料
    }
    public int pop(){
        if (stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());//棧二負責彈出資料，由棧的特性可知棧彈出的資料即為棧一中順序輸入的順序
            }
        }
        return stack2.pop();
    }
}