第三章 栈和队列

1、第三章第三章 栈和队列栈和队列 3.1 堆栈 3.2 队列3.1 堆栈3.1.1 堆栈的定义和基本操作w栈（stack）是一种特殊的线性表，这种表只能在其一端（称为栈顶top）进行插入和删除操作,如图2-4-1所示。栈的概念来自存货的堆栈，存货时一件一件往上堆，每次取货时都有只能从上面取。栈的存取特征是后进先出（Last In First Out,缩写为LIFO）。栈顶将随着栈中元素的增减而浮动，通过栈顶指针指明当前栈顶元素位置。栈的固定端称为栈底（bottom），栈底指针并不移动。w栈的基本操作包括：创建一个栈进栈 栈顶 出栈w进栈（push），出栈（pop）w读取栈顶元素，判栈空，w栈清空

2、（初始化），求当前栈w中元素的个数，撤消一个栈等w 栈底3.1.2 顺序存储栈w可用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个游标变量top（习惯称为栈顶指针，注意与指针变量的区别），top指出栈顶表元素在数组中的下标。当栈为空时，top =0;栈满时，top=MAXN(数组元素个数),如图2-4-1所示。顺序存储栈示意图w wMAXN-1 MAXN-1 top w . .w . .w . .w 1 1wtop-0 0w 栈空 栈满 1、顺序存储栈的进栈操作(1)w 顺序存储栈的进栈操作(2)w函数如下：wint push(NODE stack,int maxn

3、,int top,NODE x)/*设栈点的数据类型为NODE，栈空间最多能存maxn个结点*/wif (top=maxn) return 1; /*栈满，进栈失败返回*/wstack top=x; /*完成进栈运算*/w+top;wreturn 0; /*进栈成功，返回0*/w2、顺序存储栈出栈操作(1)顺序存储栈出栈操作(2)w函数如下：wint pop(NODE stack,int top,NODE cp)wif(top=0) return 1; /*栈空，出栈失败返回*/w-top; wcp=stack top; /*完成出栈运算*/wreturn 0; /*出栈成功，返回*/w3.1

4、.3 链式存储栈w栈也可以用链表实现，用链表实现的栈称为链式栈。链表的第一个元素是栈顶结点，链表的末尾元素是栈底结点，链表的首表指针是栈顶指针top ,top为null的空链表是空栈。w设栈结点类型为：wtypedet struct node wNODE data; /*栈元值，某种NODE类型*/wstruct node *link;wLNODE;(一) 链式存储栈的进栈函数w示意图 top top=p p-link=topw w p4 X 5 2 null函数定义w函数如下：wvoid L_push(NODE x,LNODE *top) /*设栈结点的数据类型为NODE*/wLNODE *

