232. 用栈实现队列 - 力扣（LeetCode）
思路:用两个栈来实现队列大体上的思路是一个栈专门用来输入数据，一个栈A专门用来输入，一个栈B专门用来输出，push的时候直接把值输入到栈A就可以了。但是输出数据要麻烦点，因为队列是先进先出的，所以得先把数据从栈A中取出来，然后把数据存到栈B中，接着再取出来，起到一个类似翻转的效果，这样末尾（栈A底）的数据就变成了头部（栈B顶）的数据了。需要注意的是，如果栈B中已经有数据就直接把数据输出，没有数据才需要把栈A中的数据全部转移到栈B，否则会导致顺序错乱
技巧：贴出来的AC代码是看过标准答案以后改进过的，所以整体思路上和标准答案很像，主要改动是在peek()的优化上，起初是我把pop()的代码直接粘过来改改，后来看了标准答案才发现可以直接复用，这样让代码更加简洁明了，bug也比较好改
我的AC代码
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
_lstack.push(x);
}
int pop() {
int ans;
if(!_rstack.empty()) {
ans = _rstack.top();
_rstack.pop();
}
else {
while(!_lstack.empty()) {
_rstack.push(_lstack.top());
_lstack.pop();
}
ans = _rstack.top();
_rstack.pop();
}
return ans;
}
int peek() {
int ans = this->pop();
_rstack.push(ans);
return ans;
}
bool empty() {
return _lstack.empty() && _rstack.empty();
}
private:
stack<int> _lstack;
stack<int> _rstack;
};标准答案
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
if (stOut.empty()) {
// 从stIn导入数据直到stIn为空
while(!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
/** Get the front element. */
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return stIn.empty() && stOut.empty();
}
};
225. 用队列实现栈 - 力扣（LeetCode）
思路:两个队列实现方法，一个队列A用来操作，一个队列B用来备份数据，还需要设置一个_size参数来存储队列A的长度。push()的时候直接存入队列A，pop()的时候先取出_size - 1个值，然后将这些值暂存入队列B，再读取最后一个值的数据，接下来再删除这个值并且把队列B中暂存的值全部存回队列A。top()直接返回栈A末尾的元素即可，empty()则直接看队列A是不是空的就行了，因为队列B只是用来临时备份，并不参与实际存储。
- 我是小丑，原来队列自带
size这个属性，没必要自己再设置一个，又是画蛇添足的一天 - 如果想要只用一个队列实现栈，只需要在弹出的时候将弹出数据再重新添加回栈即可
我的AC代码
class MyStack {
public:
MyStack() {
_size = 0;
}
void push(int x) {
qcontrol.push(x);
_size++;
}
int pop() {
int ans;
int cnt = _size - 1;
while(cnt--) {
qstorage.push(qcontrol.front());
qcontrol.pop();
}
ans = qcontrol.front();
qcontrol.pop();
while(!qstorage.empty()) {
qcontrol.push(qstorage.front());
qstorage.pop();
}
if(_size > 0) {
_size--;
}
return ans;
}
int top() {
int ans = qcontrol.back();
return ans;
}
bool empty() {
return qcontrol.empty();
}
private:
queue<int> qcontrol;
queue<int> qstorage;
int _size;
};复刻标准答案只用一个队列的做法
class MyStack {
public:
MyStack() {
}
void push(int x) {
qcontrol.push(x);
}
int pop() {
int ans;
int cnt = qcontrol.size() - 1;
while(cnt--) {
qcontrol.push(qcontrol.front());
qcontrol.pop();
}
ans = qcontrol.front();
qcontrol.pop();
return ans;
}
int top() {
int ans = qcontrol.back();
return ans;
}
bool empty() {
return qcontrol.empty();
}
private:
queue<int> qcontrol;
};标准答案
正常做法(用两个队列)
class MyStack {
public:
queue<int> que1;
queue<int> que2; // 辅助队列，用来备份
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que1.size();
size--;
while (size--) { // 将que1 导入que2，但要留下最后一个元素
que2.push(que1.front());
que1.pop();
}
int result = que1.front(); // 留下的最后一个元素就是要返回的值
que1.pop();
que1 = que2; // 再将que2赋值给que1
while (!que2.empty()) { // 清空que2
que2.pop();
}
return result;
}
/** Get the top element. */
int top() {
return que1.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que1.empty();
}
};空间复杂度直线降低法(只用一个队列)
class MyStack {
public:
queue<int> que;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que.size();
size--;
while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
que.pop();
return result;
}
/** Get the top element. */
int top() {
return que.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que.empty();
}
};
Comments NOTHING