开发笔记:设计一个获取最小值时间复杂度为O的栈

篇首语：本文由编程笔记#小编为大家整理，主要介绍了设计一个获取最小值时间复杂度为O的栈相关的知识，希望对你有一定的参考价值。

【题目】

• 实现一个栈，在实现栈的基本功能的前提下，再实现返回最小元素的操作。

【要求】

• pop、push、getMin操作的时间复杂度都是O(1)


• 设计的类可以使用现成的栈结构。

【分析】

• 想要使得获取最小值的时间复杂度为O(1),最简单的方法就是提前将最小值记录下来，当我们需要获取时便可直接获取


• 栈的特点就是先进后出。它的操作具有一定规律，这使得我们可以很好的记录最小值。


• 很容易就能够想到“双栈”来实现

【实现】

• 实现语言：C++


• 源代码如下：

#include<iostream>
#include
using namespace std;
#define Error -1
// 一个有获取最小值功能的特殊栈，获取最小值的时间复杂度为O(1)
class GetMinStack
{
private:
stack m_BasicStack; //主栈
stack m_MinNumStack; //最小值栈

public:
void push(int value) //入栈
{
if(m_BasicStack.empty()) //如果栈中无数据
m_MinNumStack.push(value);
else if(value<=m_MinNumStack.top()) //如果入栈的值比当前的最小值还要小
m_MinNumStack.push(value);

m_BasicStack.push(value);
}

int pop()
{
if(m_MinNumStack.empty())
{
//不可出栈
cout<<"您操作的栈为空"< return Error;
}

int temp=m_BasicStack.top();
m_BasicStack.pop();
if(temp==m_MinNumStack.top())
m_MinNumStack.pop();

return temp;
}

int getMin()
{
if(m_MinNumStack.empty())
{
//不可出栈
cout<<"您操作的栈为空"< return Error;
}
return m_MinNumStack.top();
}
};
int main()
{
GetMinStack test;
test.push(5);
test.push(8);
test.push(4);
test.push(10);

cout<<"该栈最小的数为："<}


• 运行截图