5、p=(LNODE *)malloc(sizeof(LNODE);wp-data=x;wp-link=top;wtop=p;w（二 ）链接存储栈的出栈函数w示意图wTopw p4 5 2 Null 函数定义 int L_pop(NODE *cp,LNODE *top) /*设栈结点的数据类型为NODE*/wLNODE *p=top;wif(top=NULL) return 1;/*空栈*/w*cp=p-data;wtop=p-link;wfree(p);wreturn 0;/*出栈成功*/w3.2 3.2 队队 列列 w一、队列定义、w队列是只允许在一端进行插入，另一端正进行删除的线性表，如图3

6、-7所示。 出队 q0 q1 qi qi+1 qn-1 进队 队首 队尾w 图3-7 队列示意图 w队列中允许删除运算的一端称队首，允许插入运算的一端称为队尾。习惯称在队列中插入结点操作为进队，队列中删除结点的操作为出队。w若有队Q=(q0,q1,qn-1),则q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，所以队列具有先进先出（First In First Out简称FIFO）的特性。w队列的基本操作包括：创建一个队列，入列，出队，读取队首元素，判队空，请队列空，求当前队列中的元素个数，撤消一个队列等。3.2.1 顺序存储队列w可以用顺序存储线性表来表示队列，为了指明当前

7、执行出队运算的队首位置，需一个游标变量front（习惯上称为头指针），为了指明当前执行进队运算的队尾位置，需要一个游标变量rear（习惯上称为尾指针）。w开始时，让队列front度rear都指向数组的前端，这是一个空队列。在队列未满情况下，队列可执行进队运算。进队时，首先让rear加1,变为指向队列新结点的存放下标，然后将新结点送到由rear所指的数组元素中。队列非空时，可执行出队运算。出队时，首先把front所指的队列首结点送到接受结点的变量中，然后让front加1，使front指向新的队首结点。出入队列的状态示意图环形队列(1)w若用有MAXN个元素的数组表示队列，随着一系列进队和出队运算

8、，队列的结点移向存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决方法是当发生这样的情况时，把队列中的结点移到数组的前端，并修改头指针和尾指针。另一种更好的解决办法是采用环形队列。w环形队列就是将实现队列的数组q的首元q0与末元qmax-1连接起来。队空的初态为front=rear=0；在环形队列中，当rear赶上front时，队列满。反之，当front赶上rear时，队列为空。这样队空或队满的条件都同为front=rear，这给程序判别队空或队满带来不便。为此采用当队列只剩下一个空闲结点的空间时，就认为队列已满的简单办法以区别队空和队满。示意图如下：w队列出、

9、入队操作示例： 环形队列(2)在下面的入列和出队算法中，queue数组用来存放队列元素，头指针为front，尾指针为rear，数据结构定义如下：#define MAX 50int queueMAX；int front=-1,rear= -1;1、顺序队列的进队列算法：队满时返回eof，否则返回0int insert_queue (int x) if (rear= =MAX-1) return(eof); queue+rear=x; return(0);环形队列(3)2、顺序队列出队列算法：队空时返回eof，否则返回y值wint delete_queue()w int y ;w if (fron

10、t= =rear) return(eof);w y=queue+front;w return(y);w3、入循环队列wint inset_q(int q, int x)w int front,rear;w if (rear+1)%MAX)= =front) return(eof);welse rear=(rear+1)%MAX;w qrear=x;w return(1);w w环形队列（4）4、出循环队列int delete_q(int q, int y) int front,rear; if(front= = rear) return(0); front=(front+1)%MAX; y=q

11、front; return(y);3.2.2链式存储队列 队列也可以用链表实现，用链表实现的队列称为链式队列。链表的第一个表示是队列首结点，链表的末尾表示是队列的队尾结点，队尾结点的链接指针值为null。队列的头指针hpt指向队列的首结点，队列的尾指针tpt指向队尾结点。当队列的头指针hpt值为null时，队列为空。设有：wtypedef struct nodew node data;w struct node *link;w Lnode;一、链式队列进队函数w示意图 tptwhpt p A X nullB C null链式队列进队函数定义wvoid Len_queue(Lnode *hpt,

12、Lnode *tpt,node x) w Lnode *p=(Lnode *)malloc(sizeof(Lnode);w p-data=x;w p-link=null;w if (hpt= =null)tpt=hpt=p;welse tpt = (= (tpt)-link=p;w 二、链式队列出队函数w示意图 hpt=hpt-link tptwhpt pA B C null链式队列出队函数定义wint Lde_queue(Lnode *hpt,Lnode *tpt,node *cp)w Lnode *p= hpt;w if(hpt= =null) return 1; /* 队空*/w*cp=

13、 (hpt)-data;whpt=(hpt)-link;wif(hpt= = null) tpt=null;wfree (p);wreturn 0;w 举例(1)wP33 二w1向一个栈顶指针为Top的链栈中插入一个S所指的结点时，其进行的操作是（ ）。w2从栈顶指针为Top的链栈中删除一个结点，并将结点保存在X中，进行的操作是（ ）。w3在具有N个单元的循环队列中，队满时共有（ ）个元素。w4假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e进行一系列操作SSXSXSSXXX之后，得到的输出序列为（ ）。w5设有数组A0.m作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是（