数据结构-用C语言描述第二版第3章 栈和队列

第三章

栈和队列•第3章 栈和队列栈栈的应用举例队列队列的应用举例第三章

栈和队列第3章

栈和队列栈和队列是两类特殊的线性表，其逻辑结构仍然是线性结构，但栈和队列是运算受限的线性表。栈和队列结构被广泛应用于各种程序设计中。本章讨论栈和队列的定义、运算及其实现等。第三章

栈和队列栈的定义及其运算栈是一类特殊的线性表，数据元素的插入和删除运算只能在表的一端进行，通常将进行插入和删除的一端称为栈顶，另一端称为栈底。将元素的插入称为入栈或进栈，元素的删除称为出栈或退栈。栈也称为后进先出的线性表（简称LIFO表）如图3.1(a)所示。在日常生活中，栈的形式经常出现。例如，一叠盘子或一叠书的取放、铁路调度站，如图3.1(b)所示。栈的基本运算：置空栈setnull(s)：将栈s置成空栈，建立起栈顶指针。判栈空empty(s)：若s为空栈，则返回TRUE值，否则返回FALSE值。入栈push(s,x)：若s未满，将x插入s栈栈顶，并使栈顶指针指向x。出栈pop(s)：若s栈非空，则从栈中删去栈顶元素，返回原栈顶元素。取栈顶元素gettop(s)：若s栈非空，则返回当前栈顶元素。3.1栈第三章

栈和队列第三章

栈和队列3.1.2栈的顺序存储结构栈的顺序存储结构又称为顺序栈，顺序栈也可用向量来实现。顺序栈的类型定义如下：#define

MAXSIZE

100

/*栈的最大容量，这里设为100*/typedef

struct{datatype

stack[MAXSIZE];int

top;}seqstack;/*顺序栈类型定义*/seqstack

*s;/*定义s为指向顺序栈的指针变量*/在顺序栈中进栈或出栈运算时要注意空间的“溢出”。当栈满时，若再进行入栈运算，会产生空间“上溢”；而当栈空时，再进行出栈运算，会产生空间“下溢”。图3.2说明了栈中元素与栈顶指针的关系。第三章

栈和队列第三章

栈和队列在顺序栈上实现的栈的基本运算。置空栈void

setnull(seqstack

*s){

s->top=-1;}判栈空算法int

empty(seqstack

*s){

if(s->top<0)

return(TRUE);else

return(FALSE);}入栈int

push(seqstack*s，datatype

x){

if

(s->top>=MAXSIZE-1){printf(“stack

overflow！\n”);return(FALSE);}else{s->data[++s->top]=x;return(TRUE);}}第三章

栈和队列（4）出栈datatype

pop(seqstack

*s){

if(s->top<0){printf(“stack

empty！\n”);return(NULL);}else{s->top--;return(s->Data[s->top+1]);}}（5）取栈顶元素算法datatype

gettop(seqstack

*s){

if(s->top<0){printf(“stack

empty！\n”);return(NULL);}elsereturn(s->Data

[s->top]);}第三章

栈和队列有时可以将多个栈安排在同一个顺序存储空间中，实现多个栈共享存储空间。假定两个栈共享空间，可以给它们分配一个长度为m的数组空间如图3.3所示。两个栈共享的数据类型定义如下：typedef

struct{datatype

stack[m];int

top[2];

/*

top[0]和top[1]分别为两栈的栈顶指针*/}sharedstack;第三章

栈和队列两个栈共享存储单元的部分运算算法如下：（1）置空栈void

setnull(sharedstack

*s){s->top[0]=-1;s->top[1]=m;}

/*setnull*/（2）入栈int

push(sharedstack

*s，int

i，datatype

x){if(i<0||i>1||s->top[0]+1=

=s->top[1])return

FALSE;else{

if(i==0)

s->stack[++s->top[0]]=x;elses->stack[--s->top[1]]=x;return

TRUE;}}/*push*/第三章

栈和队列（3）出栈datatype

