实现一个栈，要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间 复杂度为O(1)

本文主要是介绍实现一个栈，要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间 复杂度为O(1)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实现一个栈，要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间
复杂度为O(1) ，要求时间复杂度为O（1），我们可以在一个栈里定义两个数组，一个数组_array用来存放数据，另一个数组_min用来存放最小值，当栈为空的时候首先入栈第一个数，在两个数组分别存放这个数，当下一个数入栈时，将其存放到数组_array中，然后再和数组_min中最顶处元素比较，若小于该数，则存放进去（即入栈），若大于或等于该数则将较小的数存放进去，依次进行。出栈时则正常删除栈顶元素。这样我们就可以满足时间复杂度为O(1)的情况下实现返回最小值。

代码实现：

#include<stdio.h>
#include<windows.h>
#include<malloc.h>
#include<assert.h>typedef int DataType;typedef struct Stack
{DataType* _array;DataType* _min;size_t _top; //栈顶 size_t _end;
}Stack;void MinStackPush(Stack *s,DataType x);
void MinStackPop(Stack *s);
DataType MinStack(Stack *s);

#define _CRT_SECURE_NO_WARNINGS 1
#include"MinStack.h"
void StackInit(Stack* s)
{s->_array = (DataType*)malloc(10 * sizeof(DataType));s->_min = (DataType*)malloc(10 * sizeof(DataType));if (s->_array&&s->_min){s->_end = 0;s->_top = 0;}
}
void MinStackPush(Stack *s, DataType x)
{assert(s);if (s->_top == 0){s->_array[s->_top] = x;s->_min[s->_top] = x;s->_top++;}else{if (x > s->_array[s->_top - 1]){s->_array[s->_top] = x;s->_min[s->_top] = s->_min[s->_top - 1];s->_top++;}else{s->_array[s->_top] = x;s->_min[s->_top] = x;s->_top++;}}
}
void StackPrint(Stack *s)
{assert(s);size_t size = s->_top - s->_end;int i = 0;for (i = 0; i < (int)size; i++){printf("%d ", s->_array[i]);}printf("\n");for (i = 0; i < (int)size; i++){printf("%d ", s->_min[i]);}printf("\n");
}
void MinStackPop(Stack *s)
{s->_top--;
}
DataType MinStack(Stack *s)
{return s->_min[s->_top-1];
}
int main()
{Stack s;DataType m = 0;StackInit(&s);MinStackPush(&s, 2);MinStackPush(&s, 1);MinStackPush(&s, 1);MinStackPush(&s, 4);MinStackPush(&s, 5);//MinStackPop(&s);StackPrint(&s);m = MinStack(&s);printf("%d\n", m);system("pause");return 0;
}

这篇关于实现一个栈，要求实现Push(入栈)、Pop(出栈)、Min(返回最小值)的时间 复杂度为O(1)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---