栈

1.基础知识

后进先出。STL中与队列对应的类模板为stack ，常用操作：top()返回栈顶元素；push()向栈顶插入元素；pop()删除栈顶元素；empty()检查容器是否为空；size()返回容器的元素数。所有操作都在 O(1) 时间内完成。 关于栈的实现方式,详见: 栈与队列-顺序栈与链栈类模板的实现（数据结构基础 第3周）

2.应用:栈的压入、弹出序列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5 是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列， 但 4、5、3、1、2 就不可能是该压栈序列的弹出序列。 思路分析： 建一个栈。 步骤一：开始，先放入栈中一个元素； 步骤二：然后比较栈顶元素与待出栈元素是否相同，若相同则出栈，不同则继续往栈中放入元素，直到全部元素均已放入栈中； 步骤三：比较栈顶元素与待出栈元素是否相同，若相同则出栈，不同则由于此时已没有新元素可放入栈中，因此表明出栈顺序不合理。若栈中所有元素均可成功出栈，证明出栈顺序合理。（对于给定的进栈和出栈序列，栈的操作具有唯一性。） 代码实现

int isPopOrder(const vector<int> pushArray, const vector<int> popArray) { if(pushArray.size() != popArray.size()) return 0; if(pushArray.empty()) return 1; stack<int> s; s.push(pushArray.at(0)); int size=pushArray.size(); int indexOfInput=1; int indexOfOutput=0; while(indexOfInput<size){ if(s.top()==popArray.at(indexOfOutput)) { s.pop(); indexOfOutput++; } else { s.push(pushArray.at(indexOfInput)); indexOfInput++; } } while(!s.empty()) { if(s.top() == popArray.at(indexOfOutput)) { s.pop(); indexOfOutput++; } else{ return 0; } } return 1; }

测试

vector<int> v1 = { 1, 2, 3, 4, 5 }; vector<int> v2 = { 4, 5, 3, 2, 1 }; vector<int> v3 = { 4, 5, 3, 1, 2 }; vector<int> v4 = {4}; vector<int> v5 = {4}; vector<int> v6 = {5}; vector<int> v7 = {4, 5}; vector<int> v8; test(v1, v2); //功能测试 test(v1, v3); test(v4, v5); //边界测试 test(v4, v6); test(v4, v7); //负面测试 test(v8, v8);

3.应用:包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度均为O(1). 分析：一句话，每压入一个数，都把当前最小值（之前的最小元素和新压入栈的元素两者的较小值）保存在另一个辅助栈里。 代码实现 代码中，m_data是数据栈，而m_min是辅助栈。由于程序中使用const较多，在代码中对其做了说明。

//在一个函数声明中，const可以修饰形参，表明它是一个输入参数，在函数内部不能改变其值； void StackWithMin::push(const int &value) { m_data.push(value); if(m_min.empty()) { m_min.push(value); } else { int preMin=m_min.top(); if(preMin<value) m_min.push(preMin); else m_min.push(value); } } void StackWithMin::pop() { if(!m_data.empty() && !m_min.empty()) { m_data.pop(); m_min.pop(); } else { throw "error"; } } //对于类的成员函数，若指定其为const类型，则表明其是一个常函数，不能修改类的 成员变量； //对于类的成员函数，有时候必须指定其返回值为const类型，以使得其返回值不为“左值” //返回值为引用，即没有复制返回值，返回的是对象本身。注意这个对象不能使局部变量，否则函数返回时就被释放了。 const int& StackWithMin::min() const { if(!m_min.empty()) return m_min.top(); else throw "error"; }