数据结构第三章-1.pptVIP

第三章 栈和队列 栈（Stack） 队列（Queue） 定义 逻辑结构 存储结构 运算规则 实现方式 ３.１ 堆栈的定义 3.1.1 堆栈的逻辑结构 堆栈（也简称栈）是一个线性表，其数据元素只能从这个有序集合的同一端插入或删除，这一端称为堆栈的栈顶（top），而另一端称为堆栈的栈底（bottom）。 特点：先进后出（FILO）或后进先出（LIFO） 如同线性表一样，堆栈也有顺序存贮和链式存贮两种存贮方式。 在不同的存贮方式下，上述运算的执行过程是不相同的，下面就两种不同的存贮方式讨论堆栈运算的实现。 3.２ 堆栈的顺序存储及操作 3.2.1 堆栈顺序存储 堆栈顺序存储方式: 是将堆栈中的数据元素连续顺序地存放于存储器相邻的单元,来保证堆栈数据元素逻辑上的有序性。 堆栈占用的第一个存储单元的地址，就是堆栈的首地址，也是堆栈中栈底元素（e0）存放的位置。 2.堆栈顺序存储结构定义 typedef struct { EType *element; //一维数组 int top; //指向堆栈栈顶元素 int MaxSize; //可存储的最多数据元素 } Stack； Stack S，S1，S2； 3.2.2 堆栈顺序存储结构下的操作 viod CreatStack (Stack S , int MaxStackSize) {// 构造一个最大容量为MaxStackSize 的堆栈S S.MaxSize = MaxStackSize; S.element = new EType [S.MaxSize]; S.top = -1; } 堆栈栈顶指针设为-1（用户约定），即堆栈为空时，栈顶指针“指向”栈底空间的前面。 2.判断堆栈是否为空或为满 bool IsEmpty(Stack S) {// 判断堆栈S是否为空 if (S.top == -1) return true; return false; } bool IsFull(Stack S){// 判断堆栈S是否为满 if (S.top = S.MaxSize-1) return true; return false; } 4.返回栈顶元素的值 Status GetTop(Stack S , EType x) { // 返回堆栈S中栈顶元素 if (IsEmpty (S)) return ERROR; x = S.element[S.top]; return OK; } 5.进栈 Status Push(Stack S , EType x) {// x进s栈，返回进栈后的状态值 if (IsFull(S)) return ERROR; S.top++; S.element[S.top] = x; return OK; } 6.出栈 Status Pop(Stack S , EType x) {// 将s栈顶的值取至x中，返回出栈后的状态值 if (IsEmpty(S)) return ERROR; x = S.element[S.top]; S.top--; return OK; } Q1：堆栈是什么？它与一般线性表有什么不同？ Q2：顺序表和顺序栈的操作有何区别？ 3.3 堆栈的链式存储及操作 3.3.1 堆栈的链式存储 。 特点:是用物理上不一定相邻的存储单元来存储堆栈的元素，附加一个指针域也叫链域, 保证堆栈之间的逻辑上的连续性。 表头链接域top始终指向栈顶结点，即链表的第一个结点。对链式栈，一般不存在栈满问题，除非存储空间全部被耗尽； 链式栈空表现为链式栈的表头结点链接域top的值为空，即链表为空。 3.3.2 链式栈的操作 1.构造链式栈 ChainStack* CreatStack(ChainStack *S) {// 构造一个空栈 S=new ChainStack; S-top=NULL; return S; } 2.判断堆栈S是否为空 bool IsEmpty(ChainStack *S) { if (!S-top) return true; return false; } 3.返回链式栈栈顶元素的值 Status Push(ChainStack *S, EType x) {// x进s栈，返回进栈后的状态值 StackNode *q = new StackNode; q -data=x; q -link=S-top; S-top = q return OK; } 5.出栈 Status Pop(Ch