栈和队列的转换

1. 用两个栈实现一个队列

根据栈的特性，通过一个栈来实现一个队列的行为是做不到的，所以可以再加一个。用两个栈实现一个队列，可以利用栈的后进先出（LIFO）性质，将栈的顺序反转，从而实现队列的先进先出（FIFO）行为。

具体实现方法如下：

  1. 定义两个栈：

    • stack1：用于入队操作。
    • stack2：用于出队操作

  2. 入队操作（enqueue）：将新元素压入 stack1。

  3. 出队操作（dequeue）：

    • 如果 stack2 为空，将 stack1 中的所有元素弹出并压入 stack2。

    • 弹出 stack2 的栈顶元素作为出队元素。

  4. 访问队头（front）：元素的操作和出队列相似，只是不需要弹出元素。

下图模拟了数据在两个栈（自定义队列）中的移动过程：

通过上面的描述，可以写出如下的C++代码：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <stack>
using namespace std;

class QueueUsingStacks
{
public:
    void enqueue(int value)
    {
        m_st1.push(value);
    }

    int dequeue()
    {
        if (m_st2.empty())
        {
            if (m_st1.empty())
            {
                throw std::out_of_range("空队列");
            }
            moveStack1ToStack2();
        }
        int topValue = m_st2.top();
        m_st2.pop();
        return topValue;
    }

    int front()
    {
        if (m_st2.empty())
        {
            if (m_st1.empty())
            {
                throw std::out_of_range("空队列");
            }
            moveStack1ToStack2();
        }
        return m_st2.top();
    }

    bool isEmpty() const
    {
        return m_st1.empty() && m_st2.empty();
    }
private:
    void moveStack1ToStack2()
    {
        while (!m_st1.empty())
        {
            m_st2.push(m_st1.top());
            m_st1.pop();
        }
    }

    stack<int> m_st1;
    stack<int> m_st2;
};

int main()
{
    QueueUsingStacks queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    cout << "Front: " << queue.front() << endl;     // 输出 1
    cout << "Dequeue: " << queue.dequeue() << endl; // 输出 1
    queue.enqueue(4);
    cout << "Front: " << queue.front() << endl;     // 输出 2
    cout << "Dequeue: " << queue.dequeue() << endl; // 输出 2
    cout << "Dequeue: " << queue.dequeue() << endl; // 输出 3
    cout << "Dequeue: " << queue.dequeue() << endl; // 输出 4

    return 0;
}

2. 用两个队列实现一个栈

既然使用两个栈可以实现一个队列，同样通过两个队列也可以实现一个栈，主要思路是利用队列的先进先出（FIFO）性质，将队列中的数据顺序反转，从而实现栈的后进先出（LIFO）行为。

具体实现方法如下：

  1. 定义两个队列：
    • queue1：用于存储元素。
    • queue2：辅助队列，用于倒转 queue1 中的顺序。
  2. 入栈操作（push）：
    • 将新元素加入 queue2。
    • 将 queue1 中的所有元素依次移到 queue2。
    • 交换 queue1 和 queue2。
  3. 出栈操作（pop）：从 queue1 中弹出队头元素。
  4. 访问栈顶（top）：访问 queue1 中的队头元素。

下图为大家演示的是队列中添加数字4和数字5的过程：

通过上面的文字描述，我们可以写成如下的C++代码：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <queue>
using namespace std;

class StackUsingQueues 
{
public:
    void push(int value) 
    {
        m_q2.push(value);
        while (!m_q1.empty()) 
        {
            m_q2.push(m_q1.front());
            m_q1.pop();
        }
        std::swap(m_q1, m_q2);
    }

    int pop() 
    {
        if (m_q1.empty()) 
        {
            throw std::out_of_range("Stack is empty");
        }
        int topValue = m_q1.front();
        m_q1.pop();
        return topValue;
    }

    int top() const 
    {
        if (m_q1.empty()) 
        {
            throw std::out_of_range("Stack is empty");
        }
        return m_q1.front();
    }

    bool isEmpty() const 
    {
        return m_q1.empty();
    }
private:
    queue<int> m_q1;
    queue<int> m_q2;
};

int main() 
{
    StackUsingQueues stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);

    cout << "Top: " << stack.top() << endl; // 输出 3
    cout << "Pop: " << stack.pop() << endl; // 输出 3
    cout << "Pop: " << stack.pop() << endl; // 输出 2
    stack.push(4);
    cout << "Pop: " << stack.pop() << endl; // 输出 4
    cout << "Pop: " << stack.pop() << endl; // 输出 1

    return 0;
}