劍指offer：5.用兩個棧實現佇列
摘要：
題目
用兩個棧來實現一個佇列，完成佇列的Push和Pop操作。 佇列中的元素為int型別。 牛客網oj地址
解題思路
因為佇列是先進先出，而棧是先進後出，所以我們在操作的時候需要一個輔助棧將順序逆轉然後pop。具體操作是這樣的，使用一個棧進行push操作，另一個輔助棧進行pop...
題目
用兩個棧來實現一個佇列，完成佇列的Push和Pop操作。 佇列中的元素為int型別。 牛客網oj地址
解題思路
因為佇列是先進先出，而棧是先進後出，所以我們在操作的時候需要一個輔助棧將順序逆轉然後pop。具體操作是這樣的，使用一個棧進行push操作，另一個輔助棧進行pop操作。當pop棧為空時就將push棧中的東西倒出來壓倒pop棧中（這樣就實現了逆序操作），當pop棧不為空的時候直接進行pop操作。具體程式碼如下所示：
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
int tempNode=stack1.top();
stack1.pop();
stack2.push(tempNode);
}
}
int result=stack2.top();
stack2.pop();
return result;
}
private:
stack<int> stack1;
stack<int> stack2;
};
類似題目
leetcode：225. 用佇列實現棧 。解決思路類似，這裡就不多描述了，ac程式碼如下：
class MyStack {
private:
queue<int> stack1;
queue<int> stack2;
public:
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
if(stack1.empty()){
stack1.push(x);
while(!stack2.empty()){
stack1.push(stack2.front());
stack2.pop();
}
}else{
stack2.push(x);
while(!stack1.empty()){
stack2.push(stack1.front());
stack1.pop();
}
}
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int result=0;
if(!stack1.empty()){
result=stack1.front();
stack1.pop();
}else{
result=stack2.front();
stack2.pop();
}
return result;
}
/** Get the top element. */
int top() {
if(!stack1.empty()){
return stack1.front();
}
return stack2.front();
}
/** Returns whether the stack is empty. */
bool empty() {
if(stack1.empty()&&stack2.empty()){
return true;
}
return false;
}
};
本 作品 由 尹傲雄 採用 知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協議 進行許可。