可以获取最小值的栈

2018-09-27 约 1807 字预计阅读 4 分钟

如何实现可以获取最小值的栈？

这个问题是很久之前在微信公众号上看见的一个问题，突然想起来就来操作一下。开发环境 : sublime+MinGW 先附上我自己实现的栈的结构

//定义链栈的节点的结构体 
typedef struct  StackNode
{
	int data;
	struct StackNode *next;
}StackNode,*LinkStackPtr;

//链栈的结构体
typedef struct LinkStack
{
	//栈顶
	LinkStackPtr top;
	//总数量
	int count;
}LinkStack;

//初始化栈
LinkStack *init(){
	LinkStack *stack=(LinkStack*)malloc(sizeof(LinkStack));
	if (stack==NULL)
	{
		printf("动态开辟空间失败");
	}else
		//初始化空栈
		stack->top=NULL;
		stack->count=0;
		return stack;
}

//创建节点
LinkStackPtr  creatNode(){
	LinkStackPtr stack;
	//开辟空间
	stack =(LinkStackPtr)malloc(sizeof(StackNode));
	if(stack==NULL){
		printf("动态开辟空间失败");
	}
	scanf("%d",&(stack->data));
	stack->next=NULL;
	return stack;
}

//压栈
void push(LinkStack * s){
	//创建节点
	LinkStackPtr newStack= creatNode();
	//保存当前的节点
	LinkStackPtr currentTopStack=s->top;
	//栈顶变为刚进栈的元素
	s->top=newStack;
	//连接
	newStack->next=currentTopStack;
	//数目加一
	s->count++;
}

//弹栈
void pop(LinkStack *s){
	//将栈顶弹出
	LinkStackPtr topStack=s->top;
	s->top=topStack->next;
	s->count--;
	free(topStack);
}

Solution 1：

在进栈的时候用一个变量保存当前的最小值每次进栈就会和最小值比较如果比最小值要小就会更新这个变量的值，出栈的时候比较麻烦，如果最小值被弹出去了就需要遍历整个栈来获取最小值。

Implement：

typedef struct  StackNode
{
	int data;
	struct StackNode *next;
}StackNode,*LinkStackPtr;

//链栈的结构体
typedef struct LinkStack
{
	//栈顶
	LinkStackPtr top;
	//总数量
	int count;
	//最小值
	int min;
}LinkStack;

//进栈
void push(LinkStack * s){
	//创建节点
	LinkStackPtr newStack= creatNode();
	//**********************************
	if(s->count==0){
		s->min=newStack->data;	
	}else if(s->min>newStack->data){
		s->min=newStack->data;
	}
	//*********************************
	//保存当前的节点
	LinkStackPtr currentTopStack=s->top;
	//栈顶变为刚进栈的元素
	s->top=newStack;
	//连接
	newStack->next=currentTopStack;
	//数目加一
	s->count++;
}

//弹栈
void pop(LinkStack *s){
	//将栈顶弹出
	LinkStackPtr topStack=s->top;
	//从第二个开始比较
	LinkStackPtr stackNode=topStack->next;
	//弹出去的那个节点的数据
	int min=topStack->data;
	s->top=topStack->next;
	s->count--;
	free(topStack);
	//如果弹出的是最小值就需要从当前栈顶遍历数组获取最小值
	if(min==s->min){
		min=stackNode->data;
	  do{
	  	if(min>stackNode->data){
	  		min=stackNode->data;
	  	}
		stackNode=stackNode->next;
	   }while(stackNode!=NULL);	
	}
	s->min=min;
}

这种方法进栈时间复杂度为 O(1), 但是出栈时间复杂度为 O(n). 显然不是很优雅。

Solution 2：

空间换时间利用一个辅助栈，辅助栈里面存放最小值，辅助栈进栈时判断进栈的元素和当前栈顶的元素大小跟小就可以进栈。所以最小值就是辅助栈的栈顶元素，出栈时如果出栈的元素是最小值节点那辅助栈也同时弹栈再取栈顶元素。

Implement：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义链栈的节点的结构体 
typedef struct  StackNode
{
	int data;
	struct StackNode *next;
}StackNode,*LinkStackPtr;

//链栈的结构体
typedef struct LinkStack
{
	//栈顶
	LinkStackPtr top;
	//总数量
	int count;
	//辅助栈
	struct LinkStack *mins;
}LinkStack;

