第3章限定性线性表-栈和队列
《第3章限定性线性表-栈和队列》由会员分享，可在线阅读，更多相关《第3章限定性线性表-栈和队列（78页珍藏版）》请在文档大全上搜索。
1、第第3章章 限定性线性表限定性线性表栈和队列栈和队列3.1 栈栈3.2 队列队列3.3 总结与提高总结与提高3.1 3.1 栈栈3.1.1 栈的定义栈的定义3.1.2 栈的表示和实现栈的表示和实现3.1.3 栈的应用举例栈的应用举例3.1.4 栈与递归的实现栈与递归的实现栈的定义：栈的定义： 栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，表的另一端被称为栈底 (Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。 根据栈定义，每次进栈的元素都被放在原栈顶元素
2、之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示： 进栈、出栈图例进栈、出栈图例进栈进栈出栈出栈进栈出栈栈顶栈底ana2a1栈的抽象数据类型定义栈的抽象数据类型定义关系：关系：栈中数据元素之间是栈中数据元素之间是线性关系线性关系数据元素数据元素：可以是任意类型的数据，但必须属于：可以是任意类型的数据，但必须属于同同一个数据对象一个数据对象。 基本操作基本操作：InitStack（S） 2. ClearStack（S）3. IsEmpty（S） 4. IsFull（S） 5. Push（S，x） 1. 6.
3、 Pop（S，x） 7. GetTop（S，x）3.1.2 栈的表示和实现栈的表示和实现栈栈在计算机中主要有在计算机中主要有两种两种基本的存储结基本的存储结构：构：顺序存储结构顺序存储结构和和链式存储结构链式存储结构。顺序存储的栈为顺序存储的栈为顺序栈；顺序栈；链式存储的栈为链式存储的栈为链栈链栈。1.1.顺序栈顺序栈 顺序栈是用顺序存储结构实现的栈，即顺序栈是用顺序存储结构实现的栈，即利用一组利用一组地址连续地址连续的存储单元依次存放的存储单元依次存放自栈自栈底到栈顶底到栈顶的数据元素，同时由于栈的操作的的数据元素，同时由于栈的操作的特殊性，还必须附设一个特殊性，还必须附设一个位置指针位置指
4、针top（栈（栈顶指针）来动态地指示栈顶元素在顺序栈中顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以的位置。通常以top = -1表示空栈。表示空栈。栈的顺序存储结构定义如下栈的顺序存储结构定义如下 ：#define Stack_Size 50typedef struct StackElementType elemStack_Size; /*用来存放栈中元素的一维数组用来存放栈中元素的一维数组*/ int top; /*用来存放栈顶元素的下标，用来存放栈顶元素的下标，top为为-1表示空栈表示空栈*/SeqStack; 顺序栈中的进栈和出栈图例顺序栈中的进栈和出栈图例AEDCBABAto
5、p top top top顺序栈基本操作的实现顺序栈基本操作的实现1）初始化）初始化void InitStack(SeqStack *S)/*构造一个空栈构造一个空栈S*/ S-top= -1;2）进栈）进栈int Push(SeqStack * S, StackElementType x)if(S-top= Stack_Size-1) return(FALSE); /*栈已满栈已满*/S-top+;S-elemS-top=x;return(TRUE);3）出栈）出栈int Pop(SeqStack * S, StackElementType *x) if(S-top=-1) /*栈为空栈为空
6、*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改栈顶指针修改栈顶指针 */ return(TRUE); 4） 取栈顶元素取栈顶元素int GetTop（SeqStack S, StackElementType *x） /* 将栈将栈S的栈顶元素弹出，放到的栈顶元素弹出，放到x所指的存储空间中，但所指的存储空间中，但栈顶指针保持不变栈顶指针保持不变 */if(S-top=-1) /*栈为空栈为空*/ return(FALSE);else *x = S-elemS-top; return(TRUE); 两栈共享技术（双端栈）：两栈共享技术（
7、双端栈）：主要利用了栈主要利用了栈“栈底位置不变栈底位置不变，而栈顶位置动态变而栈顶位置动态变化化”的特性。首先为两个栈申请一个共享的一维数的特性。首先为两个栈申请一个共享的一维数组空间组空间SM，将两个栈的栈底分别放在一维数组的，将两个栈的栈底分别放在一维数组的两端，分别是两端，分别是0，M-1。 共享栈的空间示意为：共享栈的空间示意为：top0和和top1分别为两个栈分别为两个栈顶指示器顶指示器 。top0top1Stack：0M-1两栈共享的数据结构定义两栈共享的数据结构定义#define M 100typedef struct StackElementType StackM; int
8、top2; /*top0和和top1分别为两个栈顶分别为两个栈顶指示器指示器*/DqStack;（1） 两栈共享的初始化操作算法两栈共享的初始化操作算法void InitStack(DqStack *S)S-top0=-1;S-top1=M;（2） 两栈共享的进栈操作算法两栈共享的进栈操作算法int Push(DqStack *S, StackElementType x, int i) /*把数据元素把数据元素x压入压入i号堆栈号堆栈*/ if(S-top0+1=S-top1) /*栈已满栈已满*/ return(FALSE);switch(i)case 0:S-top0+; S-StackS
9、-top0=x; break; case 1: S-top1-; S-StackS-top1=x; break; default: return(FALSE) /*参数错误参数错误*/ return(TRUE);（3） 两栈共享的出栈操作算法两栈共享的出栈操作算法int Pop(DqStack *S, StackElementType *x, int i) /* 从从i 号堆栈中弹出栈顶元素并送到号堆栈中弹出栈顶元素并送到x中中 */ switch(i) case 0: if(S-top0=-1) return(FALSE); *x=S-StackS-top0; S-top0-; break;
10、 case 1:if(S-top1=M) return(FALSE); *x=S-StackS-top1;S-top1+;break;default: return(FALSE);return(TRUE);2. 链栈链栈链栈链栈是采用是采用链表链表作为存储结构实现的栈。为作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。便于操作，采用带头结点的单链表实现栈。由于栈的插入和删除操作仅限制在表头位置由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。进行，所以链表的表头指针就作为栈顶指针。 链栈的示意图为：链栈的示意图为：anan-1 a1top top为栈顶
11、指针，始终指向当前栈顶元素前面的头结为栈顶指针，始终指向当前栈顶元素前面的头结点。若点。若top-next=NULL，则代表空栈。，则代表空栈。注意：注意：链栈在使用完毕时，应该释放其空间。链栈在使用完毕时，应该释放其空间。链栈结构的用链栈结构的用C语言定义语言定义typedef struct node StackElementType data; struct node *next;LinkStackNode;typedef LinkStackNode *LinkStack;链栈的进栈操作链栈的进栈操作int Push(LinkStack top, StackElementType x)/*
