Implement the following operations of a stack using queues.
Notes:
push to back
, peek/pop from front
, size
, and is empty
operations are valid.void push(int x)
int pop() 要求返回被弹出的元素值
int top()
bool empty()
1、这道题目要求用队列来实现堆栈,要求只能使用队列的push pop front size empty这几个函数,完成堆栈的压入、弹出、栈顶元素和判断是否为空的功能。
2、队列与堆栈的唯一不同之处,在于堆栈是队尾输入、队尾输出,队列是队尾输入、队首输出,所以如果我们把输入的新元素放在队首,是不是就可以用队列完成堆栈了?
代码如下:(附详解)
queue<int>q1;//定义一个队列
/** Push element x onto stack. */
void push(int x)
{
q1.push(x);
for(int i=0;i<q1.size()-1;i++)//对于每个队中已有元素,取出之后插到队尾,保证新元素在前,旧元素在后
{
q1.push(q1.front());
q1.pop();
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() //返回元素值
{
int t=q1.front();
q1.pop();
return t;
}
/** Get the top element. */
int top()
{
return q1.front();
}
/** Returns whether the stack is empty. */
bool empty()
{
return q1.empty();
}
上述代码实测2ms,beats 100% of cpp submissions。