//初始化栈
LinkStack *init(){
	LinkStack *stack=(LinkStack*)malloc(sizeof(LinkStack));
	if (stack==NULL)
	{
		printf("动态开辟空间失败");
	}else
		//初始化空栈
		stack->top=NULL;
		stack->count=0;
		return stack;
}

//创建节点
LinkStackPtr  creatNode(){
	LinkStackPtr stack;
	//开辟空间
	stack =(LinkStackPtr)malloc(sizeof(StackNode));
	if(stack==NULL){
		printf("动态开辟空间失败");
	}
	scanf("%d",&(stack->data));
	stack->next=NULL;
	return stack;
}

//进栈
void push(LinkStack * s){
	//创建节点
	LinkStackPtr newStack= creatNode();
	//保存当前的节点
	LinkStackPtr currentTopStack=s->top;

	//开辟空间 用于添加到辅助栈中，之前直接操作 newStack，指针地址导致后面辅助栈和主栈混合到了一起，
	LinkStackPtr minStackNode =(LinkStackPtr)malloc(sizeof(StackNode));
	if(minStackNode==NULL){
		printf("动态开辟空间失败");
	}
	minStackNode->data=newStack->data;
	minStackNode->next=NULL;

	//栈顶变为刚进栈的元素
	s->top=newStack;
	//辅助栈
	LinkStack *mins=s->mins;
	//保存辅助栈当前栈顶
	LinkStackPtr  currentMinsTop=mins->top;
	if(s->count==0){
	   mins->top=newStack;
	   newStack->next=NULL;
    }else
    	//如果进栈的元素比当前辅助栈的栈顶小
    	//相等的要进栈
    	if(newStack->data<=mins->top->data){
    		mins->top=minStackNode;
    		//连接
    		mins->top->next=currentMinsTop;
    		mins->count++;
    	}
	//连接
	s->top->next=currentTopStack;
	//数目加一
	s->count++;
}

//弹栈
void pop(LinkStack *s){
	//将栈顶弹出
	LinkStackPtr topStack=s->top;
    //辅助栈
	LinkStack * mins=s->mins;
	//保存辅助栈栈顶元素便于销毁
	LinkStackPtr minsTopStack=mins->top;
	s->top=topStack->next;
	s->count--;
	//弹出的元素是最小值
	if (topStack->data==mins->top->data)
	{
		//辅助栈同时弹栈
		mins->top=minsTopStack->next;
		mins->count--;
		free(minsTopStack);
	}
	free(topStack);
}

//遍历栈（栈顶到栈底）
void printStack(LinkStack *stack){
	//当前栈顶
	LinkStackPtr stackNode=stack->top;
	do{
		printf("%d\n",stackNode->data);
		stackNode=stackNode->next;
	}while(stackNode!=NULL);
}

int main(int argc, char const *argv[])
{
	//申明并初始化栈结构
	LinkStack *stack=init();
	//初始化这个链栈的辅助（C 语言学的不好原谅这些很奇怪的操作）
	stack->mins=init();
	push(stack);
	printf("*******进栈******\n");
	printStack(stack);
	printf("*********辅助栈*******\n");
	printStack(stack->mins);
	printf("*******最小值******\n");
	printf("%d\n", stack->mins->top->data);
	pop(stack);
	printf("*******出栈******\n");
	printStack(stack);
	printf("*******最小值******\n");
	printf("%d\n", stack->mins->top->data);
	printf("*********辅助栈*******\n");
	printStack(stack->mins);
	return 0;
}

明显这个方法进栈出栈时间复杂度都是 O(1)，空间复杂度相对会高一点，其实空间复杂度还可以优化，可以在辅助栈里面存索引，这样进栈时会避免存入相同的最小值，如 2 1 1 1 1 1 存到辅助栈就是 2 1 1 1 1 1 后面的 1 都是重复的，如果存索引就是 0 1 进栈时跟之前一样，出栈时判断索引是否和辅助栈存的索引一致，不一致就不动。这里因为这个是个链栈 , 要根据索引取值并不方便所以就不实现了。

这里我把代码全部贴上来了，C 语言确实学的不怎么样，所以里面会有一些奇怪的操作，这个算法本身很简单但是用 C 语言一实现就会有一堆问题，昨天进栈的时候一个指针把辅助栈和主栈搞混了一直有 bug, 今天早上上课才想起来，毕竟 C 语言写的少 hahahaha, 所以后面我打算以后会同时用 C 语言和 Java 都实现一遍。

目录

可以获取最小值的栈

如何实现可以获取最小值的栈？

Solution 1：

Solution 2：