【剑指offer】学习计划day1

快来打我* 2024-04-25 20:04 6阅读 0赞

![b4bb8d0773154557a21960b174eb195a.gif][]

![4727a76c8f55490581d8ba0ba8dcddaf.png][]

**目录**

一. 前言

二. 用两个栈实现队列

a.题目

b.题解分析

c.AC代码

二. 包含min函数的栈

a.题目

b.题解分析

c.AC代码

--------------------

### 一. 前言 ###

>  本系列是针对Leetcode中剑指offer学习计划的记录与思路讲解。详情查看以下链接：
> 
> [剑指offer-学习计划![icon-default.png_t_N3I4][]https://leetcode.cn/study-plan/lcof/?progress=x56gvoct][offer-_icon-default.png_t_N3I4_https_leetcode.cn_study-plan_lcof_progress_x56gvoct]

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

题目编号：JZ09，JZ30

### 二. ###

#### a.题目 ####

![8f4635a690294907858660e9321dc4a3.png][]

#### b.题解分析 ####

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

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

![66b3b2cc211847d3b01aefccdd9a90d1.png][]

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

![881ceb91b49a4697a34dcc6081e43a20.gif][]

#### 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
    };

![801c278ccced4b3c8389a0e613772dea.png][]

### 二. [：][Link 2] ###

#### a.题目 ####

![b8e13bb21a5440d194b42957f275694d.png][]

#### b.题解分析 ####

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

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

![c998c75a542b467ba96fbe92fd24abe3.png][]

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

![66f87956de144d70ab237077fc86099d.gif][]

#### 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();//辅助栈的栈顶元素即为最小值
        }
    };

--------------------

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

***制作不易，能否点个赞再走呢*****🙏**

[b4bb8d0773154557a21960b174eb195a.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/419a83c4d17a4bee85fb25e7d74e3cbc.gif
[4727a76c8f55490581d8ba0ba8dcddaf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/8f53f9eb50664e59bfcb30605fcc1d63.png
[icon-default.png_t_N3I4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/b3989c3c7d4f4fa58687baabda883ebb.png
[offer-_icon-default.png_t_N3I4_https_leetcode.cn_study-plan_lcof_progress_x56gvoct]: https://leetcode.cn/study-plan/lcof/?progress=x56gvoct
[8f4635a690294907858660e9321dc4a3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/d1dc607005ca4fccb52be92bd2680256.png
[Link 1]: http://t.csdn.cn/loGu0
[66b3b2cc211847d3b01aefccdd9a90d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e3ea8dc2b3c742b9ae94c8758f31a897.png
[881ceb91b49a4697a34dcc6081e43a20.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/499987802bd14afd8581e826f8140bbf.gif
[801c278ccced4b3c8389a0e613772dea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/bfb33b0b6cc64788ae797dabfc581890.png
[Link 2]: https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=x56gvoct
[b8e13bb21a5440d194b42957f275694d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/ed1f333ac70447e1b6b0418315e3d56c.png
[c998c75a542b467ba96fbe92fd24abe3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/6266ece8bd0246479bbc13354a7b331f.png
[66f87956de144d70ab237077fc86099d.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/2571a15fa2844a8e8fab10e4cb335470.gif