[スタックとキュー]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)具体的な実現:
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();
}
}