• lc[栈与队列]---225.用队列实现栈


    一、题目描述

     个人的思路:

            由于队列是先进先出,所以不能像昨天“两个栈实现队列”一样,倒腾一次就可以实现顺序的反转(因为a队列先出来的元素y,push到b队列中,仍然是最先出来的)。

            所以,我选择用cnt记数,记录有多少个元素,pop的操作就让in的queue全部导入out的queue,并同时记录总的个数cnt,保存好最后一个元素,然后执行cnt-1次的push操作和out.pop()操作即可,然后别忘了out还要执行一次pop()防止其中的元素影响下一次的操作。

    1. class MyStack
    2. {
    3. public:
    4. MyStack() {}
    5. void push(int x)
    6. {
    7. in.push(x);
    8. }
    9. int pop()
    10. {
    11. int res;
    12. int cnt=0;
    13. while(!in.empty())
    14. {
    15. res=in.front();
    16. out.push(res);
    17. in.pop();
    18. cnt++;
    19. }
    20. for(int i=0;i-1;i++)/*最后一个不用入栈了--->作为删除pop操作*/
    21. {
    22. in.push(out.front());
    23. out.pop();
    24. }
    25. out.pop();//需要将栈中的元素都清楚干净,不影响下一次的操作
    26. return res;
    27. }
    28. int top()
    29. {
    30. int res;
    31. int cnt=0;
    32. while(!in.empty())
    33. {
    34. res=in.front();
    35. out.push(res);
    36. in.pop();
    37. cnt++;
    38. }
    39. for(int i=0;i//注意:全部都放进来
    40. {
    41. in.push(out.front());
    42. out.pop();
    43. }
    44. return res;
    45. }
    46. bool empty()
    47. {
    48. return (in.empty());
    49. }
    50. public:
    51. queue<int>in;
    52. queue<int>out;
    53. };

    二、参考思路与代码

    注:queue的size()和back()函数Day14:C++之STL容器(2/3)__Brooke_的博客-CSDN博客

    1.两个队列的实现

            队列是先进先出的规则,把一个队列中的数据导入另一个队列中,数据的顺序并没有变,并没有变成先进后出的顺序。

            所以用栈实现队列, 和用队列实现栈的思路还是不一样的,这取决于这两个数据结构的性质。

            但是依然还是要用两个队列来模拟栈,只不过没有输入和输出的关系,而是另一个队列完全用又来备份的!

            如下面动画所示,用两个队列que1和que2实现队列的功能,que2其实完全就是一个备份的作用,把que1最后面的元素以外的元素都备份到que2,然后弹出最后面的元素,再把其他元素从que2导回que1。

    1. class MyStack {
    2. public:
    3. queue<int> que1;
    4. queue<int> que2; // 辅助队列,用来备份
    5. /** Initialize your data structure here. */
    6. MyStack() {
    7. }
    8. /** Push element x onto stack. */
    9. void push(int x) {
    10. que1.push(x);
    11. }
    12. /** Removes the element on top of the stack and returns that element. */
    13. int pop() {
    14. int size = que1.size();
    15. size--;
    16. while (size--) { // 将que1 导入que2,但要留下最后一个元素
    17. que2.push(que1.front());
    18. que1.pop();
    19. }
    20. int result = que1.front(); // 留下的最后一个元素就是要返回的值
    21. que1.pop();
    22. que1 = que2; // 再将que2赋值给que1
    23. while (!que2.empty()) { // 清空que2
    24. que2.pop();
    25. }
    26. return result;
    27. }
    28. /** Get the top element. */
    29. int top() {
    30. return que1.back();
    31. }
    32. /** Returns whether the stack is empty. */
    33. bool empty() {
    34. return que1.empty();
    35. }
    36. };

    2.(优化)用一个队列实现

            一个队列在模拟栈弹出元素的时候只要将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部,此时在去弹出元素就是栈的顺序了。

    1. class MyStack {
    2. public:
    3. queue<int> que;
    4. /** Initialize your data structure here. */
    5. MyStack() {
    6. }
    7. /** Push element x onto stack. */
    8. void push(int x) {
    9. que.push(x);
    10. }
    11. /** Removes the element on top of the stack and returns that element. */
    12. int pop() {
    13. int size = que.size();
    14. size--;
    15. while (size--) { // 将队列头部的元素(除了最后一个元素外) 重新添加到队列尾部
    16. que.push(que.front());
    17. que.pop();
    18. }
    19. int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
    20. que.pop();
    21. return result;
    22. }
    23. /** Get the top element. */
    24. int top() {
    25. return que.back();
    26. }
    27. /** Returns whether the stack is empty. */
    28. bool empty() {
    29. return que.empty();
    30. }
    31. };

  • 相关阅读:
    部分地图瓦片数据源整理
    .NFT Framework简介
    力扣labuladong——一刷day05
    http和tcp
    端粒/端粒酶生信切入点,6+端粒酶+泛癌+甲基化+实验。
    力扣刷题第二十三天--栈与队列
    BUUCTF reverse wp 96 - 100
    <PLC><西门子><工控>西门子博图V18中使用SCL语言编写一个CRC16-modbus校验程序
    深度学习计算 - 层和块
    acwing322消木块
  • 原文地址:https://blog.csdn.net/zjjaibc/article/details/127113304