《程序员代码面试指南》第一章 栈和队列(1)C++实现
设计一个带有getMin功能的栈
【题目】
构造一个特殊的栈，除了具有栈的基本功能，还能返回栈中最小元素。
【要求】
1.pop、push、getMin操作的时间复杂度都是O(1)。
2.设计的栈类型可以使用现成的栈结构
【解法】
设计两个栈，一个是基本栈，用来保存数据；另一个用来记录栈中的最小值，随着基本栈中元素pop/push而改变。
【具体实现】
1.声明
#ifndef _GETMINSTACK_
#define _GETMINSTACK_
#include <stack>
using namespace std;
class MyStack{
public:
MyStack(){};//构造函数
~MyStack(){};//析构函数
void push(int elem);
int pop();
int getMin();
bool empty();
int top();
private:
stack<int> stackData; //私有对象不能直接访问
stack<int> stackMin;
};
#endif // _GETMINSTACK_
2.实现
#include <iostream>
#include "MyStack.h"
using namespace std;
void MyStack::push(int elem)
{
if(stackMin.empty())
{
stackMin.push(elem);
}
else if(elem<=stackMin.top())
{
stackMin.push(elem);
}
stackData.push(elem);
}
int MyStack::pop()
{
int value;
if(stackMin.empty())
{
cout<<"The stack is empty"<<endl;
}
value = stackData.top();//拼写错误：vlaue
stackData.pop();//pop是没有返回值的，因此要先top取出值，再pop
if(value==stackMin.top())
{
stackMin.pop();
}
return value;
}
int MyStack::top()
{
return stackData.top();
}
bool MyStack::empty()
{
return stackData.empty();
}
int MyStack::getMin()
{
if(stackMin.empty())
{
cout<<"The stack is empty"<<endl;
}
//else不加else？
return stackMin.top();
}
3.测试
#include <iostream>
#include "MyStack.h"
using namespace std;
int main()
{
int a[]={3,4,5,2,1,6};
MyStack s;//一个对象
for(int i = 0;i<6;i++)
{
s.push(a[i]);
cout<<"s.top() is "<<s.top()<<endl;
cout<<"s.getMin() is "<<s.getMin()<<endl;
}
cout<<"The datum in the stack is:"<<endl;
while(!s.empty())
{
cout<<s.top()<<endl;
s.pop();
}
return 0;
}
4.运行结果
【总结】
1.本题采用C++解法时，利用类的概念，相当于构造一个新的“数据类型”，其中两个私有对象分别为两个栈；成员函数中除了getMin这一显式函数外还包括有具体实现中要用到的pop、push、top、empty操作。
2.题目要求里写了可以使用现成的栈类型，因此在包含了<stack>头文件的前提下，私有对象可以直接使用stack<int>的形式构造基本栈。
3.类中成员函数的实现也可以使用了<stack>头文件中的栈基本操作。在这里需要注意的是函数的返回值问题，例如在<stack>头文件中pop函数是没有返回值的，而自己定义的pop函数为了代码的方便定义了int的返回值，因此需要注意匹配问题。
【不足】
代码中对异常情况没有增加异常处理机制，只是用了cout来说明，有待改进。
【参考资料】
1.左神的《程序员面试代码指南》第一章中“设计一个有getMin功能的栈”的第一个问题。
2.博客园Stan大神的个人博客 https://www.cnblogs.com/PrimeLife/p/5310127.html
