【剑指offer】学习计划day1

目录

一. 前言 

二. 用两个栈实现队列

        a.题目

         b.题解分析

          c.AC代码

  二. 包含min函数的栈

         a.题目

         b.题解分析

        c.AC代码 

一. 前言 

 本系列是针对Leetcode中剑指offer学习计划的记录与思路讲解。详情查看以下链接：

剑指offer-学习计划https://leetcode.cn/study-plan/lcof/?progress=x56gvoct

    本期是本系列的day1，话不多说，让我们来看看今天的主题----》栈与队列（简单）

    题目编号：JZ09，JZ30

二.

        a.题目

         b.题解分析

        是不是很熟悉？这题在之前【刷题篇】栈和队列 中有碰到过，我们当时分析了使用一个栈和使用两个栈实现的可行性，发现如果我们采用就地存储，只使用一个栈，是无法达到我们的目的。而本题很明确的告诉了我们使用两个栈来实现，我们也就不需要考虑这么多了。

        好嘞，让我们简单回忆以下之前的思路(又开始凑字数了)：由于队列的特性是先进先出，栈的特性是后进先出，所以我们对队头进行删除操作必须先将前n-1个元素出栈后才能删除---》

解题方法是将一个栈用来存放入队的元素(input)，而另一个栈则用来出队(output) 。对于入队操作，则往input入栈；而对于出队操作，如果ouput为空，则先将input中的元素全部压入output中，此时output的栈顶元素恰好就是队头元素，然后出栈即可，如果不为空，则直接出栈。动态演示如下：

          c.AC代码

class CQueue {
public:
    stack<int> input;
    stack<int> output;
    CQueue() {

    }
    //入队
    void appendTail(int value) 
    {
        //往input入栈
        input.push(value);
    }
    //出队
    int deleteHead() 
    {
        //output为空，先将input数据移入
        if (output.empty())
        {
            if(input.empty())
            {
                //input也为空，队列为空，返回-1
                return -1;
            }
            while (!input.empty())
            {
                int val = input.top();
                input.pop();
                output.push(val);
            }
        }//end of if
        //此时output栈顶元素即为队头元素，出栈
        int ret = output.top();
        output.pop();
        return ret;
    }//end of fun
};

  二. ：

         a.题目

         b.题解分析

        由于栈是限制型数据结构，因此我们无法对其进行遍历求最小值。所以我们每次操作时需要一并对最小值进行维护。

        本题的思路是：再构建一个辅助栈来存储最小值，最小栈 中的每个元素对应栈的每个状态时的最小值。例如：最小栈的栈底元素对应栈只有一个元素时的最小值，最小栈栈底元素的上一个元素对应栈有两个元素时的最小值，以此类推：

         这样，栈顶元素就是当前栈的最小值。当我们进行入栈时，我们就将栈顶元素和入栈元素进行比较，同步将当前最小值压入辅助栈中，保证栈顶元素始终为栈的最小值。而当我们进行出栈时，我们同步将辅助栈进行出栈，出栈后辅助栈的栈顶元素恰好就是当前状态栈的最小值。演示如下：

        c.AC代码 

class MinStack {
    stack<int> s1;
    stack<int> minstack;//存储最小值的辅助栈
public:
    /** initialize your data structure here. */
    MinStack() {
        minstack.push(INT_MAX);
    }
    //入栈
    void push(int x) 
    {
        s1.push(x);
        minstack.push(std::min(x,minstack.top()));//同步将最小值压入辅助栈
    }
    //出栈
    void pop() {
        if(s1.empty())
        {
            return;
        }
        s1.pop();
        minstack.pop();//同步对辅助栈进行出栈
    }
    //求栈顶元素
    int top() {
        return s1.top();
    }
    //求最小值
    int min() {
        return minstack.top();//辅助栈的栈顶元素即为最小值
    }
};

以上，就是本期的全部内容啦🌸

制作不易，能否点个赞再走呢🙏文章来源地址https://www.toymoban.com/news/detail-423641.html

到了这里，关于【剑指offer】学习计划day1的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！