首页 > 代码库 > 包含min函数的栈
包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。
分析：当一个栈解决不了问题的时候我们就可以考虑采用辅助栈。
每次第二个栈一直是保存所定义栈中最小的元素，每次入栈的时候，辅助栈都进行比较保存最小的元素。
先在头文件定义：
typedef char ElemType;class StackWithMin{public: StackWithMin (); void push(const char & ); void pop(char &);bool isEmpty();private: SeqStack *m_data; SeqStack *m_min;};
接下来在源文件中实现
//初始化StackWithMinStackWithMin::StackWithMin () { m_data=InitStack(); m_min=InitStack();}//push,如果比m_min的栈顶小，就将value压进去void StackWithMin::push(const ElemType & value){ //每次都对m_data和m_min都进行操作 Push(m_data,value); if(m_min->top==-1||value<m_min->data[m_min->top]) Push(m_min,value); else Push(m_min,m_min->data[m_min->top]);}//popvoid StackWithMin::pop(ElemType & value){ assert(m_data->top>=0&&m_min->top>=0); Pop(m_data,value); Pop(m_min,value); }//判断是否为空bool StackWithMin::isEmpty(){ if (m_data->top==-1||m_min->top==-1) return true; return false; }
main.cpp实现
StackWithMin stack; cout<<"包含min函数栈输入元素，并按<ENTER>结束"<<endl; ElemType ch,ch_result; ch=getchar(); while(ch!=‘\n‘) { stack.push(ch); ch=getchar(); } while(!stack.isEmpty()) { stack.pop(ch_result); cout<<ch_result<<" "; }
结果：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。