数据结构－栈

1.容器
容器用于容纳元素集合，并对元素集合进行管理和维护．
传统意义上的管理和维护就是：增，删，改，查．
我们分析每种类型容器时，主要分析其增，删，改，查动作实现，及复杂度．

2.栈
2.1.结构
2.1.1.图解
栈是容器类型．
但栈不同于数组，链表这一类的容器．数组和链表这类容器规定了对容器内元素的组织方式，但栈这类容器并不限定容器内元素的组织方式．它只是限制了容器增加元素，删除元素的行为．

由于栈对容器内元素组织方式无要求，所以，结构方面依赖实现栈的底层容器．采用数组来实现的栈，结构就是数组．采用链表来实现的栈，结构就是链表．采用其他容器来实现的栈，结构为对应容器的结构．

2.2.动作
2.2.1.增
栈中插入新元素．
原则上新元素只能插入到容器最后元素之后．
新增过程可参考实现栈的容器中尾部新增新元素的情况．
2.2.2.删
栈中删除元素．
原则上只能删除尾元素．
删除过程可参考实现栈的容器中移除尾部元素的情况．
2.2.3.查
栈一般不用支持查找，只要提供访问尾元素的方法就行了．
2.2.4.改
栈中修改元素，只能修改尾元素．
修改过程可参考实现栈的容器中修改尾部元素的情况．

2.3.时间复杂度
评价容器的依据一个是其占据的线性空间，一个是操作执行的时间复杂度．
对基于数组或链表实现的栈其各个操作时间复杂度为：
(1). 增：Θ(1) (只能在尾元素之后新增)
(2). 删：Θ(1) (只能移除尾元素)
(3). 查：Θ(1) (只能查询尾元素)
(4). 改：Θ(1) (只能修改尾元素)