2021-5-9 日记 C++(十六)

今天的leetcode题目是用两个栈实现队列

队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:

输入:
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
提示:

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

首先看题,我们普遍认知的栈是FILO(First In Last Out)先进后出的,而队列则是FIFO先进先出的,我们要让栈底的元素先出,就要借助一个辅助栈,同时也就达成了题目要求用两个栈实现队列的要求。

第一步我们先想的是怎么用这个辅助栈,比如栈1先压进两个数1和2,那么2在上1在下,怎么样才能把1弄到栈顶,让1先出呢?

很显然的我们可以先把栈1的栈顶元素“搬”到栈2,这样就可以完成栈1所有元素的倒置,并且让原本栈底的元素变成栈顶元素。

那如果栈1的元素更多呢?比如1、2、3、4、5顺序压入栈1,我们要取到3,也就是把1、2、3都“出队”。那么很简单的我们先把5压入栈2,接着是4…一直到1,到1之后再把1出栈、2出栈、3出栈,随后完成操作。

大概有了思路后就是编程time了,思路清晰后其实不难写出答案
1、第一步,定义栈1和栈2

    stack<int>stack1,stack2;

2、第二步,定义入栈函数

    void appendTail(int value) {
        stack1.push(value);
    }

3、第三步,定义出栈函数,我们分步讲解
(1)首先判断栈2是否空,如果栈1和栈2都为空则返回-1,若栈2为空栈1不空,则将栈1元素全部压入栈2

        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if(stack2.empty())
        {
            return -1;
        }

(2)如果栈1元素全部压入栈2且栈2不为空,则开始输出栈顶元素,相当于开始执行队列的“出队”操作

        else
        {
            int returnnum = stack2.top();
            stack2.pop();
            return returnnum;
        }
上一篇:剑指 Offer 09. 用两个栈实现队列


下一篇:ORACLE-数据泵