232. 用栈实现队列

1.题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

2.示例

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
1
2
3
4
5
6
7
8
9
10
11
12
13

3.答案

栈先进后出，队列先进先出。 需要使用两个栈实现队列的push和pop。设置输入栈，输出栈，push时元素就进入输入栈，每次pop或者peek的时候如果输出栈有内容就先输出输出栈的内容（这些都是最早进入的元素），如果输出栈为空，将输入栈元素全部转入输出栈。当两个栈均为空则队列为空。

class MyQueue {
public:
    stack<int> s1;  //输入栈
    stack<int> s2;  //输出栈
    MyQueue() {
    
    }
    
    void push(int x) {
       s1.push(x);   //元素进栈
    }
    
    int pop() {
    if(s2.empty()){  //此时输出栈为空，将输入栈全部内容转移
        while(!s1.empty()){
            int a=s1.top();
            s1.pop();
            s2.push(a);
        }
        }
        int a=s2.top();
        s2.pop();
        return a;
    }
    
    int peek() {
       if(s2.empty()){  //此时输出栈为空，将输入栈全部内容转移
        while(!s1.empty()){
            int a=s1.top();
            s1.pop();
            s2.push(a);
        }
        }
        return s2.top();
    }
    
    bool empty() {
        if(s1.empty()&&s2.empty()) return true;
        return false;
    }
};

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-queue-using-stacks