数据结构与算法学习笔记（8）——队列、栈

发表于   |   分类于   |  

本章来介绍栈和队列中经常遇到的问题。

本文仅供个人记录和复习，不用于其他用途

用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

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
class Solution
{
public:
    void push(int node)
    {
        stack1.push(node);
    }
    int pop()
    {
        int temp;
        if (stack2.empty())
        {
            while (!stack1.empty())
            {
                temp = stack1.top();
                stack2.push(temp);
                stack1.pop();
            }
        }
        temp = stack2.top();
        stack2.pop();
        
        return temp;
    }
private:
    stack<int> stack1;
    stack<int> stack2;
};

stack1用于入队，stack2用于出队。我们知道队列是先进先出，如果要入队的话，直接就将元素加入stack1即可。出队时我们首先要判断stack2是否为空，不为空就直接出栈，为空就需要我们将stack1的所有元素弹出，并且全部加入到stack2中，然后只需要弹出stack2的栈顶即可。

当然，如果需要使用两个队列实现一个栈也很简单，入栈就将元素加入队列1，出栈首先判断队列A中的元素个数是否为1，等于1就出队列，否则将队列1的元素放入队列2，一直到队列1只剩1个元素，然后将这个元素出队，再把队列2的元素放入到队列1。由于栈是先进后出，所以只能够先将队列中的元素先全部出队，获取最后一个元素。