当前位置：首页 > article >正文

C语言练习题包含min函数的栈

article 2024/11/14 4:01:57

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

数据范围：操作数量满足 0≤n≤300 ，输入的元素满足 ∣val∣≤10000
进阶：栈的各个操作的时间复杂度是 O(1) ，空间复杂度是O(n)

示例:

输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

输出: -1,2,1,-1

解析:

"PSH-1"表示将-1压入栈中，栈中元素为-1

"PSH2"表示将2压入栈中，栈中元素为2，-1

“MIN”表示获取此时栈中最小元素==>返回-1

"TOP"表示获取栈顶元素==>返回2

"POP"表示弹出栈顶元素，弹出2，栈中元素为-1

"PSH1"表示将1压入栈中，栈中元素为1，-1

"TOP"表示获取栈顶元素==>返回1

“MIN”表示获取此时栈中最小元素==>返回-1

分析如下：

题目意思是要展示栈的数据结构，演示压栈、弹出、获取栈顶元素、获取最小值这四个操作。

由于栈是记录临时变量的，不方便我们演示，这里采用数组来记录栈中元素，并参考栈的压入弹出等功能对数组进行操作，从而实现演示。

这里题目要求操作数不大于300个，可以使用一个300元素大小的数组记录。同时元素的绝对值不大于10000，则可以使用整型元素数组。

压栈操作就是给数组元素赋值，为了方便记录，我们另外定义一个整型元素，用来记录现在栈中的元素个数。则栈顶的元素就是元素个数的最后一个。每次压栈，则元素个数+1，将该值赋给数组中对应的元素。

弹出操作可以用元素个数-1表示。

获取栈顶元素则是获取当前元素个数的最后一个。

获取最小元素，这是查找现在数组中最小的元素。

代码展示：

//题目考察的是压栈、出栈操作
//由于要记录栈中的数据，这里通过全局变量实现。

int arr[300] = { 0 }, count = 0;
//由于题中操作数量<=300，创建数组arr，包含300个int类型元素；count为数组中元素计数；

void push(int value)    //按题意，push是压栈操作，即将输入值压入栈中
{
    if (count >= sizeof(arr))   //先判断栈中元素是否够300个，超出则直接返回，不压入数据
        return;
    arr[count++] = value;   //栈中元素不足300个，则将value值压入栈中，并将元素数+1
}

void pop() //按题意，pop是弹出操作，即将栈顶的元素弹出
{
    if (count <= 0)     //先判断栈中还有没有元素，没有元素则直接返回
        return;
    count--;   //数组中记录元素个数为count，count--即将栈顶数据弹出；

}

int top()   //按题意，top是获取栈顶元素
{
    return arr[count - 1];  //返回栈顶元素
}

int min()   //按题意，min是获取最小值
{
    int i = 0;          //遍历查找，挨个判断栈中最小值
    int ret = arr[0];
    for (i = 0; i < count; i++)
    {
        if (ret > arr[i])
            ret = arr[i];   //遇到更小的就将值赋给ret
    }
    return ret; //返回最小值
}

上面的方法写起面临一个问题，如果栈中元素个数很多（或频繁变化），则这里会耗费时间。考虑题目中所要求栈的各个操作的时间复杂度是 O(1) ，空间复杂度是O(n) ，空间复杂度满足，时间复杂度不满足。时间复杂度O(1）的意思是，无论栈中有多少个元素，花费的时间都是固定的。

基于以上考虑，我们改变策略，在每次压栈的时候就判断现在的最小值，这样每次压栈都会更新最小值。由于每次压栈是整型变量，则这个最小值也可以用int类型表示。

如果用一个整型变量记录最小值，则又面临一个问题。当现在已有10个元素，第10个元素是20，10个元素中最小值是-5，下一个压入元素是-20，这时新的最小值会更新为-20。如果下一个操作是弹出栈顶元素，则最小值应该是-5，可现在-20是最小值，如果舍弃，则丢失了之前的-5。若要记录两个最小值，那再之前的最小值也会出现丢失现象。

因此，我们需要一个跟随栈中元素变化的最小值，这里我选择再建立一个相同容量的数组，用来记录每次压入新元素时的最小值。这样弹出栈顶元素后，最小值数组的前一个数就是之前的最小值。

代码如下：

//题目考察的是压栈、出栈操作
//由于要记录栈中的数据，这里通过全局变量实现。

int arr[300] = { 0 }, count = 0, arr_min[300] = {0};
//由于题中操作数量<=300，创建数组arr，包含300个int类型元素；count为数组中元素计数；
//由于题中元素绝对值<=10000，故创建arr_min数组记录数组最小元素。
//这里arr_min使用数组是考虑到每次压栈最小值都可能变化，每次出栈最小值也可能变化。

void push(int value)    //按题意，push是压栈操作，即将输入值压入栈中
{
    if (count >= sizeof(arr))   //先判断栈中元素是否够300个，超出则直接返回，不压入数据
        return;
    arr[count] = value;   //栈中元素不足300个，则将value值压入数组中
    if (count == 0)       //栈中元素数为0，则将第一个数付给最小值。
    {
        arr_min[count++] = value;
        return;
    }
    if (arr_min[count - 1] > value)    //如果之前的最小值大于压入值，则将value赋值给arr_min[count-1]，记录新的最小值
        arr_min[count] = value;
    else                               //压入值不大于之前的最小值，则最小值不变
        arr_min[count] = arr_min[count - 1];    
    count++;
}

void pop() //按题意，pop是弹出操作，即将栈顶的元素弹出
{
    if (count <= 0)     //先判断栈中还有没有元素，没有元素则直接返回
        return;
    count--;   //数组中记录元素个数为count，count--即将栈顶数据弹出；

}

int top()   //按题意，top是获取栈顶元素
{
    return arr[count - 1];  //返回栈顶元素
}


int min()   //按题意，min是获取最小值
{
    return arr_min[count-1]; //返回当前栈中的最小值
}

按以上代码，每一个函数的时间复杂度都是固定值，满足题目要求。

查看全文

http://www.kler.cn/a/283977.html