pop(sharedstack

*s，int

i){

if(i<0||i>1)return

NULL;elseif(i=

=0)if

(s->top[0]==-1)return

NULL;elsereturn（s->stack[s->top[0]--]）;elseif(s->top[1]==m)return

NULL;elsereturn（s->stack[s->top[1]++]）;}/*pop*/第三章

栈和队列3.1.3栈的链式存储结构栈的链式存储结构称为链栈。链栈是运算受限的单链表，其运算只能在链表头部进行，其头指针就是栈顶指针。链栈的数据类型定义：typedef

struct

node{datatype

data;struct

node

*next;}linkstack;linkstack

*top;/*链栈头指针，即栈顶指针*/链栈如图3.5所示，其中top是栈顶指针。当top=NULL时，该链栈是空栈。第三章

栈和队列链栈的入栈和出栈运算算法。入栈void

push(linkstack

*top，datatype

x){

linkstack

*p;p=(linkstack

*)malloc(sizeof(linkstack));/*生成一个新结点*p*p->data=x;p->next=top;top=p;}出栈datatype

pop(linkstack

*top){

linkstack

*p;datatype

x;if(top=

=NULL){printf("stack

empty！\n");return(NULL);}第三章

栈和队列else{p＝top；top=top->next;x=p->data;free(p);

/*释放p所指的结点*/return(x);}}第三章

栈和队列3.2栈的应用举例3.2.1表达式求值一般的，一个表达式由操作数、运算符和分界符组成。若运算符出现在两个运算数或操作数之间（单目运算符除外），称为中缀表达式。中缀表达式有利于人的理解，但不适合机器的实现。因此，在编译系统中，要把中缀表达式变换成一种后缀表达式（也称为逆波兰式），在后缀表达式中，运算符处在两个操作数之后。后缀表达式一不需要使用括号；二不需要考虑运算符的优先级，只需从左到右扫描后缀表达式，当扫描遇到运算符时，就把它前面的两个操作数取出，然后进行运算。如图3.6所示。把中缀表达式变换为相应的后缀表达式，然后根据后缀表达式计算表达式的值，这两个步骤都可以利用栈结构来实现。第三章

栈和队列运算后缀表达式ABCD/-E*+T1

C/DT2

B-T1ABT1-E*+AT2E*+T3

T2*EAT3+T4

A+T3T4图3.6后缀表达式的计算过程第三章

栈和队列要把中缀表达式转变为后缀表达式可以从左到右依次扫描中缀表达式，根据所读到的是操作数还是运算符，利用栈并结合各个运算符之间的优先

级关系（表3-1

）来进行运算。其算法思想是：设置一个栈并初始化，然

后从左到右顺序读入中缀表达式。当读到的是操作数时就直接将其输出，

并接着读下一个。当读到的是运算符时，就将它赋给

2，并根据运算符的优先级关系表3-1，比较

2与当前栈顶运算符

1的优先级。若

2的优先级比1的高，则将

2进栈，继续读下一个；若

2的优先级比

1的低，则将

1出栈并作为后缀表达式的一部分输出，然后继续比较

2与新的当前栈顶运算符1的优先级；若2的优先级与1的相同，且1为‘(’，2为‘)’，则将

1出栈，并丢弃1和2，再继续读下一个；若2的优先级与1的相同，且1和

2都是‘#’，则表示表达式处理完毕，算法结束。例如，图3.7表示对中缀表达式A*(B+C)*D变换为后缀表达式，最后结果为ABC+*D*。第三章

栈和队列表3-1运算符优先级关系表2+()#1+>><<<>>>><<<>>>>>><>>>>>><>>(<<<<<=)>>>>>>#<<<<<=第三章

栈和队列步数读入符号序列栈输出1A#A2*#*A3(#*(A4B#*(AB5+#*(+AB6C#*(+ABC7)#*ABC+8*#*ABC+*9D#*ABC+*D10##ABC+*D*图3.7中缀表达式转变为后缀表达式过程第三章

栈和队列将中缀表达式变换为后缀表达式的算法描述如下：void

