剑指offer-用两个栈实现队列

忘是亡心i 2022-02-20 04:17 353阅读 0赞
题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

实现思想

栈是后入先出的，队列是先入先出的。
基于以上特点，其实本题要实现的就是将后入先出转换成先入先出。我们用到的方法是：栈1用来保存数据，当有数据过来的时候也直接压在栈顶即可，模拟队列的抛出操作实际上就是抛出栈底的数据，所以我们将数据一个一个的抛出保存在栈2中，这样所有的数据就反向保存在了栈2中，所以抛出栈2最上面的数据就是栈1最底下的数据。抛出之后别忘了再将栈2中的数据返回栈1保存恢复原来的顺序，方便下次数据的插入。

代码实现
  1. #include <stdc++.h>
  3. using namespace std;
  4. class Solution
  5. {
  6. public:
  7.     void push(int node) {
  8.         stack1.push(node);
  9.     }
  11.     int pop() {
  12.         //将堆栈1反向添加到堆栈2
  13.         while(!stack1.empty()) {
  14.             stack2.push(stack1.top());
  15.             stack1.pop();
  16.         }
  17.         //弹出堆栈2的最上面的一个
  18.         int top = stack2.top();
  19.         stack2.pop();
  20.         //再将堆栈2反向添加回堆栈1
  21.         while(!stack2.empty()) {
  22.             stack1.push(stack2.top());
  23.             stack2.pop();
  24.         }
  25.         return top;
  27.     }
  29. private:
  30.     stack<int> stack1;
  31.     stack<int> stack2;
  32. };
  35. int main()
  36. {
  37.     Solution S;
  38.     int x;
  39.     //模拟压入队列
  40.     cout << "压入数据：";
  41.     for( int i = 0; i < 10; i++) {
  42.         S.push(i);
  43.         cout << i << " ";
  45.     }
  46.     //模拟弹出队列
  47.     cout << endl;
  48.     cout << "抛出数据：";
  49.     for( int i = 0; i < 10; i++) {
  50.         x = S.pop();
  51.         cout << x << " ";
  52.     }
  53.     cout << endl;
  54.     cout << "Hello world!" << endl;
  55.     return 0;
  56. }
运行截图

在这里插入图片描述

总结

本题很容易实现，没啥好说的，最终还有一个问题没解决：当栈为空的时候也返回了最顶部的数据赋值给了一个int型的变量，这个时候的变量值是多少！
就比如：

  1. stack<int> stack_temp;
  2.     int y = stack_temp.top();
  3.     cout << y;

最终y的值应该是什么，是不是随机的，还是c++对这类问题有相应的默认值，就跟数组后面未赋值的数组默认为 ‘\0’ 一样？

发表评论

表情：
评论列表 （有 0 条评论，353人围观）

还没有评论，来说两句吧...

相关阅读