一、用队列实现栈 (Stack via Queues)

栈是一种后进先出（LIFO）​的数据结构。要使用队列（先进先出，FIFO）来模拟栈，核心在于如何利用队列的操作让最后入队的元素能够最先出队。主要有两种方法：双队列法和单队列法。

双队列法：

这种方法使用两个队列，通常称为 q1（主队列）和 q2（辅助队列）

。

#include<iostream>
#include<string>
#include<algorithm>
#include<stdexcept>
#include<stack>
using namespace std;
class MyStack
{
private:
    Queue<int> q1; // 主队列，通常用于存储栈中的所有元素
    Queue<int> q2; // 辅助队列，用于在pop和top操作时临时存放元素

public:
    // 将元素 x 压入栈顶
    void push(int x)
    {
        q1.enqueue(x); // 新元素直接进入主队列q1的尾部
        // 注意：此时新元素位于q1的尾部，而栈顶元素应该是最后加入的元素，
        // 但队列是FIFO，所以需要通过后续的pop和top操作来调整访问顺序
    }

    // 移除并返回栈顶元素（最后入队的元素）
    int pop() {
        // 将q1中除最后一个元素外的所有元素转移到q2
        while (q1.getsize() > 1) // 循环直到q1只剩一个元素（即栈顶元素）
        {
            q2.enqueue(q1.dequeue()); // 将q1队首元素出队并加入q2队尾
        }
        // 此时q1中剩下的最后一个元素就是最后进入队列的元素（即栈顶元素）
        int result = q1.dequeue(); // 移除并获取该栈顶元素

        // 将q2中的所有元素转移回q1，恢复q1存储所有剩余元素的状态
        while (!q2.empty())
        {
            q1.enqueue(q2.dequeue()); // 将q2队首元素出队并加入q1队尾
        }
        return result; // 返回被移除的栈顶元素
    }

    // 返回栈顶元素但不移除
    int top() {
        // 将q1中除最后一个元素外的所有元素转移到q2
        while (q1.getsize() > 1) // 循环直到q1只剩一个元素（即栈顶元素）
        {
            q2.enqueue(q1.dequeue()); // 将q1队首元素出队并加入q2队尾
        }
        // 获取q1的最后一个元素（栈顶元素）
        int result = q1.dequeue(); // 取出栈顶元素
        q1.enqueue(result); // 因为只是获取而非移除，所以需要将其重新放回q1

        // 将q2中的所有元素转移回q1
        while (!q2.empty())
        {
            q1.enqueue(q2.dequeue()); // 将q2队首元素出队并加入q1队尾
        }
        return result; // 返回栈顶元素的值
    }

    // 检查栈是否为空
    bool empty() {
        return q1.empty(); // 因为所有元素都存储在q1中，只需检查q1是否为空
    }
};
int main()
{
	MyStack s;
	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);
	cout << s.top() << endl;
	s.pop();
	cout << s.top() << endl;
	cout << s.empty() << endl;
	return 0;
}

• ​**push(x) - 入栈操作**​：

  • 先将新元素 x 入队到辅助队列 q2。
  • 然后将主队列 q1 中的所有元素依次出队并入队到 q2。此举确保了新元素位于 q2 的队首​（即栈顶）。
  • 最后，交换 q1 和 q2 的角色，使得 q1 始终是包含所有元素的主队列，q2 再次变为空队列以备下次使用。
  • ​时间复杂度​：O(n)，因为需要转移 q1 中的所有元素。

• ​**pop() - 出栈操作**​：

  • 由于在每次 push 操作后，q1 的队首元素就是栈顶元素，因此直接让 q1 出队即可。
  • ​时间复杂度​：O(1)。

• ​**top() - 获取栈顶元素**​：

  • 与 pop 操作类似，直接返回 q1 的队首元素但不移除。
  • ​时间复杂度​：O(1)。

• ​**empty() - 检查栈是否为空**​：

  • 检查主队列 q1 是否为空即可。
  • ​时间复杂度​：O(1)。

​💡 提示​：这种方法通过确保每次入栈操作后主队列 q1 的队首都是最新元素，使得 pop 和 top 操作变得非常简单直接，但 push 操作的成本较高

双队列法与单队列法对比

