代码随想录算法训练营Day10|232. 用栈实现队列、225. 用队列实现栈
232. 用栈实现队列
题目要求"假设所有操作都是有效的 (例如,一个空的队列不会调用 pop
或者 peek
操作)",因此在使用pop()
,peek()
操作时不需要进行异常输入的判断。
本题使用两个栈来分别作为输入和输出的接口,关键在于栈的方向对立,以下图为例:
我们将栈分为进栈和出栈:
-
输入:直接将值输入进栈即可。
-
输出:首先将进栈值倒序压入出栈中,这时栈中所有元素会反转,此时出栈的栈顶元素就是相对应的队列的首位元素。在多次写入写出过程中可能会出现进栈和出栈均包含元素的情况,为满足队列先进先出(FIFO)的特性我们需要分开讨论:
- 当出栈为不为空:直接输出出栈的栈顶元素即可。
- 当出栈为空时:需要将进栈元素全部导入(注意是全部元素),再输出出栈栈顶元素。
出栈不为空时,不能再将进栈元素导入,这是因为进栈导入出栈只能保证导入的那段字符串反转,之后再追加压入的元素理论上压入出栈的优先级应该更高。
另外需要注意的是栈中查看栈顶元素和弹出栈顶元素是独立的操作,一般都配套进行使用:
stack<int> st;
// 查看栈顶元素
st.top();
// 弹出栈顶元素
st.pop();
完整代码如下:
class MyQueue {
public:
MyQueue() {
// 空栈不需要初始化
}
void push(int x) {
stIn.push(x);
}
int pop() {
if (stOut.empty()) {
// 将输入栈元素全部压入输出栈
while (!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int temp = stOut.top();
stOut.pop();
return temp;
}
int peek() {
int temp;
if (stOut.empty()) {
// 将输入栈元素全部压入输出栈
while (!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
return stOut.top();
}
bool empty() {
return (stIn.empty() && stOut.empty());
}
private:
stack<int> stIn;
stack<int> stOut;
};
/**
* 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();
*/
进一步优化,为了提高代码的复用性,一定要懂得复用,功能相近的函数要抽象出来,不要大量的复制粘贴,很容易出问题!对于查看首位元素的函数可以进一步优化:
int peek() {
int result = this->pop();
stOut.push(result);
return result;
}
225. 用队列实现栈
同上,不需要考虑异常情况。
队列是先进先出的规则,把一个队列中的数据导入另一个队列中,数据的顺序并没有变,并没有变成先进后出的顺序。
①双队列法
如下面动画所示,用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1。
代码如下:
class MyStack {
public:
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
// 只取出n-1个元素,输出末尾元素
size--;
while (size--) {
que2.push(que1.front());
que1.pop();
}
int result = que1.front();
que1.pop();
// 再重置备份队列
queue<int> backUp = que1;
que1 = que2;
que2 = backUp;
return result;
}
int top() {
return que1.back();
}
bool empty() {
return que1.empty();
}
private:
queue<int> que1;
queue<int> que2;
};
/**
* 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();
*/
②单队列法
其实这道题目就是用一个队列就够了。
一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时在去弹出元素就是栈的顺序了。
class MyStack {
public:
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
size--;
while (size--) {
que.push(que.front());
que.pop();
}
int result = que.front();
que.pop();
return result;
}
int top() {
return que.back();
}
bool empty() {
return que.empty();
}
private:
queue<int> que;
};
/**
* 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();
*/
标签:obj,队列,元素,随想录,pop,que1,int,用栈
From: https://www.cnblogs.com/buryinshadow/p/16933472.html