post(seqstack

*s，char

R[]){

char

ch1，ch2；int

j=0;s->stack[0]="#";s->top=0;ch2=R[j];while(!(ch2=="#")&&(gettop(s)=="#"))/*当不是结束符#时循环*/{

if(ch2!="+"

)

&&

(ch2!="-"

)

&&

(ch2!="*"

)

&&

(ch2!="/")&&

(ch2!="(&&

(ch2!=")")

&&

(ch2!="#")}{printf("%c"，ch2);ch2=R[++j];}elseif(proceed(gettop(s)，ch2)=

="<")第三章

栈和队列{push(s，ch2);ch2=R[++j];}elseif(proceed(gettop(s)，ch2)=

=">"){ch1=pop(s);printf("%c"，ch1);}elseif(proceed(gettop(s),ch2)=

="="

)&&（gettop(s)=

="("&&ch2=="){ch1=pop(s);ch2=R[++j];}elseprintf("输入表达式有语法错误");}}/*

postfix*/其中proceed()函数实现表3-1的运算符优先级关系比较功能，其函数返回值为对应的字符，取值为‘>’，‘<’或‘=’。第三章

栈和队列把中缀表达式变换成相应的后缀表达式后，根据后缀表达式计算表达式的基本思想是：设置一个操作数栈，从左到右扫描后缀表达式，每读到一个操作数，就将其压入栈中；每当读到一个运算符时，就从栈中弹出两个操作数，结合读入的运算符进行计算，然后将计算结果重新入栈，一直进行，直到整个表达式扫描完毕，最后在栈顶位置的数就是该表达式的值。图3.8示出后缀表达式ABCD/

E*+的求值过程。第三章

栈和队列top

DCtopT1topEBBtopT2T2topT3AAAAA

top

T4(a)读入ABCD后，(b)读到/，作C/DT1，(c)读到-，作B-T1T2，(d)读入E后，

(e)读到*，作T2*E

T3，(f)读到+，作A+T3T4图3.8后缀表达式求值过程示例第三章

栈和队列3.2.2递归的实现在程序设计中常常要用到递归的方法。递归函数的特点是在函数内部可以直接或间接地调用函数本身。函数直接调用本身称为直接递归调用；而一个函数通过另一个函数来调用其本身。例如，一个整数n的阶乘的定义：其递归算法如下：int

fact(int

n){

if(n=

=0)return(1);elsereturn(n*fact(n-1));}第三章

栈和队列递归函数执行过程的信息传递和控制转移可以用栈结构来实现。系统将整个程序运行时所需的空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当退出一个函数时，就释放它所占用的存储区，当前工作的函数的数据区总在栈顶。例如，递归函数fact（4）的执行过程如图3.10所示，而图3.11表示求解4！时工作栈的变化。第三章

栈和队列第三章

栈和队列第三章栈和队列3.3.1队列的定义及其运算队列也是一种运算受限的线性表。只允许在表的一端进行插入运算，而在另一端进行删除运算。允许插入（也称为入队）的一端称为队尾，允许删除（也称为出队）的一端称为队头，当队列中没有数据元素时称为空队列。队列是一种与栈相反的结构。队列也称为先进先出的线性表，简称为FIFO表，如图3.12所示。队列的含义与现实生活中购物排队相似，先进入队列的成员总是先离开队列。3.3队列第三章

栈和队列通常，队列的基本运算有以下五种：置空队setnull(q)：设置一个队列q为空队列。判队列空empty（q）：若队列q为空，则返回TRUE，否则返回FALSE。入队列enqueue（q，x）：将数据元素x插入队列q的队尾。出队列delqueue（q）：若队列q非空，删除队列的队头元素，并返回该队头元素。取队头元素getfront(q)：若队列q非空，则返回队头元素，否则返回空元素值。第三章

栈和队列3.3.2队列的顺序存储结构队列的顺序存储结构称为顺序队列。与顺序表类似，队列的顺序存储结构也是利用一个向量空间来存放当前队列中的元素。一般的，队列需设置两个指针分别指示当前队头元素和队尾元素。为了方便运算，可约定队尾指针指示当前队尾元素在队列中的实际位置，而队头指针指示当前队头元素的前一个位置。顺序队列的类型定义如下：typedef

struct{datatype

queue[MAXSIZE];/*MAXSIZE为队列的最大长度*/int

front，rear;}sequeue;sequeue

*sq；第三章

栈和队列顺序队基本运算的实现：置空队void

setnull(sequeue

*sq){sq->front=-1;sq->rear=-1;}入队int

enqueue(sequeue

*sq，datatype

x){

if

(sq->rear=

=MAXSIZE-1)return(FALSE);else{sq->queue[++sq->rear]=x;return(TRUE);}}第三章

栈和队列（3）出队datatypedelqueue(sequeue

*sq){

if(sq->front=

=sq->rear)return(NULL);elsereturn(sq->queue[++sq->front]);}第三章

栈和队列以上算法在入队运算中，由于队满条件的限制会产生“假上溢”现象，即当前队列并没有满但会产生“上溢”。如图3.13所示。为了更好地解决“假上溢”问题，可以将顺序队列设想为一个首尾相接的圆环，称为循环向量，队列称为循环队列，如图3.14所示。此时，可以克服“假溢出”现象。队尾指针加1的运算在循环意义下可描述为：if(sq->rear+1==MAXSIZE)sq->rear=0;else

sq->rear++;也可以利用利用数学上的求模运算描述为：sq->rear=(sq->rear+1)%MAXSIZE同样，出队运算时，在循环意义下的队头指针加1运算可描述为：sq->front=(sq->front+1)%MAXSIZE但在利用循环队列时会出现队空和队满两种不同的状态无法区别的情形，如图3.14（b）和（c），利用等式sq->front=sq->rear都可以表示队空和队满两种不同的状态。第三章

栈和队列第三章

栈和队列第三章

栈和队列一般的，可利用以下两种方法解决这个问题：设置一个区别队列满与队列空的标志，该标志用于标记在队列中执行的最后一次运算。不过，使用标志会减慢队列入队和出队的速度。第二种方法是在入队运算之前，先判断(sq->

rear+1)%MAXSIZE与sq->front是否相等，若相等，则认为队列满。但这样会使得在循环队列中队头指针所指的位置始终是空的，有

MAXSIZE个分量的循环空间只能表示长度不超过MAXSIZE-1的队列。但通过少利用一个元素空间而解决了队满与队空条件相同的矛盾，总的来说是可行的。循环队列的入队和出队运算算法描述如下：第三章

栈和队列入队列算法int

encyque(sequeue

*sq，datatype

x){

if((sq->rear+1)%MAXSIZE==sq->front)return(FALSE);else{sq>rear=(sq->rear+1)%MAXSIZE;sq->queue[sq->rear]=x;return(TRUE);}}出队列算法datatype

delcyque(sequeue

*sq){

if(sq->front=

=sq->rear)return(NULL);else{sq->front=(sq->front+1)%MAXSIZE;return(sq->queue[sq->front]);}}第三章

栈和队列3.3.3队列的链式存储结构队列的链式存储结构简称为链队列，它是限制在表头删除即出队和表尾插入即入队的单链表。它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。一个链队列可由一个队头指针和一个队尾指针唯一地确定，如图3.15。链队列定义如下：typedef

struct

node{datatype

data;struct

node

*next;}queuenode;/*定义链队列中的一个结点结构*/typedef

struct{queuenode

*front，*rear;}linkqueue;/*定义链队列结构*/linkqueue

*lq；第三章

栈和队列第三章

栈和队列链队列上的几种基本运算描述：置空队void

inilinkque(linkqueue

*lq){

lq->front=(queuenode

*)malloc(sizeof(queuenode));

lq->rear=lq->front;lq->front->next=NULL;}入队void

enlinkque(linkqueue

*lq，datatype

x){queuenode

*p;p=(queuenode

*)malloc(sizeof(queuenode));p->data=x;p->next=NULL;lq->rear->next=p;lq->rear=p;}第三章

栈和队列（3）出队出队列运算必须考虑链队列的长度大于