学步园

本文参考了网上有名的帖子微软等公司数据结构+算法面试100题系列

//c++编写<br /> //多加一个辅助栈，栈顶为当前最小值，入栈时，比较入栈数据与辅助栈的栈顶元素的大小，要是<=辅助栈栈顶元//素，则数据入栈后，也加入辅助栈。也正因为如此，主栈栈顶元素总是大于等于辅助栈的栈顶元素，出栈时，比//较栈顶元素与辅助栈的元素，相等时就都出栈，要不只有主栈出栈。</p> <p>//其中有一个困扰我的问题是，要是栈空了，再pop时，怎样返回出错信息？怎么知道是出错信息还是出栈的元素//呢？</p> <p>#include<iostream><br /> using namespace std;</p> <p>#define MAXLENGTH 10</p> <p>class minStack<br /> {<br /> int* pStackArray; //主栈<br /> int* pMinStack; // 辅助栈<br /> int sTop,mTop; //主栈栈顶与辅助栈栈顶</p> <p>//构造函数，初始化数据<br /> public: minStack()<br /> {<br /> pStackArray = new int[MAXLENGTH];<br /> pMinStack = new int[MAXLENGTH];<br /> sTop = mTop = -1;<br /> }<br /> //忘了写析构函数，要有人看着篇文章，就自己写一个吧。</p> <p> bool isEmpty(){</p> <p> if(-1 == sTop)<br /> return true;<br /> else return false;<br /> }<br /> bool isFull(){</p> <p> if(MAXLENGTH - 1 == sTop)<br /> return true;<br /> else return false;<br /> }<br /> void push(int n){</p> <p> if(!isFull()) {</p> <p> pStackArray[++sTop] = n;<br /> if(isEmpty()) pMinStack[++mTop] = n;<br /> else if(n <= pMinStack[mTop]) pMinStack[++mTop] = n;<br /> }<br /> }<br /> int pop(){</p> <p> if(!isEmpty()){</p> <p> if(pStackArray[sTop] == pMinStack[mTop]) mTop--;</p> <p> sTop--;<br /> return pStackArray[sTop+1];<br /> }<br /> }<br /> int getTop(){</p> <p> if(!isEmpty()) return pStackArray[sTop];<br /> }<br /> int getMin(){</p> <p> if(!isEmpty()) return pMinStack[mTop];<br /> }<br /> };</p> <p>//main元素是我自己随便写的，写的很烂，自己可以写好一点，好好测试一下这个类有什么问题，麻烦也给我说<br /> //一声。</p> <p>int main()<br /> {<br /> minStack minstack;<br /> minstack.push(1);<br /> minstack.push(2);<br /> minstack.push(0);<br /> minstack.push(3);</p> <p> int i = 4;<br /> while(i > 0){</p> <p> cout << minstack.pop() << " ";<br /> cout << minstack.getMin() << endl;<br /> i--;<br /> }<br /> return 0;<br /> }