链接
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
耗时
解题:10 min
题解:9 min
题意
用两个栈实现一个队列。
队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
思路
设置两个栈,st1 和 st2。
入队时,直接把元素放入 st1。
出队时,先看 st2 是否为空,如果为空,将 st1 中的元素顺序放入 st2 中,这样 st2 中就可以是正常顺序出栈了;如果 st2 不为空,直接弹出 st2 栈顶元素返回即可。
PS: 出队时别忘记检查当 st2 为空时,st1 是否为空,如果 st1 也为空,说明队列中没有元素,需要返回 -1。
AC代码
class CQueue {
public:
stack<int> st1, st2;
CQueue() {
while(!st1.empty()) {
st1.pop();
}
while(!st2.empty()) {
st2.pop();
}
}
void appendTail(int value) {
st1.push(value);
}
int deleteHead() {
if(st2.empty()) {
if(st1.empty()) return -1;
while(!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}
int ans = st2.top();
st2.pop();
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)