第三章 栈和队列 ——栈（1）
一、概念导入
栈和队列本质是一种操作受限的线性表
栈在计算机的实现有多种方式：
◆ 硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快；
◆ 软堆栈：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有动态方式和静态方式两种。
二、栈的基本概念
1 栈的概念 栈(Stack)：
是限制在表的一端进行插入和删除操作的线性表。
又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom)：是固定端，又称为表头。
空栈：当表中没有元素时称为空栈。
设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。
栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。
即栈的修改是按后进先出的原则进行的。
2 栈的抽象数据类型定义
ADT Stack{ 数据对象：D ={ ai|ai∈ElemSet, i=1,2,…,n，n≥0 }
数据关系：R ={
基本操作：初始化、进栈、出栈、取栈顶元素等 } ADT Stack
常用的栈运算：
StackEmpty(S)：
测试栈S是否为空
StackFull(S)：测试栈S是否已满
StackTop(S)：返回栈S的栈顶元素
Push(x,S)：在栈S的栈顶插入元素x，简称入栈
Pop(S)：删除并返回栈S的栈顶元素，简称出栈或抛栈