【0232.用栈实现队列】
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
int temp;
if (!stOut.empty()) {
}
else {
while (!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
temp = stOut.top();
stOut.pop();
return temp;
}
int peek() {
int temp;
if (!stOut.empty()) {
}
else {
while (!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
temp = stOut.top();
return temp;
}
bool empty() {
if (stIn.empty() && stOut.empty()) {
return true;
}
return false;
}
};
/**
* 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();
*/
-
运行成功
-
第一次做栈、队列的题 原本就没有思路 对基本的定义和基本的操作语句都不了解 而且对pop 和 peek函数的设计花费时间最多 对卡哥的代码分析 下面将对上述问题一 一回应
-
关于 本题对栈和队列使用的思路
- 栈有栈的操作 队列有队列的操作 区别就是push pop的位置不同。本题要用栈实现队列的操作 意思是 题目希望通过定义一个数据类型MyQueue 它pop出来的是最开始的元素而不是最后的元素。 那么你就想 直接定义queue类型不就直接pop出来最开始的元素了吗 不 这道题不让你用queue而只能用stack类型 可是stack不能直接用pop函数剔除最开始的元素 这就是这道题的关键 ：构造数据类型MyQueue 达到用栈实现队列的操作 即意思是 如何用stack对象.pop() 实现queue对象.pop （不论栈还是队列 push都是一致的）
- 本题 思路是 定义一个输入栈stIn 一个输出栈stOut （定义语句写在public:下面 构造函数等子函数之前） 只要是输入操作 那么元素就都stIn.push(x)进入输入栈 只要是进行输出操作 。。。。。在输入栈staIn里的元素为空的情况下 从输出栈stOut.pop()取元素 否则就需要先把输入栈里的元素腾空到输出栈里 再进行上述的--输入栈为空的情况下从输出栈pop取元素这个操作。 第一次做 这个思路还是比较陌生的
- 关于 “把输入栈里的元素腾空到输出栈里” 不能直接
stOut.push(stIn.pop());因为pop push 不能在弹出、插入的同时得到返回值 也就是说pop push操作只进行弹出插入 无返回值 改成stOut.push(stIn.top()); stIn.pop();即可 因为top()操作返回栈顶元素 此外队列的基本操作语句也要注意这点!
-
关于 C++中对栈、队列的定义和基本操作语句
// 使用容器定义栈、队列 我也不知道什么时候用 // 下面三行代码中stack 换成queue就是用容器定义队列的操作 std::stack<int, std::deque<int> > third; //默认使用deque为底层容器 std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈 std::stack<int, std::list<int>> third; // 定义以list为底层容器的栈 // 不用容器的定义语句 stack<int> stIn; stack<int> stOut; queue<int> que1; // stack基本操作语句 # include<stack> s.push(x); //入栈,在栈顶增加元素 s.pop(); //出栈, 移除栈顶元素 s.top(); //访问栈顶, 返回栈顶元素 s1.push(s2.pop()) //是不对的 注意标准库里的pop函数没有返回值 应该改为下面语句 s1.push(s2.top()) s.size(); //栈的大小, 返回栈中元素个数 s.empty(); //栈是否为空, 为空则返回真 while(!s.empty()){ } if(!stOut.empty()) //等常常作为判断语句的条件 // queue基本操作语句 # include<queue> q.push(x); //入队,在队尾添加元素 q.pop(); //出队, 删除队列的第一个元素 q.front(); //访问队首, 返回第一个元素 q.back(); //访问队尾, 返回最后一个元素 q.size(); //队的大小, 返回队列中元素个数 q.empty(). //队是否为空, 为空则返回真 -
关于本题的 pop peek函数
int pop() { int temp; if (!stOut.empty()) { } else { while (!stIn.empty()) { stOut.push(stIn.top()); stIn.pop(); } } temp = stOut.top(); stOut.pop(); return temp; } 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; }- 上述代码其实我的最开始的if完全没必要 因为if条件满足的话什么什么语句都不会执行的 那么直接删去if 后面的else条件写出来换成if 就与卡哥的代码一模一样了 这就是对不执行语句的冗余代码进行删除的简单思路 可能写代码时 因为水平不高逻辑层次低所以容易出现冗余代码 写完代码检查下是否存在冗余代码返回去就可以得到一个更强更凝练的逻辑
-
关于本题的peek函数
int peek() { if (stOut.empty()) { while (!stIn.empty()) { stOut.push(stIn.top()); stIn.pop(); } } int temp = stOut.top(); return temp; } /** Get the front element. */ int peek() { int res = this->pop(); // 直接使用已有的pop函数 stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去 return res; }- 设计的peek和设计的pop类似 都有返回值 但一个只需要找到 另一个需要找到并删除 所以笨代码就和前面设计的pop类似 但卡哥的思路是 在自己要设计的函数peek里调用自己已经设计的函数pop 减少相似代码的赋值 增强代码复用性 这个思路值得有！！但是本题 感觉你用了本题的pop获得值后 同时你删除了这个值 你需要再push进去 但这样元素的顺序不久改变了么 那么之后再pop的时候是不是会受到影响呢 我这么觉得
【0225.用队列实现栈】
class MyStack {
public:
queue<int> que1;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int temp1 = que1.back();
int temp2 = que1.front();
while (temp2 != temp1) {
que1.push(temp2);
que1.pop();
temp2 = que1.front();
}
que1.pop();
return temp1;
}
int top() {
return que1.back();
}
bool empty() {
if (que1.empty()) {
return true;
}
return false;
}
};
/**
* 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();
*/
-
运行不成功
-
两点 一是最后的empty()函数代码冗余 二是pop函数有问题
-
关于empty（）函数冗余的问题
-
bool empty() { if (que1.empty()) { return true; } return false; } /** Returns whether the stack is empty. */ bool empty() { return que.empty(); }- 既然 两函数返回值一直 就直接在子函数1中 return 子函数2即可
-
关于pop函数
-
我的思路算是优化版本的----不是用两个队列 而是一个队列就可以完成 因为我参考两个栈实现队列的基本操作这个思路 因为栈和队列最本质的区别是pop时哪头元素先出 两个栈可以实现整串元素的逆序 那么逆序之后栈.pop栈头的那个元素 就是 原顺序队列.pop队头那个元素。因此本题要用队列实现栈的操作 核心也在于如何逆序 从而队列pop对头的那个元素 就是栈pop栈底的那个元素 仔细考虑 一个队列 队头元素出队 进入到队尾 直到执行size次即可（而不是将要出队的队头元素等于最开始要出队的那个队尾元素 这也是我的代码错误之处 ---- 判断条件写错了）
-
我的错误代码
int pop() { int temp1 = que1.back(); int temp2 = que1.front(); while (temp2 != temp1) { que1.push(temp2); que1.pop(); temp2 = que1.front(); } que1.pop(); return temp1; } -
更改正确后
int pop() { int temp1 = que1.back(); int temp2 = que1.front(); int que1Size = que1.size(); while (--que1Size) { que1.push(temp2); que1.pop(); temp2 = que1.front(); } que1.pop(); return temp1; } -
至此以上代码运行成功
-
-
跟卡哥优化版本思路一样
明天继续：）
标签：stIn,int,pop,day22,stOut,push,empty From： https://www.cnblogs.com/deservee/p/16909634.html