代码随想录训练营第10天|LeetCode ：232.用栈实现队列、225.用队列实现栈

参考

代码随想录

题目一：LeetCode 232：用栈实现队列

用栈实现队列的原理如下：

需要用到两个栈stack1和stack2，例如图中一个输入序列为1，2，3，4，这个输入序列先存入stack1中，然后再从stack1中全部弹出存入stack2中，若要读取数据，就从stack2中弹出数据，这样就实现了先入先出。如果输入输出是穿插着的，每次输入数据就先存放在stack1中，每次输出从stack2中弹出数据，若stack2为空，则从将stack1中的所有数据弹出放入到stack2中，然后再从stack2中弹出数据。代码实现如下：

class MyQueue {
public:
    MyQueue() {
    }
    
    void push(int x) {
        stack1.push(x);
    }
    
    int pop() {
        int ret = peek();
        stack2.pop();
        return ret;
    }
    
    int peek() {
        int ret;
        if(!stack2.empty())
            ret = stack2.top();
        else
        {
            while(!stack1.empty())
            {
                int val = stack1.top();
                stack1.pop();
                stack2.push(val);
            }
            ret = stack2.top();
        }
        return ret;
    }
    
    bool empty() {
        return stack1.empty() && stack2.empty();
    }
private:
    stack<int> stack1,stack2;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
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
43
44
45
46
47

其中相对复杂一些的是peek()函数，要先判断stack2中是否有数据，若有直接读出数据，否则将stack1中的全部数据弹出放入stack2中，再从stack中弹出数据。

题目二：LeetCode 225：用队列实现栈

用队列实现栈的原理如下：（假设输入序列为1，2，3）
第一步，将数据读入第一个队列中：

第二步，将第一个队列中除最后一个以外的其他数据读出放入第二个队列中：

第三步，读出第一个队列中的数据，该数据就是栈弹出的数据，然后将第二个队列中的数据移回第一个队列中：

每次压栈就把数据放入到第一个队列中即可。
代码实现如下：

class MyStack {
public:
    MyStack() {
    }
    
    void push(int x) {
        queue1.push(x);
    }
    
    int pop() {
        int cnt = queue1.size() - 1;
        while(cnt--)   queue2.push(queue1.front()),queue1.pop();
        int ret = queue1.front();
        queue1.pop();
        cnt = queue2.size();
        while(cnt--)    queue1.push(queue2.front()),queue2.pop();
        return ret;
    }
    
    int top() {
        int ret = pop();
        queue1.push(ret);
        return ret;
    }
    
    bool empty() {
        return queue1.empty() && queue2.empty();
    }
private:
    queue<int> queue1,queue2;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
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

上面实现过程中，第二个队列的作用仅仅是临时存储数据，当然其实也可以将这些数据添加到第一个队列的末尾，这样就不需要第二个队列了。只使用一个队列的实现方法是：假设队列中有n个数据，则将前n-1个数据读出并添加到队列末尾，然后队首的数据就是下一个要弹出的数据。代码实现如下：

class MyStack {
public:
    MyStack() {
    }
    
    void push(int x) {
        que.push(x);
    }
    
    int pop() {
        int cnt = que.size() - 1;
        while(cnt--)    que.push(que.front()),que.pop();
        int ret = que.front();
        que.pop();
        return ret;
    }
    
    int top() {
        int ret = pop();
        que.push(ret);
        return ret;
    }
    
    bool empty() {
        return que.empty();
    }
private:
    queue<int> que;
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */
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

小结

今天的题不难，没有涉及什么算法，只是栈和队列基础知识的简单应用。在使用stack和queue的时候需要注意top()函数和pop()函数，以及front()函数和pop()函数的区别。