力扣225题 解题思路和步骤 C++实现带注释,谭浩强c语言程序设计第五版答案

一、题目理解

力扣225题要求实现一个栈，该栈使用队列来进行模拟。栈是一种后进先出（LIFO）的数据结构，而队列是先进先出（FIFO）的数据结构。因此，我们需要通过两个队列来模拟栈的行为。

二、解题思路

要使用两个队列来模拟栈，我们可以采取以下策略：将所有元素插入到一个队列中，当需要弹出元素时，将这个队列中的所有元素（除了一个）移动到另一个队列中，一个元素即为栈顶元素，可以进行弹出操作。交换两个队列的角色，重复上述过程。

三、C++实现

class MyStack { 
    public: queue q1, q2; // 使用两个队列q1和q2来模拟栈 
    MyStack() {} // 构造函数
}; 

void push(int x) { 
    q1.push(x); // 将元素x插入到队列q1中 
} 
int pop() { 
    int size = q1.size(); // 获取队列q1的元素个数 
    for (int i = 0; i < size - 1; i++) { 
        q2.push(q1.front()); // 将q1中的元素（除了一个）移动到q2 
        q1.pop(); // 移除q1的队首元素 
    } 
    int result = q1.front(); // 一个元素是栈顶元素 
    q1.pop(); // 移除栈顶元素 
    swap(q1, q2); // 交换两个队列，以便下一次操作 
    return result; // 返回栈顶元素 
}

四、案例说明

当我们执行以下操作：`push(1)`, `push(2)`, `push(3)`，执行`pop()`，输出将是3，因为3是最先插入的元素，符合栈的后进先出特性。