用两个栈来实现一个队列,使用 个元素来完成 次在队列尾部插入整数push)和 次在队列头部删除整数(pop)的功能。 队列中的元素为 int 类型。保证操作合法,即保证 pop 操作时队列内已有元素。
时间: 2024-05-25 17:15:17 浏览: 114
用两个栈实现一个队列的功能
好的,这是一道经典的数据结构题,可以使用两个栈来实现。具体实现步骤如下:
1. 定义两个栈 stack1 和 stack2 ,其中 stack1 用于插入元素,stack2 用于删除元素。
2. 在插入元素时,直接将元素 push 到 stack1 中。
3. 在删除元素时,首先判断 stack2 是否为空。如果不为空,直接从 stack2 中 pop 出栈顶元素即可;如果为空,则将 stack1 中的所有元素依次 pop 并 push 到 stack2 中,最后再从 stack2 中 pop 出栈顶元素。
4. 注意要保证 pop 操作时队列内已有元素,否则会出现错误。
下面是代码实现:
class MyQueue {
private:
stack<int> stack1;
stack<int> stack2;
public:
MyQueue() {}
void push(int x) {
stack1.push(x);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
int result = stack2.top();
stack2.pop();
return result;
}
};
阅读全文