用两个栈来实现一个队列,使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。 数据范围: n≤1000
时间: 2024-05-25 16:19:19 浏览: 8
好的,这是一个经典的算法问题。我们可以使用两个栈来实现一个队列。具体实现方法如下:
首先定义两个栈,一个用来存储入队列的元素,一个用来存储出队列的元素。
当需要插入元素时,将元素压入入队列的栈中。
当需要弹出元素时,如果出队列的栈为空,则将入队列的栈中的所有元素出栈并压入出队列的栈中,然后再从出队列的栈中弹出一个元素,作为队列的头元素。
下面是代码实现:
class MyQueue {
public:
stack<int> instack, outstack;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
instack.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(outstack.empty()){
while(!instack.empty()){
outstack.push(instack.top());
instack.pop();
}
}
int x = outstack.top();
outstack.pop();
return x;
}
/** Get the front element. */
int peek() {
int res = pop(); // 重要代码,不弹出元素
outstack.push(res); // 还原数据
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return instack.empty() && outstack.empty();
}
};
注意我们实现了 peek() 函数,它的作用是获取队列的头部元素,但不弹出该元素,具体实现方法是先调用 pop() 函数弹出元素,然后将该元素再次压入出队列的栈中,即可还原队列的状态。