栈是一种特殊的线性表,其特殊指出在于栈的存储结构比较特殊

栈是一种特殊的线性表，特殊之处在于插入和删除操作的位置受到限制，若插入和删除操作只允许在线性表的一端进行，则是栈，特点是后进先出栈的抽象数据模型:栈stack是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，允许操作的一端称为栈顶top不允许操作的一端称谓栈底Bottom，栈中插入元素操作称为入栈push，删除元素的操作称为出栈pop没有元素的栈称为空栈、例如对数据序列｛ABCD｝执行操作序列｛入栈，出栈，入栈，入栈，出栈，出栈出栈｝，出栈序列为｛BDCA｝栈机器状态如图图

4.1栈顺序栈及其状态变化由于栈的插入和删除操作只允许在栈顶进行，每次入栈元素即成为栈顶元素，每次出栈元素总是最后一个入栈元素，因此栈的特点是后进先出LastInFirstOut，就像一落盘子，每次将只有一个盘子在最上面，从最上面取走一个盘子，不能从中间插入或者插出栈的基本操作有创建栈，判断是否为空，入栈，出栈，和取出栈顶元素等栈不支持对指定位置的插入，删除等顺序栈采用顺序存储结构的栈称为顺序栈SequentialStack｝声明顺序栈如下，实现栈接口，使用顺序表作为成员变量实现栈，约定null不能入栈其中，入栈和出栈操作实现为顺序表尾部插入和尾部删除，时间复杂度为01顺序表的插入方法已经实现自动扩充数组容量，当需要扩充容量时，入栈的时间复杂度为0n栈和线性表是不同的数据抽象类型，栈概念不依赖于线性表而存在，我们只是使用顺序表进行设计，也可以使用数组实现链式栈采用连式存储结构的栈称为链式栈LinkedStack单链表结构的链式栈及入栈，出栈操作如图，设单链表不带头节点头指针top指向第一个元素节点栈顶，入栈操作是头插入，在栈顶节点之前插入节点，出栈操作是头删除，删除栈顶节点并返回栈顶元素，再使top指向新的栈顶节点a空栈声明链式栈类如下，实现栈接口使用单链表作为成员变量实现栈入栈和出栈操作实现为单链表头部插入和删除时间复杂度为

01.。