数据结构——栈(Stacks)

栈遵循LIFO ( last in first out) 即后入先出原则

栈结构类似于叠盘子 后叠上去的要先拿走 才能拿到下面的盘子

因此stack是一种访问受限的线性存储结构

用单向链表的结构来存储

stack类

1 class stack
2 {
3     stack();
4     bool empty() const;
5     void pop();    //移除栈顶元素
6     void push()(const T&item);//增加元素至栈顶
7     int size() const;
8     T &top() const;//返回栈顶元素 
9 }

栈的两个常见应用：

&&Run-time Stack　　运行时间栈

顺序执行活动，运行栈顶的活动，运行完毕弹出。

&&RPN or Postfix Notation

将中缀表达式转化为后缀表达式压入栈中，顺序弹出进行运算。

如：a*b+c　　-> ab*c+

　　a*(b+c)　　-> abc+*

　　a-(b-(c-d))　　-> abcd---

压入栈中时分为 数字栈 和 符号栈

符号栈：进栈与栈顶元素比较优先级。

　　　　同级则先弹出栈顶元素再新元素进栈，

　　　　优先级低则先弹出栈顶元素再与新的栈顶元素比较，

　　　　优先级高则直接入栈。

　　　　‘（’ 直接入栈，碰到 ‘）’ 则将直至 ‘（’ 的符号全部弹出。

举例：

数据结构——栈(Stacks)

原文：http://www.cnblogs.com/verlen11/p/4187697.html