51工具盒子- 用两个栈实现一个队列 {#1-用两个栈实现一个队列} =============================
根据栈的特性，通过一个栈来实现一个队列的行为是做不到的，所以可以再加一个。用两个栈实现一个队列，可以利用栈的后进先出（LIFO）性质，将栈的顺序反转，从而实现队列的先进先出（FIFO）行为。
具体实现方法如下：
-
定义两个栈：
stack1：用于入队操作。stack2：用于出队操作
-
入队操作（enqueue） ：将新元素压入
stack1。 -
出队操作（dequeue）：
-
如果
stack2为空，将stack1中的所有元素弹出并压入stack2。 -
弹出
stack2的栈顶元素作为出队元素。
-
-
访问队头（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）行为。
具体实现方法如下：
- 定义两个队列 ：
queue1：用于存储元素。queue2：辅助队列，用于倒转queue1中的顺序。
- 入栈操作（push） ：
- 将新元素加入
queue2。 - 将
queue1中的所有元素依次移到queue2。 - 交换
queue1和queue2。
- 将新元素加入
- 出栈操作（pop） ：从
queue1中弹出队头元素。 - 访问栈顶（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; } |
