栈和队列讲义

1、栈和队列讲义1 栈2 队列习题定义栈是限定仅在表尾进行插入和删除运算的线性表；表尾称为栈顶；表头称为栈底；当栈中没有数据元素时称为空栈。假设栈 S=(a1，a2，.，an)，可以形象描述为右图所示形式：a1是栈底元素；an是栈顶元素；入栈指插入数据元素；出栈指删除数据元素；栈的常用运算置空栈SetNull(S)，完成对栈的初始化。判断栈空Empty(S)，若栈S为空则返回真，否则返回假。进栈Push(S，e)，在栈S的栈顶插入数据元素e。出栈Pop(S)，删除栈S的栈顶数据元素，并将数据元素返回。取栈顶元素GetTop(S)，取栈S的栈顶数据元素，并把数据元素返回。该操作完成后，栈的状态不变。

2、栈的存储结构有两种：顺序存储结构采用顺序表存储的栈称为顺序栈。链式存储结构。采用单链表存储的栈称为链栈。1.1 栈的顺序存储表示顺序栈定义栈的顺序存储结构定义为：typedef struct datatype elementsmaxsize； int Top； seqstack ；其中：maxsize是栈的容量。 datatype是栈中数据元素的数据类型。 Top指示当前栈顶位置，空栈Top值为-1。 栈底位置为0。栈的状态变化012345Top=-1Top=0Top=4Top=2Top=-1AABCDABC(a)空栈 (b)A进栈 (c)BCDE进栈 (d)ED出栈 (e)CBA出栈0123

