栈和队列7.pptVIP

第3章 栈和队列 张成文 北京邮电大学计算机学院 概述 两种特殊的线性表。 逻辑结构和线性表相同。 比起线性表其运算受限制，故又称它们为运算受限的线性表。 1. 栈 1.1 栈的定义 1.2 顺序栈 1.3 链栈 1.1 栈的定义 栈是限制仅在表的一端进行插入和删除运算的线性表。 (1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。 1.2 顺序栈 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。 顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。 顺序栈的类型定义 #define TRUE 1 #define FALSE 0 #define Stack_Size 50 ?typedef struct { StackElementType elem[Stack_Size]; /* 一维数组*/ int top; /*用来存放栈顶元素的下标*/ }SeqStack; ? 注意 ①顺序栈中元素用向量存放 ②栈底位置是固定不变的，可设置在向量两端的任意一个端点 ③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置 顺序栈的基本运算 （1） 置栈空（初始化） （2） 判栈空 （3） 判栈满 （4） 进栈操作 （5） 退栈操作 （6） 取栈顶元素 ??? 　 （1）置栈空（初始化） ? void InitStack（SeqStack *S）??? {//将顺序栈置空? ????? S-top=-1; ??? }  (2) 判栈空 ? int StackEmpty（SeqStack *S）??? { /*判栈S为空栈时返回值为真，反之为假*/ return S-top==-1;??? } （3）判栈满 ? int StackFull（SeqStack *S）???? {/*判栈S为满时返回真，否则返回假*/ ?????? return S-top==StackSize-1;???? } （4）进栈 进栈时，需要将S-＞top加1 注意： ?①S-＞top==StackSize-1表示栈满 ②“上溢”现象-当栈满时，再做进栈运算产生空间溢出的现象。 ????? 上溢是一种出错状态，应设法避免。 ? void Push（SeqStack *S，DataType x） { if (StackFull(S))????Error(“Stack overflow”); //上溢，退出运行 S-data[++S-top]=x;//栈顶指针加1后将x入栈 } （5）退栈 退栈时，需将S-＞top减1 注意： ①S-＞top0表示空栈 ②下溢现象——当栈空时，做退栈运算产生的溢出现象。????? 下溢是正常现象，常用作程序控制转移的条件。 DataType Pop（S） {??if(StackEmpty(S))?????Error(“Stack underflow”); //下溢，退出运行??return S-data[S-top--];//栈顶元素返回后将栈顶指针减1 } （6）取栈顶元素 ? DataType StackTop（S）??? {?????? if(StackEmpty(S))?????????? Error(Stack is empty);?????? return S-data[S-top];???? } 1.4 链栈 ? typedef struct stacknode{??????????? DataType data??????????? struct stacknode *next?????? }StackNode; StackNode *head=NULL; ???typedef struct{???????? StackNode *top;? //栈顶指针?????? }LinkStack; 链栈的基本运算 (1) 置栈空 (2) 判栈空 (3) 进栈 (4) 退栈 (5) 取栈顶元素 （1） 置栈空 ???? ?void InitStack(LinkStack *S)????? {???????????? S-top=NULL;????? } (2) 判栈空 ????? int StackEmpty(LinkStac