栈 -- 顺序栈、链式栈的实现 及其应用（函数栈，表达式求值，括号匹配）

我们使用浏览器的时候经常会用到前进、后退功能。
依次访问完一串页面 a – b – c之后点击后退功能，则能够依次看到c – b – a的页面。
但是这个过程中，如果后退到了页面b,点击了新的页面d,则再点击前进无法回到页面c。
这个过程的实现就是我们 “栈”数据在其中起作用了。

实现

栈的基本实现有如下两种：

• 顺序栈 – 基于数组的实现
• 链式栈 – 基于链表的实现

顺序栈实现

#include <iostream>
#include <assert.h>using namespace std;class ArrayStack{
private:int size; // stack sizeint count; // stack element countint *arr; // 数组，保存栈中元素public:ArrayStack(int n) {size = n;count = 0;arr = new int[n];}ArrayStack(ArrayStack &obj) = delete;~ArrayStack() {delete []arr;}; //析构掉new出来的数组bool push(int element); // push元素到栈中int pop();  //从栈中弹出元素，并返回弹出到数值bool isEmpty(); //栈是否为空void show();    //打印栈中元素int get_size() { return size;} //获取栈的大小
};bool ArrayStack::push(int element) {assert(count != size );arr[count] = element;count ++;return  true;
}int ArrayStack::pop() {assert(count != 0);int tmp = arr[count];count --;return  tmp;
}bool ArrayStack::isEmpty() {if(count != 0) {return true;}return  false;
}void ArrayStack::show() {if(!this->isEmpty()) {cout << "stack is empty " << endl;}cout << "stack size is: " << count << " element is :";for (int i = 0;i < count; ++i) {cout << arr[i] << " ";}cout << endl;
}typedef  struct Link{int val;struct Link *next;
}list;class ListStack {
private:int size; // stack的大小int count; // stack的长度list *head; // 链表public:};int main() {ArrayStack st(5);int ele;int len = st.get_size();while (len != 0) {cin >> ele;st.push(ele);len --;}st.show();st.pop();st.show();st.pop();st.show();return 0;
}

输出如下：

#输入 
2 3 4  5 6#输出 
stack size is: 5 element is :2 3 4 5 6 
stack size is: 4 element is :2 3 4 5 
stack size is: 3 element is :2 3 4 

链式栈实现

#include <iostream>
#include <assert.h>using namespace std;/*链式栈的功能实现*/
template <class T> //模版类，用来创建任意数据类型的栈
class ListStack {
private:int size; // stack的大小int count; // stack的长度/*链式栈的数据结构*/struct Link{T val;struct Link *next;Link(T x = T()): val(x), next(nullptr){}};Link *head; // 链表public:ListStack(){} //默认构造函数ListStack(int n):size(n),count(0){head = new Link;}~ListStack();bool push(T x); //向栈中push元素T pop(); //pop元素bool isEmpty();void show();int get_size() { return size;}
};template <class T>
ListStack<T>::~ListStack() {Link *p, *tmp;p = head;while(p->next) {tmp = p -> next;p -> next = p -> next -> next;delete tmp;}delete  head;size = 0;count = 0;
}template <class T>
bool ListStack<T>::push(T x) {if(count == size) {return  false;}auto *p = new Link;p ->val = x;p -> next = head -> next;head -> next = p;count ++;return  true;
}template <class T>
T ListStack<T>::pop() {if (count == 0 || head == NULL) {return -1;}auto *p = head -> next;T val = p -> val;head -> next = head -> next -> next;count --; // 栈中元素个数自减delete p; // 需要将pop的元素空间释放return val;
}template <class T>
bool ListStack<T>::isEmpty() {return count == 0;
}template <class T>
void ListStack<T>::show() {if(isEmpty() || head == NULL) {cout << "stack is empty" << endl;}auto *p = head -> next;cout << "stack size is : " << count << " element is :";while(p) {cout << p -> val << " ";p = p -> next;}cout << endl;
}
int main() {ListStack<int> *st = new ListStack<int>(5); //初始化链式栈的大小为5int ele;int len_stack = st -> get_size();cout << "stack length is " << len_stack << endl;while(0 != len_stack) {cin >> ele;st->push(ele);len_stack --;}st->show();st->pop();st->show();st->pop();st->show();return 0;
}

输出如下:

stack length is 5#输入元素
2 3 4 5 6#输出
stack size is : 5 element is :6 5 4 3 2 
stack size is : 4 element is :5 4 3 2 
stack size is : 3 element is :4 3 2 

应用

函数栈 的应用

操作系统在进程运行的时候会为进程中的每个线程分配独立的内存空间，这块内存被组织成独立的栈的数据结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，这个函数对应的栈帧就会出栈。
如代码:

int main() {int a = 1;int ret = 0;int res = 0;ret = add(3, 5); res = a + ret; printf("%d", res);return 0;
} 
int add(int x, int y) { int sum = 0;sum = x + y;return sum;
} 

