day10:
232.用栈实现队列
题目链接
状态:
文档:programmercarl.com
思路:
用栈实现队列。要先明白两者的区别。
栈:单开门,先进后出,只有一端能进出。
队列:双开门,先进先出,一端进一端出。
既然想用单开门实现双开门,那么一个单开门肯定是不够的,因为单开门进出的顺序已经不满足双开门的顺序了,所以我们需要设置两个单开门,让其中一个单开门是进栈状态,另一个单开门是出栈状态。
在push数据的时候,只要数据放进输入栈(进栈)就好。
但在pop的时候,操作就复杂一些。输出栈如果为空,就把进栈数据全部导入进来(注意是全部导入),再在出栈里弹出数据;如果输出栈不为空,则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢?如果进栈和出栈都为空的话,说明模拟的队列为空了。
代码:
class MyQueue {
public:
//先设置两个栈 进栈和出栈
stack<int> stIn;
stack<int> stOut;
MyQueue() {
}
//输入
void push(int x) {
//进栈也输入
stIn.push(x);
}
//输出的时候分两种情况
//一种是出栈中有元素 那么直接pop即可
//一种是出栈中无元素,要先把进栈中的所以元素都导入,再pop
int pop() {
//如果出栈为空
if(stOut.empty())
{
//把stIn中的ele全部导入进来
while(!stIn.empty())
{
stOut.push(stIn.top());
stIn.pop();
}
}
//出栈中有东西 直接pop
int result = stOut.top();
stOut.pop();
return result;
}
//返回队列开头元素
//和上面的stOut.top()是一个东西
//复用一下
int peek() {
int result = this->pop();
//上面的函数中把result pop出来了,所以还需要再push回去
stOut.push(result);
return result;
}
bool empty() {
//两个栈都空了 才能说明队列空了
return stIn.empty() && stOut.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
225. 用队列实现栈
题目链接
状态:
文档:programmercarl.com
思路:
刚刚做过栈与队列:用栈来实现队列。现在可能依然想着用一个输入队列,一个输出队列,就可以模拟栈的功能,仔细想一下还真不行。
队列是先进先出的规则,把一个队列中的数据导入另一个队列中,数据的顺序并没有变(依旧是先进先出),并没有变成先进后出的顺序。
所以用栈实现队列, 和用队列实现栈的思路还是不一样的,这取决于这两个数据结构的性质。
但是依然还是要用两个队列来模拟栈,只不过没有输入和输出的关系,而是另一个队列完全用来备份的。
用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把除que1最后面的元素外的元素都备份到que2,然后弹出que1中这个最后面的元素,再把其他元素从que2导回que1。
其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时再去弹出元素就是栈的顺序了。
代码:
class MyStack {
public:
//用一个队列去实现
queue<int> que;
MyStack() {
}
//进栈 -- 队列也同时进
void push(int x) {
que.push(x);
}
//出栈 -- 把最后一个元素外的元素重新入到队列中
int pop() {
int size = que.size(); //队列的长度
size--; //表示除了最后一个元素外的长度
while(size != 0)
{
//进队列
que.push(que.front());
//出队列
que.pop();
size--;
}
int result = que.front();
que.pop();
return result;
}
//返回栈顶元素
//也就相当于返回pop()中的result
// int top() {
// int result = this->pop();
// que.push(result);
// return result;
// }
//queue有back()接口 所以不用像上面一样那么麻烦了
int top() {
return que.back();
}
//判断栈是否为空
bool empty() {
return que.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/