​选择建议​：如果 push 操作非常频繁，单队列法可能更合适。如果 pop 和 top 操作非常频繁，双队列法可能更合适。

 二、用栈实现队列 (Queue via Stacks)

#include<iostream>
#include<string>
#include<algorithm>
#include<stdexcept>
#include<stack>
using namespace std;

class MyQueue
{
private:
	Stack<int>s1;
	Stack<int>s2;

public:
	void push(int x)
	{
		s1.push(x);
	}
	int pop()
	{
		if (s2.empty()) {//如果 outStack 为空，则将 inStack 中的所有元素依次弹出并压入 outStack。

			while (!s1.empty())//此操作将元素的顺序反转，使得最先进入 inStack 的元素位于 outStack 的栈顶。
//弹出并返回 outStack 的栈顶元素。
			{
				s2.push(s1.pop());
			}
		}
		return  s2.pop();
	}
	int peek()//获取栈顶与弹栈的逻辑一样只是不用删除元素直接获取就行了
	{
		if (s2.empty()) {
			while (!s1.empty())
			{
				s2.push(s1.pop());
			}
		}
		return  s2.top();
	}
	bool empty()
	{
		return s1.empty() && s2.empty();//同时为空即空
	}


};
int main()//运行例子
{
	MyQueue q1;
	q1.push(5);
	q1.push(6);
	q1.push(7);
	cout << q1.pop() << endl;
	cout << q1.peek() << endl;
	return 0;
}

队列是一种先进先出（FIFO）​的数据结构。使用栈（后进先出，LIFO）来实现队列，最经典和高效的方法是双栈法​

这种方法使用两个栈：一个作为输入栈​ (inStack)，专用于处理入队（push）操作；另一个作为输出栈​ (outStack)，专用于处理出队（pop）和查看队首（peek）操作。

• ​**push(x) - 入队操作**​：

  • 新元素直接压入 inStack。
  • ​时间复杂度​：O(1)。

• ​**pop() - 出队操作**​：

  • 如果 outStack 为空，则将 inStack 中的所有元素依次弹出并压入 outStack。此操作将元素的顺序反转，使得最先进入 inStack 的元素位于 outStack 的栈顶。
  • 弹出并返回 outStack 的栈顶元素。
  • ​时间复杂度​：​均摊 O(1)​。最坏情况下（当 outStack 为空时）一次操作是 O(n)，但每个元素最多只会从 inStack 转移到 outStack 一次，因此多次 pop 操作的平均时间复杂度是很低的。

• ​**peek() - 获取队首元素**​：

  • 逻辑与 pop 操作类似。如果 outStack 为空，则需要先将 inStack 的所有元素转移到 outStack。
  • 然后返回 outStack 的栈顶元素（但不弹出）。
  • ​时间复杂度​：均摊 O(1)。

• ​**empty() - 检查队列是否为空**​：

  • 检查 inStack 和 outStack 是否都为空。
  • ​时间复杂度​：O(1)。

​ 提示​：双栈法是实现队列的高效方法。关键在于惰性转移元素——只有在 outStack 为空且需要执行 pop 或 peek 操作时，才将 inStack 的元素倒入 outStack。这样确保了每个元素只被转移一次，使得 pop 和 peek 操作的均摊时间复杂度为 O(1)

。

 三、关键总结与注意事项

1. ​思维转换​：这类问题的核心在于理解如何利用基本数据结构（队列的FIFO或栈的LIFO）并通过组合操作来模拟另一种数据结构的特性。​队列实现栈的关键是反转元素的顺序；栈实现队列的关键也是反转元素的顺序​（通过第二个栈）。
2. ​时间复杂度分析​：关注均摊时间复杂度​（Amortized Time Complexity），特别是在用栈实现队列的 pop 操作中。不要因为一次昂贵的操作而认为整个算法效率低下。
3. ​实际应用​：这些问题主要是为了考察对数据结构的理解，其教学意义大于工程实践意义​。在实际项目开发中，应直接使用编程语言提供的标准栈或队列实现。
4. ​代码实现注意​：
   • 务必注意边界条件的判断，例如在 pop 或 top/peek 操作前检查栈或队列是否为空。
   • 在用队列实现栈时，如果使用双队列法，注意在交换队列引用时不要出错。
   • 在用栈实现队列时，确保只有在 outStack 为空时才进行转移操作，避免不必要的操作。