两个栈组成队列

Posted on | In |

【题目】

编写一个类，用两个栈实现队列的基本操作：add、poll、peek

【解法】

一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush。另一个栈只作为单出栈，在弹出数据时只从这个栈弹出，记为stackPop。
stackPop会将stackPush中的数据整体弹出再压入stackPop作为弹出顺序。
需要做到以下两点：

  1. 如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入
  2. 如果stackPop不为空，stackPush绝对不能向stackPop中压入数据

【代码】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class TwoStackQueue {
    public Stack<Integer> stackPush;
    public Stack<Integer> stackPop;
    public TwoStackQueue() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }
    public void add(int pushInt) {
        stackPush.push(pushInt);
    }
    public int poll() {
        putPushToPop();
        return stackPop.pop();
    }
    public int peek() {
        putPushToPop();
        return stackPop.peek();
    }
    
    public void putPushToPop() {
        if(stackPop.empty() && stackPush.empty()) {
            throw new RuntimeException("Queue is empty");
        }else if(stackPop.empty()) {
            stackPush.stream().forEach(item -> {
                stackPop.push(item);
            });
        }
    }
}