从代码中可以看到main()调用add()函数，获取计算结果，并与临时变量a相加，最后打印res的数值。
栈帧的组织图基本如下:

表达式求值中 的应用

要求支持带括号的四则元算，可以使用数据栈和符号栈进行实现
过程如下：

实现过程如下：

#include <iostream>
#include <algorithm>
#include <stack>
#include <map>using namespace std;void print_erro(string s,int line) {cout << s <<" " << line << endl;exit(-1);
}void calculate(stack<int> &num_stak, stack<char> &oper_stack) {int num1;int num2;int result;num1 = num_stak.top();num_stak.pop();num2 = num_stak.top();num_stak.pop();if (oper_stack.top() == '+') {result = num1 + num2;} else if (oper_stack.top() == '-') {result = -(num1 - num2);} else if (oper_stack.top() == '*') {result = num1 * num2;} else if (oper_stack.top() == '/') {if (num1 == 0) {print_erro("divide num is 0 \n", __LINE__);}result = num2 / num1;} else {print_erro("operator failed\n", __LINE__);}oper_stack.pop();num_stak.push(result);
}int state_change(string s) {static const int BEGIN_STATE = 0;static const int NUM_STATE = 1;static const int OPE_STATE = 2;int STATE = BEGIN_STATE;map<char,int> prio;stack<int> num_stack;stack<char> oper_stack;int cacl_flag = -1;int number = 0;prio['+'] = 1;prio['-'] = 1;prio['*'] = 2;prio['/'] = 2;prio['('] = 3;int i;if (s.empty()) {print_erro("string is empty\n",__LINE__);}for(int i = 0;i < s.size(); ++i) {if (s[i] == ' ') {continue;}switch (STATE){case BEGIN_STATE:if (s[i] >= '0' && s[i] <= '9') {STATE = NUM_STATE;} else if(s[i] == ')'){print_erro("string is not leagal\n",__LINE__);} else {STATE = OPE_STATE;}i--;break;case NUM_STATE:if (s[i] >= '0' && s[i] <= '9') {number = number*10 + s[i] - '0';} else {num_stack.push(number);if (cacl_flag == 2) {calculate(num_stack,oper_stack);}STATE = OPE_STATE;number = 0;i--;}break;case OPE_STATE:if(prio[s[i]] == 1) {oper_stack.push(s[i]);cacl_flag = 1;} else if(prio[s[i]] == 2) {oper_stack.push(s[i]);cacl_flag = 2;} else if (prio[s[i]] == 3) {cacl_flag = 3;STATE = NUM_STATE;break;} else if (s[i] == ')') {calculate(num_stack,oper_stack);break;} else if(s[i] >= '0' && s[i] <= '9') {STATE = NUM_STATE;i--;} else {print_erro("string is not leagal \n",__LINE__);}break;default:break;}}if (number != 0) {num_stack.push(number);calculate(num_stack,oper_stack);}if (number == 0 && num_stack.empty()) {return 0;}while(!oper_stack.empty() && num_stack.size() != 1) {calculate(num_stack,oper_stack);}if (!oper_stack.empty()) {print_erro("string is not leagal", __LINE__);}return num_stack.top();
}int main() {string s;cout << "input the string " << endl;cin >> s;int a = state_change(s);cout << "calcute the result is " << a << endl;return 0;
}

编译运行如下:

input the string 
(((1+5)/2+6*9+10)-(2+3)*100)
calcute the result is -433

括号匹配中 的应用

给定一个由括号组成的字符串，判断该字符串是否是一个合法的括号序列
假设给定的字符串中只包含三种括号：花括号{}，方括号[]，圆括号()，它们可以任意嵌套，如：{[{}]}或则[{()}([])]都为合法括号，{[}()]或则[({)]为不合法括号。

这个时候我们可以使用栈来保存未匹配的左括号，基本实现过程如下：

• 从左到右依次扫描字符串，当遇到左括号的时候入栈
• 遇到右括号 则从 栈顶取一个左括号，如果能够和当前右括号匹配(比如"(“和”)“匹配，”[“和”]“匹配，”{“和”}"匹配)，则栈顶左括号可以从栈顶弹出。
• 继续扫描后续字符串，如果遇到不能配对的右括号，或者栈中没有数据，则说明当前括号序列不合法。

实现如下:

bool isValid(string s) {if(s.length() == 0) return true;stack<char> S;for (int i = 0;i < s.length(); ++i) {switch(s[i]) {case ')':{if(!S.empty()) {if(S.top() == '('){S.pop();} else {return false;}}else {return false;}break;}case ']':{if(!S.empty()) {if(S.top() == '['){S.pop();} else {return false;}}else {return false;}break;                    }case '}':{if(!S.empty()) {if(S.top() == '{'){S.pop();} else {return false;}}else {return false;}break;                    }case '(':{S.push(s[i]);break;}case '[':{S.push(s[i]);break;}case '{':{S.push(s[i]);break;}}}if (S.size() != 0) {return false;}return true;
}