欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

实现一个栈:取栈中的最小值的时间复杂度为O(1)

程序员文章站 2022-06-03 13:32:39
...

思路:每次入栈前先找到最小的元素(每次有新元素入栈时就将新的元素假设为最小的元素min)(情况1:入栈时,栈内没有任何元素,即是一个空栈。这时候先将要入栈的元素入栈,再紧接着将最小的元素入栈;*情况2*:入栈时栈内已经有元素了,这时候将最小值min与栈顶元素相比较,如果栈顶元素比最小值还要小,则将其赋值给最小值min(min永远是最小的值)。然后先将要入栈的元素入栈再紧接着将最小值入栈。)如此一来,总是最小值最后入栈,那么取栈顶元素时,栈顶元素永远是最小的那一个
minStack.h文件

#pragma once 

typedef char minStackType;

typedef struct minStack
{
    minStackType *data;
    //有效元素个数
    int size;
    //表示data段内存中能容纳的元素个数
    int capacity;
}minStack;
//初始化函数
void minStackInit(minStack *stack);
//销毁函数
void minStackDestroy(minStack *stack);
//入栈函数
void minStackPush(minStack *stack,minStackType value);
//出栈函数
void minStackPop(minStack *stack);
//取栈顶元素函数
int minStackGetTop(minStack *stack,minStackType *value);

minStack.c文件

#include<stdio.h>
#include"minSeqStack.h"
#include<stdlib.h>

#define Test_Header printf("\n==========%s==========\n",__FUNCTION__);


//初始化函数
void minStackInit(minStack *stack)
{
    if(stack == NULL)
    {
        //非法输入
        return;
    }
    stack->size = 0;
    stack->capacity = 1000;
    stack->data = (minStackType*)malloc(stack->capacity * sizeof(minStackType));
}
//销毁函数
void minStackDestroy(minStack *stack)
{
    if(stack == NULL)
    {
        //非法输入
        return;
    }
    free(stack->data);
    stack->data = NULL;
    stack->size = 0;
    stack->capacity = 0;
}
//入栈函数
void minStackPush(minStack *stack,minStackType value)
{
    if(stack == NULL)
    {
        //非法输入
        return;
    }
    //每一次入栈前判断栈是否满了
    if(stack->size == stack->capacity)
    {
        //栈满了,没有空间可供新元素插入
        return;
    }
    //假定要插入的值就是最小的值
    minStackType min = value;
    if(stack->size == 0)
    {
        //空栈
        //每次入栈两次,最小的值总是最后入栈
        stack->data[stack->size++] = value;
        stack->data[stack->size++] = min;
    }
    //不是空栈
    else
    {
        //如果当前栈中的栈顶元素比假定的最小值还要小
        if(min > stack->data[stack->size-1])
        {
            //改变最小值
            min = stack->data[stack->size-1];
        }
        //先将value入栈,再将最小值入栈
        stack->data[stack->size++] = value;
        stack->data[stack->size++] = min;
    }
}
//出栈函数
void minStackPop(minStack *stack)
{
    if(stack == NULL)
    {
        //非法输入
        return;
    }
    if(stack->size == 0)
    {
        //空栈,没有元素可以出栈
        return;
    }
    //不是空栈
    else
    {
        //此时需要出栈两个元素才会将我们最后插入的元素(包括一个新的值和最后插入的最小的值)出栈
        stack->size -= 2;
    }
}
//取栈顶元素函数,成功取到栈顶元素就返回1,否则返回0
int minStackGetTop(minStack *stack,minStackType *value)
{
    if(stack == NULL)
    {
        //非法输入
        return 0;
    }
    if(stack->size == 0)
    {
        //空栈
        return 0;
    }
    //不是空栈
    *value = stack->data[stack->size-1];
    return 1;
}
void Print(minStack *stack,const char *msg)
{
    printf("[%s]\n",msg);
    if(stack == NULL)
    {
        //非法输入
        return;
    }
    if(stack->size == 0)
    {
        //空栈
        return;
    }
    int i = 0;
    for(;i < stack->size;i++)
    {
        printf("%c ",stack->data[i]);
    }
    printf("\n");
}


void TestMinSeqStack()
{
    Test_Header;
    minStack stack;
    //初始化栈并测试
    minStackInit(&stack);
    printf("expected size = 0,capacity = 1000,actual size = %d,capacity = %d\n\n",stack.size,stack.capacity);
    //入栈函数测试
    minStackPush(&stack,'x');
    minStackPush(&stack,'y');
    Print(&stack,"入栈2个元素:x y");
    //以下为取栈顶元素函数测试(栈顶元素总是最小值)
    minStackType value;

    int ret = minStackGetTop(&stack,&value);
    printf("expected ret = 1,actual ret = %d\n",ret);
    printf("expected min = x,actual min = %c\n\n",value);

    minStackPush(&stack,'g');
    Print(&stack,"再入栈一个元素:g");
    ret = minStackGetTop(&stack,&value);
    printf("expected ret = 1,actual ret = %d\n",ret);
    printf("expected min = g,actual min = %c\n\n",value);

    minStackPush(&stack,'w');
    Print(&stack,"再入栈一个元素:w");
    ret = minStackGetTop(&stack,&value);
    printf("expected ret = 1,actual ret = %d\n",ret);
    printf("expected min = g,actual min = %c\n\n",value);
    //出栈函数测试
    minStackPop(&stack);
    minStackPop(&stack);
    minStackPop(&stack);
    minStackPop(&stack);
    Print(&stack,"将所有元素出栈");
    //空栈取栈顶元素测试
    ret = minStackGetTop(&stack,&value);
    printf("expected ret = 0,actual ret = %d\n\n",ret);
    //销毁栈
    minStackDestroy(&stack);
    printf("expected size = 0,capacity = 0,actual size = %d,capacity = %d\n\n",stack.size,stack.capacity);
}
//主函数调用测试函数
int main()
{
    TestMinSeqStack();
    return 0;
}

测试结果如下图:实现一个栈:取栈中的最小值的时间复杂度为O(1)