3、45012345012345012345顺序栈运算的实现栈初始化void InitS(seqstack*&S) S=(seqstack*)malloc(sizeof(seqstack); S-Top=-1;置空栈void SetNuLLS(seqstack *S) S-Top=-1；判断栈是否为空int EmptyS(seqstack *s) if (S-Top=0) return(0)；/栈非空，返回0 else return(1)；/栈空，返回1 求栈中元素个数int LengthS(seqstack*S) return(S-Top+1); 进栈int PushS(seqstack *S,

4、 datatype e) if (S-Top=maxsize-1) print (“Stack Overflow”)； return 0； /上溢 else S-Top+； S-elementsS-Top=e； return 1； 出栈int PopS(seqstack *S,datatype&e) if (EmptyS(S) print (“Stack Underflow”)； return 0； /下溢 else e= S-elementsS-Top; S-Top-; return 1； 取栈顶元素int GetTopS(seqstack *S,datatype&e) if (EmptyS

5、(S) print (“Stack Underflow”)； return 0； /下溢 else e= S-elementsS-Top; return 1； 1.2 栈的链式存储结构链栈定义栈的链式存储结构称为链栈。它是运算受限的单链表，其插入和删除操作仅在表头进行。链栈定义如下：typedef struct Node datatype element; struct Node *next;linkstack;linkstack *top;链栈示意图如右图栈顶是top指针，它惟一地确定一个链栈。当top等于NULL时，该链栈为空栈。element2elementielementnelemen

6、t=e; p-next=top; top=p; /链栈不存在上溢的问题注意：在函数中修改top的指向，并不能带回到主调函数。可以使用带有头结点的链栈解决这个问题。带有头结点的链栈：p-next=top-next;top-next=p;出栈：int PopL(linkstack *top,datatype&x) if(top=NULL) print(“Stack is underflow”); return 0; /下溢 else x=top-element; top=top-next; return 1; 带有头结点的链栈：if(top-next=NULL) .elsex=top-next-e

7、lement;top-next=top-next-next; .1.3 栈的应用数制转换 十进制N和其它进制数（二、八、十六进制）的转换，采用除基数取余的方法。 例如 (1348)10=(2504)8，其运算过程如下：n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 采用栈存放余数，入栈顺序：4、0、5、2，出栈顺序：2、5、0、4。低位高位算法：输入一个非负十进制整数，输出任意进制数（二、八、十六进制）void Conversion( ) InitStack(s); scanf(“%d,%d”,&N,&base); /输入十进制数和基数 N

8、1=N; while (N1！=0) Push(s,N1%base); /余数入栈 N1 = N1/base; while (! EmptyStack (s) e=Pop(s); /余数出栈 if (e9) printf(“%c”,e+55); /将余数转为字符 else printf(%c,e+48); printf(n); 表达式求值设表达式中只有+、-、*、/、圆括号和操作数运算符间的优先级关系 先括弧内后括弧外左括号：比括号内的运算符优先级低 比括号外的运算符优先级高右括号：比括号内的运算符优先级低 比括号外的运算符优先级高 即“（”与“）”优先级相同，比括号内的运算符优先级低。表达式

9、起始、结束符#：优先级总是最低为实现运算符优先算法，设置操作数栈和运算符栈：OPND栈：存放操作数或运算结果，包括中间结果。 OPTR栈：存放运算符表达式求值算法 p172算法思想：初态： 置OPND栈为空；将“#”作为OPTR栈的栈底元素依次读入表达式中的每个字符 1）若是操作数，则进入OPND栈； 2）若是运算符，则与OPTR栈的栈顶运算符进行优先权（级）的比较：若读入运算符的优先权高，则进入OPTR栈；若读入运算符的优先权低，则OPTR退栈（退出原有的栈顶元素），OPND栈退出两个元素，（先退出b，再退出a），中间结果result入OPND栈；若读入“）”，OPTR栈的原有栈的栈顶元素若

10、是“（”，则OPTR退出“（”；若读入“#”，OPTR栈栈顶元素也是“#”，则OPTR栈退出“#”，结束。例：求表达式（10-3）*2的值。p173例（习题13）：两个栈共享向量空间Vm，栈底分别设在向量的两端，空栈分别表示为top0=-1和top1=m，编写置空栈setnull(i)、入栈push(i,x)、出栈pop(i)的算法。012345m-10号栈入栈 1号栈入栈类型定义：typedef struct datatype vm; int top0,top1;vectorS;vectorS*s=(vectorS*)malloc(sizeof(vectorS)；置空栈：void setnu

11、ll(int i) if(i=0) s-top0=-1; else s-top1=m;入栈：void push(datatype x,int i) if(s-top0=s-top1-1) printf(“Overflow”); else if(i=0) s-top0+; s-vs-top0=x; /对0号栈入栈 else s-top1-; s-vs-top1=x; /对1号栈入栈出栈：datatype pop(int i) datatype temp; if(i=0) if(s-top0=-1) printf(“No.0 stack underflow”); else temp=s-vs-to

12、p0; s-top0-; /对0号栈出栈 else if(s-top1=m) printf(“No.1 stack underflow”); else temp=s-vs-top1; s-top1+; /对1号栈出栈 return temp;例（习题15）：编写算法判断字符串是否中心对称。“abcba” 、“abccba”是中心对称，“abcab”不是中心对称。分析：先将前半部字符入栈，然后出栈与后半部字符逐个比较。int symmetry(string*str) stack *s; InitS(s); /建立空栈 i=0; while(iStrLen(str)/2) /将前半部字符入栈 Pu

13、shS(s,SubGet(str,i,1); /调用取子串的算法，取str中的第i个字符入栈 i+； if(StrLen(str)%2=1) i+; /如果字符串长度是奇数，跳过中间一个字符 flag=1; /标志变量置1 while(!EmptyS(s)&irear+; sq-datasq-rear=x;出队： sq-front+; x=sq-datasq-front; 初始时，队列的头、尾指针指向向量空间下界的前一个位置，在此设置为-1。下图说明了在顺序队列中进行出队和入队运算时队列中的数据元素及其头、尾指针的变化情况。 若sq-front=sq-rear成立，当前队列是空队； 若(sq-

14、rear)-(sq-front)=maxsize成立，当前队列满。存在问题假上溢：顺序队列中存在未用的存储单元，但不能继续进行入队操作。解决办法：将队列中的元素向前移动，缺点是数据的移动量大。将顺序队列构造为环状，形成循环队列。链队列。循环队列设想向量sq-datamaxsize是一个首尾相接的圆环，即sq-data0接在sq-datamaxsize-1之后，即循环队列。如果利用“模”运算，上述循环意义下的头、尾指针操作可以更简洁地描述为： sq-front=(sq-front+1)maxsize sq-rear=(sq-rear+1)maxsize存在问题：空和满无法区分（见下页）循环队列空

15、和满无法区分示例循环队列空情况如左图循环队列满情况如右图解决办法：设置空/满标志。牺牲一个存储单元，队列的最大长度为maxsize-1，这是通常采用的较为简单的方法。牺牲一个存储单元的循环队列示意图：sq-frontsq-rear空队：sq-front=sq-rearsq-frontsq-rearABCDEFG满队：sq-front=(sq-rear+1)%maxsize循环队列基本运算的实现初始化void InitQS(sequeue *&sq) /建立空队列sqsq=(sequeue*)malloc(sizeof(sequeue); sq-front=sq-rear=maxsize-1;

16、置空队void SetNullQS(sequeue *sq) /置队列sq为空队 sq-front=maxsize-1; sq-rear=maxsize-1; 判队空int EmptyQS(sequeue * sq) /判别队列sq 是否为空 if(sq-rear= =sq-front) return(1); else return(0) ;取队头元素int FrontQS(sequeue *sq ,datatype&x) /取 队列sq的队头元素 if (EmptyQS(sq) printf(queue is empty); return (0); else x= sq-data(sq-fr

17、on+1) maxsize; return (1); 入队int EnqueueQS(sequeue *sq, datatype x) / 将新元素x插入队列 *sq 的队尾 if (sq-front=(sq-rear+1) maxsize) printf(“queue is full”); return(0); / 队满上溢 else sq-rear=(sq-rear+1)maxsize; sq-datasq-rear=x; return(1); 出队int DequeueQS(sequeue *sq,datatype&x) / 删除队列 *sq的头元素，并返回该元素 datatype *t

18、mp; if (EmptyQS(sq) printf(“queue is enpty”); return (0); / 队空下溢 else sq-front=(sq-front+1) maxsize; x= sq-datasq-front; return(1); 求队列长度int LengthQS(sequeue*sq) return (sq-rear-sq-front+maxsize)%maxsize);例：如果循环队列只有头指针front和队列长度len，结构类型定义如下：typedef struct datatype datamaxsize; int front,len;sequeue;

19、sequeue *sq;实现队列的6个基本运算。说明：由于可以区分空队和满队，所以不需牺牲一个存储单元。 空队：sq-len=0成立 满队：sq-len=maxsize成立队列初始化void init(sequeue*&sq) sq=new sequeue; sq-front=maxsize-1; sq-len=0;置空队void setnull(sequeue*sq) sq-front=maxsize-1; sq-len=0;判队空int empty(sequeue*sq) if(sq-len=0) return(1); else return(0);取队头元素int get(sequeue

20、*sq,datatype&x) if(empty(sq) printf(“queue is empty”); return (0); else x=sq-data(sq-front+1)%maxsize; return(1); 入队int enter(sequeue*sq,datatype x) if(sq-len=maxsize) printf(“queue is full”); return(0); /队列中最多可容纳maxsize个元素 else sq-len+; sq-data(sq-front+sq-len)%maxsize=x; return(1); 出队int del(seque

21、ue*sq,datatype&x) if(empty(sq) printf(“queue is empty”); return(0); else sq-front=(sq-front+1)%maxsize; sq-len-; x= sq-datasq-front; return(1); 链队列队列的链式存储结构简称为链队列，它是仅限在表头删除和表尾插入的单链表。解决了假溢出问题。头指针指向单链表的头结点，尾指针指向最后一个结点。空的链队列非空的链队列示意图frontrearq#q-rearq-frontfrontrear#q链队列的形式说明typedef struct node datatyp

22、e data; struct node*next;linklist; /结点的结构体类型 typedef struct linklist *front, *rear; linkqueue; /头、尾指针的结构体类型linkqueue q; / q是链队列指针 注：队头结点前附加一个头结点，且头指针指向头结点。链队列*q 为空条件：q-front=q-rear链队列的基本运算实现链队列初始化（建立空队列）void InitQL(linkqueue*&q) q=(linkqueue*)malloc(sizeof(linkqueue); /产生头、尾指针结构体 q-front=q-rear=(lin

23、klist*)malloc(sizeof(linklist);/产生头结点 q-front-next=NULL; /头结点指针域置空置空队void SetNullQL(linkqueue*q) q-rear=q-front; /尾指针也指向头结点 q-front-next=NULL; /头结点指针域置空判队空int EmptyQL(linkqueue*q) if(q-front=q-rear) return(1); else return(0);取队头元素int FrontQL(linkqueue*q,datatype&x) /取出链队列 q 的队头元素 if(EmptyQL(q) printf(“queue is empty”); return(0); else x=q-front-next-data; return(1); 入队void EnqueueQL(l