文档介绍：堆栈的逻辑结构?堆栈(也简称栈)是一个线性表,其数据元素只能从这个有序集合的同一端插入或删除,这一端称为堆栈的栈顶(top),而另一端称为堆栈的栈底(bottom)。?堆栈是限定只能在表头(或表尾)进行插入和删除运算的线性表。表头(或表尾)是开放运算的栈顶,另一端是封闭运算的栈底。?栈为后进先出表或先进后出表,简称LIFO(Last in first out)或FILO(First in last out)表。 堆栈的抽象数据类型}从堆栈中弹出元素Pop(x)向堆栈中压入元素Push(x)返回栈顶元素GetTop() 如果堆栈为满,则返回true,否则,返回falseIsFull ()如果堆栈为空,则返回true,否则,返回falseIsEmpty()构造空堆栈CreatStack()OPSet:Rset:堆栈的一端(en-1)称为的栈顶(top),而另一端(e0)称为堆栈的栈底(bottom)。Dset:是一个只能从同一端插入或删除限定性的线性表(e0,e1,…,en-1)。ADT Stack{ADT 堆栈顺序存储1. 堆栈顺序存储概念?堆栈占用的第一个存储单元的地址,就是堆栈的首地址,也是堆栈中栈底元素(e0)存放的位置。?假设堆栈中每个数据元素占用size字节空间,top指向(top=n-1)堆栈中进栈元素的栈顶元素,即栈顶元素的地址,MaxSize表示堆栈可以存储元素的最大空间。一般约定下标为0的元素空间就是栈底,这样就不再另设一变量再来记录栈底指针bottom。?利用公式:location(ei)=location(e0)+i×size求取堆栈中元素ei的地址。但是,由于堆栈是一个受限的线性表,所以,一般情况下不作取中间数据元素的运算。 堆栈的顺序存储及操作*element→top=nMaxSizee001…i…n-1…MaxSizee1eien-1图1 堆栈的顺序存储*element→top=-1MaxSize01…i…n-1…MaxSize图2 {EType*element;inttop;intMaxSize;} Stack;StackS,S1,S2;Stack是一个顺序存储的堆栈,其中element是一个一维数组,每个数组元素空间用于存放堆栈元素数据值,top指向堆栈栈顶元素,MaxSize记载堆栈可存储的最多数据元素。最后用Stack定义了三个堆栈:S,S1,S2。 ,但数据元素的空间和堆栈结构已产生空堆栈产生后,就存在一个EType类型的数组,大小是MaxSize,表中只有存放数据元素的空间,堆栈栈顶指针设为-1(用户约定),即堆栈为空时,栈顶指针“指向”栈底空间的前面。构造空堆栈S算法(Creat)viodCreatStack (Stack &S , int &MaxStackSize){// = MaxStackSize; = new EType []; = -1;} ,是指堆栈中没有一个数据元素,即栈顶指针top指向数据空间的第一个位置(0下标的空间)的前面。如堆栈不空,top总是指向栈顶元素(top的值为非-1)。判断堆栈S是否为空算法(IsEmpty)boolIsEmpty(Stack &S){// 判断堆栈S是否为空if ( == -1) return true;return false;} ,是指堆栈的所有数据空间已经全部用完,即栈顶指针top指向数据空间的最大下标位置(MaxSize-1下标的空间)。如堆栈不满,top总是指向栈顶元素(top的值小于MaxSize-1)。判断堆栈S是否为满算法(IsFull)boolIsFull(Stack &S){// 判断堆栈S是否为满if ( >= -1) return true;return false;} 堆栈的顺序存储及操作