基于visual Studio2013解决面试题之0203栈实现

zpjx

　　

题目


　　

解决代码及点评
/*
用模板类实现栈
*/
/* 标准输入输出流头文件 */
#include <iostream>
/* 将标准库的std命名空间下标示符提升到全局 */
using namespace std;
/* 定义栈模板库 */
template <class T>
class stack
{
public:
stack(int len = 10);  /* 构造函数，默认栈深度为10 */
~stack();/* 析构函数 */
void push(T value);/* 压栈 */
void pop();/* 弹出栈顶元素 */
void empty();/* 清空栈 */
T top();/* 获取栈顶元素 */
int size();/* 栈大小 */
T min();/*  */
private:
int ntop;/* 当前top位置 */
int len;                   /* 栈空间长度 */
T *arr;              /* 栈数据 */
int mtop;   /* 辅助栈，用来保存最小值的 */
int mlen;   /* 辅助栈长度 */
T *marr;    /* 辅助栈数据 */
};
template <class T>
stack<T>::stack(int len)
{
if (len <= 0)
{
return;
}
this->len = len;/* 初始化栈长度 */
ntop = 0;/* 注意空栈是用0表示，那么栈顶元素应该是ntop-1 */
arr = new T[len];/* 申请空间 */
/* 辅助栈的大小和栈大小相同 */
mlen = len;      //辅助栈，每次弹入数据都判断最小值，
//将最小值入辅助栈，元素出栈时也和辅助栈比较
//所以辅助栈的栈顶元素一直是最小值
mtop = 0;
marr = new T[mlen];
}
/* 析构函数，当构造函数有申请空间或者使用系统资源时，必须提供析构函数 */
template <class T>
stack<T>::~stack()
{
delete[]arr;
delete[]marr;
}
/* 压栈 */
template <class T>
void stack<T>::push(T value)
{
/* 首先判断是否有空间，没有空间则直接返回吧 */
if (ntop == len)
{
return;
}
/* 把值保存到栈顶，并将栈顶下标加1 */
arr[ntop++] = value;
// 辅助栈用来保存最小值,当辅助栈还是空的时候
// 直接入栈，如果不空，则需要比较栈顶是否大于value
if (mtop == 0)
marr[mtop++] = value;
else if (value < marr[mtop - 1])
{
marr[mtop++] = value;
}

}
/* 出栈 */
template <class T>
void stack<T>::pop()
{
// 如果栈空了，则出栈失败
if (ntop == 0)
{
return;
}
// 如果弹出的正好是最小值，那么把辅助栈先出栈
if (arr[ntop - 1] == marr[mtop - 1])
{
mtop--;
}
// 进行出栈操作
ntop--;
}
/* top，获取栈顶元素，也就是 ntop-1指示的那个值 */
template <class T>
T stack<T>::top()
{
if (ntop == 0)
{
return NULL;
}
return arr[ntop - 1];
}
/* 返回栈元素个数，正好是ntop */
template <class T>
int stack<T>::size()
{
return ntop;
}
/* 清空栈，只需要将ntop恢复成0，即可 */
template <class T>
void stack<T>::empty()
{
if (ntop == 0)
{
return;
}
ntop = 0;
mtop = 0;
}
/* 获取栈最小值，就是辅助栈的栈顶 */
template <class T>
T stack<T>::min()
{
return marr[mtop - 1];
}
/* 测试主函数 */
int main()
{
stack<int> s;
s.pop();
s.push(2);
s.push(3);
s.push(5);
s.push(1);
s.push(7);
s.pop();
s.pop();
cout << s.size();
cout << endl << s.top();
cout << endl << s.min();
system(&quot;pause&quot;);
return 0;
}

代码下载及其运行
　　代码下载地址：http://download.csdn.net/detail/yincheng01/6704519

　　解压密码：c.itcast.cn
　　

　　下载代码并解压后，用VC2013打开interview.sln，并设置对应的启动项目后，点击运行即可，具体步骤如下：
　　1）设置启动项目：右键点击解决方案，在弹出菜单中选择“设置启动项目”


　　2）在下拉框中选择相应项目，项目名和博客编号一致

　　3）点击“本地Windows调试器”运行


　　

程序运行结果