剑指 Offer 09. 用两个栈实现队列

题目描述

来源leetcode
剑指 Offer 09. 用两个栈实现队列
看到这个题,我看了很久,看不懂这个示例,emmm
于是我打开评论,看了大家的分析终于看懂了

题目意思

输入:

["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]

[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”] : 这个是每一行代码的操作
[[],[3],[],[]]:这个对应每个操作所需要的参数。
其中,CQueue ,deleteHead 不需要参数,一般返回null. 如果队列中没有元素,deleteHead 返回-1,若删除元素a,则返回值为a

  1. CQueue 创建队列,返回值为null
  2. appendTail 从队列尾部添加数据3,返回值为 null
  3. deteleHead 从队列头部删除数据,此时只有3, 返回值为3
  4. deleteHead 从队列头部再删除数据,此时队列中无数据了,返回值为-1

第二个例子同理,就不细说了。

解题思路

首先,我们应该明白
栈 : 是先进后出,只能在栈顶进行元素的 append 和delete操作
队列:是先进先出,在队列head 上只能进行删除操作,在tail 上只能进行添加操作
那么一个栈无法实现队列的功能就是:
栈底的元素 对应着队首的元素,无法直接删除,需要将其上方的元素全部 挪走 才能删除最后栈底元素。
其实,这跟汉诺塔差不多,要想把a上的最大的一个盘子,也就是最底层的一个盘子,只有把它上面所有的盘子都挪走。
剑指 Offer 09. 用两个栈实现队列

回到题目中,给了我们2个栈,A和B.
假设先往A中添加数据 appendTail 可以执行,是从尾部添加的
但是要删除数据 ,执行deleteHead ,就比较麻烦了。需要把A中的数据,全部移到B中,然后再在B中删除元素。
剑指 Offer 09. 用两个栈实现队列

代码

class CQueue {
public:
    stack<int>A;
    stack<int>B;
    CQueue() {
//构造函数
    }
    
    void appendTail(int value) {
        A.push(value);

    }
    
    int deleteHead() {
        //删除操作在B中进行
        if(!B.empty()){
            //B中有数
           int temp = B.top();
           B.pop();
           return temp;
        }
        else{
            //B中没数
            if(A.empty()){
                return -1;
            }
            else{
                while(!A.empty()){
                    B.push(A.top());
                    A.pop();
                }
                int temp = B.top();
                B.pop();
                return temp;
            }

        }

    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

刷题方法

1: CodeTop :根据公司 部门 岗位 ,推荐面试常考的题 https://codetop.cc/home
2:labuladong 教做题的套路 模式: https://labuladong.gitbook.io/algo/

上一篇:多线程的线程开销


下一篇:Oracle错误——ORA-39000:转储文件说明错误、ORA-39001:参数值无效、ORA-39088:文件名不能包含路径说明