[スタックとキュー]2つのスタックでキューを実装

1171 ワード

2つのスタックで1つのキューを実現し、キューのPushとPop操作を完了します.キュー内の要素はintタイプです.
Stack 1を固定してスタックを圧着するStack 2を使用してスタックを圧着する場合、直接Stack 1に圧入し、スタックを弾いた場合、Stack 2が空であれば、Stack 1をすべて圧入する.すなわち、スタック反転後のキューがStack 2が空でなければ、一部の前順キューがスタックを弾き終わっていないことを示し、スタックを弾き続ける
シミュレーションシーン(スタックの上部が右)
操作
Stack1
Stack2
A,B,C入桟
A,B,C
弾桟1回
(弾桟前)
C,B,A
弾桟1回
(弾倉開始)
C,B
Dインスタック
D
C,B
弾桟1回
D
C
E,Fインスタック
D,E,F
C
弾桟1回
D,E,F
弾桟1回
(弾桟前)
F,E,D
弾桟1回
(弾倉開始)
F,E
時間複雑度スタックO(1)弾スタックO(n)具体的な実現:
import java.util.Stack;

public class Solution {
    Stack stack1 = new Stack();
    Stack stack2 = new Stack();
    
    public void push(int node) {
        //    
        stack1.push(node);
        return;
    }
    
    public int pop() {
        //      ,  
        if(stack2.empty()){
            //stack1       stack2     
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        //   (   )  
        return stack2.pop().intValue();
    }
}