数据结构 栈和队列面试题 实现一个栈
实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间
复杂度为O(1)
实现一个栈的出栈入栈其实很简单，可是要求Min（返回最小值）的时间复杂度为O（1）,就需要换个思路来思考
时间复杂度为O（1）,我们可以通过双栈来实现，或者说一个栈里有两个数组存放数据，一个array来存放入栈的元素，一个min来存放当前栈内最小值，入栈的时候往array和min里面同时入数据，出栈时候两边同时出数据
这样的结构当我们需要Min返回最小值时候只要访问min的栈顶元素即可，这样就可以达到时间复杂度为O（1）的要求
所以我们的Stack结构体：
typedef struct Stack
{
DataType* _array;
DataType* _min;
size_t _top;
size_t _end;
}Stack;
Stack.h:
#pragma once
#define NUM 50
typedef int DataType;
typedef struct Stack
{
DataType* _array;
DataType* _min;
size_t _top;
size_t _end;
}Stack;
void StackInit(Stack* s);//栈的初始化
void StackPush(Stack* s, DataType x);//入栈
void StackPop(Stack* s);//出栈
DataType StackTop(Stack* s);//返回栈顶值
DataType StackMin(Stack* s);//返回最小值
由于我们入栈时候要往min里面入最小值，所以入栈时候要进行最小值的判断
Stack.c:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"Stack.h"
void StackInit(Stack* s)//栈的初始化
{
s->_array = (DataType*)malloc(sizeof(DataType)*NUM);
s->_min = (DataType*)malloc(sizeof(DataType)*NUM);
assert(s->_array && s->_min);
s->_top = s->_end = 0;
}
void StackPush(Stack* s, DataType x)//入栈
{
assert(s);
if (s->_top == NUM)
{
printf("stack overflow");//栈溢出
return;
}
if (s->_top == 0)
{
s->_min[s->_top] = x;
s->_array[s->_top] = x;
}
else
{
if (s->_min[s->_top - 1] > x)
{
s->_min[s->_top] = x;
}
else
s->_min[s->_top] = s->_min[s->_top - 1];
}
s->_array[s->_top] = x;
s->_top++;
}
void StackPop(Stack* s)//出栈
{
assert(s);
s->_top--;
}
DataType StackMin(Stack* s)//返回最小值
{
return s->_min[s->_top-1];
}
DataType StackTop(Stack* s)//返回栈顶值
{
return s->_array[s->_top-1];
}
int main()
{
Stack S;
Stack* p = &S;
StackInit(&S);
StackPush(&S, 5);
printf("top: %d ",StackTop(&S));
printf("Min: %d\n", StackMin(&S));
StackPush(&S, 3);
printf("top: %d ", StackTop(&S));
printf("Min: %d\n", StackMin(&S));
StackPush(&S, 4);
printf("top: %d ", StackTop(&S));
printf("Min: %d\n", StackMin(&S));
StackPush(&S, 2);
printf("top: %d ", StackTop(&S));
printf("Min: %d\n", StackMin(&S));
StackPush(&S, 6);
printf("top: %d ", StackTop(&S));
printf("Min: %d\n", StackMin(&S));
StackPush(&S, 1);
printf("top: %d ", StackTop(&S));
printf("Min: %d\n", StackMin(&S));
system("pause");
return 0;
}