题目链接
题意:
用两个栈模拟队列,要求实现插入和删除操作。
思路:
-
栈的特点:先进后出
队列的特点:先进先出
- 所以用一个栈维护插入操作,一个栈维护删除操作。
- 插入的时候,插入到栈里。
- 删除的时候,弹出栈的元素。如果为空的话,将里的所有元素弹入里,这样的元素顺序就是队列删除元素的顺序,符合队列先进先出的特性。
-
还有几个小细节:
构造函数里要将两个栈清空;
删除的时候,如果stk1也为空的话,则返回-1
class CQueue {
public:
stack<int>stk1,stk2;
CQueue() {
while(!stk1.empty()) stk1.pop();
while(!stk2.empty()) stk2.pop();
}
void appendTail(int value) {
stk1.push(value);
}
int deleteHead() {
if(stk2.empty()){
while(!stk1.empty()){
stk2.push(stk1.top());
stk1.pop();
}
}
if(stk2.empty()) return -1;
else{
int now=stk2.top();
stk2.pop();
return now;
}
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/