• 【代码随想录】算法训练营 第十天 第五章 栈与队列 Part 1


    232. 用栈实现队列

    题目

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

    实现 MyQueue 类:

    • void push(int x) 将元素 x 推到队列的末尾
    • int pop() 从队列的开头移除并返回元素
    • int peek() 返回队列开头的元素
    • boolean empty() 如果队列为空,返回 true ;否则,返回 false

    说明:

    • 你 只能 使用标准的栈操作 —— 也就是只有 push to toppeek/pop from topsize, 和 is empty 操作是合法的。
    • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

    思路

    用两个栈来模拟队列,一个模拟队列的入口,另一个模拟队列的出口,要注意的是,在实现涉及到某个口的操作时,需要保证所有元素都在模拟那个口的栈中;

    其次就是要熟悉栈stack这个容器的操作。

    代码

    1. class MyQueue {
    2. public:
    3. stack<int> stin; // 模拟队列的输入口
    4. stack<int> stout; // 模拟队列的输出口
    5. MyQueue() { // 由于我们是用栈来模拟的,所以这里不需要写内容
    6. }
    7. void push(int x) { // 由于我们的队列不限长度,所以要添加元素时就直接push到模拟输入口的栈里即可
    8. stin.push(x);
    9. }
    10. int pop() { // 模拟弹出队头元素
    11. if(stout.empty()) { // 弹出元素涉及到队列的出口,所以要判断模拟队列出口的栈是否为空
    12. while (!stin.empty()) { // 模拟队列出口的栈不为空,就要把入口栈的元素全部移到出口栈,这样才能弹出处于入口栈底的元素
    13. stout.push(stin.top()); // 将入口栈的栈顶元素取出,放入出口栈
    14. stin.pop(); // 注意上面的取出只是把值取出,元素还在里面,所以要pop掉
    15. }
    16. }
    17. int result = stout.top();
    18. stout.pop();
    19. return result;
    20. }
    21. int peek() {
    22. if (stout.empty()) {
    23. while (!stin.empty()) {
    24. stout.push(stin.top());
    25. stin.pop();
    26. }
    27. }
    28. return stout.top();
    29. }
    30. bool empty() {
    31. if (stin.empty() && stout.empty())
    32. return true;
    33. else
    34. return false;
    35. }
    36. };
    37. /**
    38. * Your MyQueue object will be instantiated and called as such:
    39. * MyQueue* obj = new MyQueue();
    40. * obj->push(x);
    41. * int param_2 = obj->pop();
    42. * int param_3 = obj->peek();
    43. * bool param_4 = obj->empty();
    44. */

    225. 用队列实现栈

    题目

    请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppop 和 empty)。

    实现 MyStack 类:

    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

    思路

    可以用两个队列实现,其实用一个队列也行。

    用两个队列的话,一个是用来模拟栈的,另一个则是作为辅助队列,只能在操作中暂存元素,操作完后还得把元素还给第一个栈然后再清空。

    代码

    两个队列实现
    1. class MyStack {
    2. public:
    3. queue<int> q1;
    4. queue<int> q2;
    5. MyStack() {
    6. }
    7. void push(int x) {
    8. q1.push(x);
    9. }
    10. int pop() {
    11. int size = q1.size();
    12. size--;
    13. while (size--) {
    14. q2.push(q1.front());
    15. q1.pop();
    16. }
    17. int result = q1.front();
    18. q1.pop();
    19. q1 = q2;
    20. while (!q2.empty()) {
    21. q2.pop();
    22. }
    23. return result;
    24. }
    25. int top() {
    26. return q1.back;
    27. }
    28. bool empty() {
    29. return q1.empty();
    30. }
    31. };
    32. /**
    33. * Your MyStack object will be instantiated and called as such:
    34. * MyStack* obj = new MyStack();
    35. * obj->push(x);
    36. * int param_2 = obj->pop();
    37. * int param_3 = obj->top();
    38. * bool param_4 = obj->empty();
    39. */
    一个队列实现
    1. class MyStack {
    2. public:
    3. queue<int> q;
    4. MyStack() {
    5. }
    6. void push(int x) {
    7. q.push(x);
    8. }
    9. int pop() {
    10. int size = q.size();
    11. size--;
    12. while (size--) {
    13. q.push(q.front());
    14. q.pop();
    15. }
    16. int result = q.front();
    17. q.pop();
    18. return result;
    19. }
    20. int top() {
    21. return q.back();
    22. }
    23. bool empty() {
    24. return q.empty();
    25. }
    26. };
    27. /**
    28. * Your MyStack object will be instantiated and called as such:
    29. * MyStack* obj = new MyStack();
    30. * obj->push(x);
    31. * int param_2 = obj->pop();
    32. * int param_3 = obj->top();
    33. * bool param_4 = obj->empty();
    34. */

  • 相关阅读:
    cloudenative2-1-go进阶
    Python 08学习之文件操作
    三级等保-linux服务器三权分立设置
    笔试刷题Day—1
    (附源码)springboot毕业生弃置物品交易系统 毕业设计 231151
    美国拒绝分享系统漏洞,中国打造首个桌面操作系统根社区应对
    MATLAB算法实战应用案例精讲-【优化算法】沙丁鱼优化算法(SOA)(附MATLAB代码实现)
    Kubeadm搭建kubernetes集群
    Shell常用脚本:Nexus批量上传本地仓库增强版脚本(强烈推荐)
    从过去到未来:回顾DDR技术的演进和未来趋势
  • 原文地址:https://blog.csdn.net/Summerison/article/details/133956290