leetcode 232

问题

Implement the following operations of a queue using stacks.

  • push(x) – Push element x to the back of queue.
  • pop() – Removes the element from in front of queue.
  • peek() – Get the front element.
  • empty() – Return whether the queue is empty.

Example:

1
2
3
4
5
6
7
MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

  • You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

分析

使用两个栈A和B模拟队列。

入队：将元素进栈A。

出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；如果不为空，栈B直接出栈。

入队时间复杂度O(1)，出队时间复杂度O(1)(摊还时间复杂度)

出队时单次的最坏时间复杂度是O(n)，但是摊还到每一次来看，平均的出队时间复杂度就是O(1).

代码

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
34
35
36
37
38
39
40
41
42
class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> a;
    stack<int> b;
    MyQueue() {
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        a.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (b.size() == 0) {
            while (a.size() != 0) {
                b.push(a.top());
                a.pop();
            }
        }
        int x = b.top();
        b.pop();
        return x;
    }
    
    /** Get the front element. */
    int peek() {
        if (b.size() == 0) {
            while (a.size() != 0) {
                b.push(a.top());
                a.pop();
            }
        }
        return b.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return a.size()==0 && b.size()==0;
    }
};