【栈和队列面试题】实现一个栈，要求实现Push(出栈)、Pop(入栈)、Min(返回最小值)的时间 复杂度为O(1)

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

 问题描述：实现一个栈，要求Push（入栈），Pop（出栈），Min（返回最小值的操作）的时间复杂度为O（1）

//MinStack.h
#pragma once#include "Stack.h"
#include <assert.h>//最小栈
// 初始化
// Push/Pop/Top/Min	要求 O(1)
typedef struct MinStack {Stack stackNormal;   //保存正常序列Stack stackMin;		 //保存当前最小数
}MinStack;void MinStackInit(MinStack* pMS);
void MinStackPush(MinStack* pMS, StackDataType data);
void MinStackPop(MinStack* pMS);
StackDataType MinStackTop(MinStack* pMS);
StackDataType MinStackMin(MinStack* pMS);
void TestMinStack();

//MinStack.c
#include "Min栈.h"
#include "Stack.h"
#include "stdio.h"void MinStackInit(MinStack* pMS)
{StackInit(&(pMS->stackMin));StackInit(&(pMS->stackNormal));
}
void MinStackPush(MinStack* pMS, StackDataType data)
{//正常序列栈，正常入站即可StackPush(&(pMS->stackNormal), data);//最小栈入栈if (StackIsEmpty(&(pMS->stackMin))) {StackPush(&(pMS->stackMin), data);return;}if (data < getTop(&(pMS->stackMin))) {StackPush(&(pMS->stackMin), data);}
}
void MinStackPop(MinStack* pMS)
{if (getTop(&pMS->stackMin) == getTop(&(pMS->stackNormal))) {StackPop(&(pMS->stackMin));}StackPop(&(pMS->stackNormal));}
StackDataType MinStackTop(MinStack* pMS)
{return getTop(&(pMS->stackNormal));
}
StackDataType MinStackMin(MinStack* pMS)
{return getTop(&(pMS->stackMin));
}//测试函数
void TestMinStack()
{MinStack stack;MinStackInit(&stack);StackDataType numbers[] = { 5, 7, 4, 3, 1, 6, 2 };for (int i = 0; i < 7; i++) {MinStackPush(&stack, numbers[i]);printf("Top = %d, Min = %d\n", MinStackTop(&stack), MinStackMin(&stack));}
}

 

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

---