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

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

具体实现方法如下:

  1. 定义两个栈

    • stack1:用于入队操作。
    • stack2:用于出队操作
  2. 入队操作(enqueue):将新元素压入 stack1

  3. 出队操作(dequeue)

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

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

  4. 访问队头(front):元素的操作和出队列相似,只是不需要弹出元素。

下图模拟了数据在两个栈(自定义队列)中的移动过程:

image-20240630184629868

通过上面的描述,可以写出如下的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
    • 交换 queue1queue2
  3. 出栈操作(pop):从 queue1 中弹出队头元素。
  4. 访问栈顶(top):访问 queue1 中的队头元素。

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

image-20240630180940029

通过上面的文字描述,我们可以写成如下的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;
}