第三章 栈和队列(1)

1、第三章 栈和队列栈和队列是一种受限的线性表，它们在操作系统、编译原理、大型应用软件系统中得到了广泛的应用 。3.1 栈3.1.1 栈的定义及基本运算1定义栈(Stack)是一种特殊的线性表，它是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。栈顶当前的位置是动态的，栈的插入和删除操作通常称为进栈或入栈，栈的删除操作通常称为出栈或退栈，当表中没有元素时称为空栈。2、特点假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修

2、改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。栈的抽象类型定义：书P45页4、栈的基本操作（1） 建栈，初始化一个栈（2） 进栈，向栈顶插入一新元素（3） 出栈，删除栈顶元素；（4） 读栈，取栈顶元素（5） 置空栈，将栈置为空（6） 判栈空，判断栈是否为空3.1.2 顺序栈栈的顺序存储结构简称为顺序栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top作为栈顶的位置指针来动态的指示

3、栈顶元素在顺序栈中的位置。顺序栈的类型定义如下：#define STACK_INIT_SIZE 100；#define STACKINCREMENT 10；typedef struct /顺序栈定义SElemtype *base; /栈底指针SElemtype *top; /栈顶指针int stacksize；/当前已分配的存储空间 SqStack；或者，顺序栈的类型定义如下：# define StackSize 100typedef char datatype;typedef struct datatype datastacksize;int top;seqstack;status Init

4、Stack ( SqStack &S) /置空栈S.base =( StackData*)malloc(STACK_INIT_SIZE * sizeof(StackData); If(!S.base) exit(overflow);S.top = S.base ;S.stacksize= STACK_INIT_SIZE ;Return ok;void initstack(seqstack *s)s>top=-1;Status StackEmpty (SqStack &S)if( S.top = S.base ) return TRUE /判栈空,空则返回TRUEelse

5、return FALSE; /否则返回FALSEn int stackempty(sqstack *s)n s>top=-1)return(ture);int StackFull (SqStack &S)if( S.top- S.base >= S. StackSize )return TRUE ; /判栈满,满则返回TRUEelse return FALSE; /否则返回FALSEn int stackempty(sqstack *s)n n if(s>top=maxsize-1) return(ture);n else return(false);n Status

6、 Push (SqStack &S，SElemType &e)if( S.top- S.base >= S. StackSize ) /插入元素x为新的栈顶元素S.base =(ElemType *)realloc(S.base , (S.stacksize+ STACKINCREMENT) * sizeof(ElemType);if(! S.base)exit(overflow);S.top= S.base + S.stacksize;S.stacksize+= STACKINCREMENT; /追加存储空间*S.top+=e;Return okvoid push(sq

7、stack *s，datatype e)if (stackfull(s)error(“stack overflow”);s>data+s>top=e;status pop (SqStack &S, SElemType &e)if( S.top = S.base ) return error； /若栈空返回0, 否则栈顶元素退出到e并返回1 e = *(-S.top);return ok;int pop (SeqStack *s, StackData &e)if ( StackEmpty(S) ) return 0;e=s>datatop;s>to

8、p-;return OK;6、取栈顶元素StatusGettop (SqStack &S, SElemType &e)if( S.top = S.base ) return ERROR； /若栈空返回ERROR, 否则栈顶元素读到e并返回OK e = *(S.top-1);return OK;Datatype gettop(sqstack *s)if(stackempty(s)error(“stack is enpty”);return s>datas>top;3.1.3 链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.

9、由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 §链式栈无栈满问题，空间可扩充§插入与删除仅在栈顶处执行§链式栈的栈顶在链头§适合于多栈操作链栈的类型说明如下：typedef int StackData;typedef struct node StackData data; /结点struct node *link; /链指针 StackNode;typedef StackNode *linkstack;§入栈int Push ( LinkStack *top, StackData x ) Stac

10、kNode *p = ( StackNode * ) malloc( sizeof ( StackNode ) );p->data = x; p->next = top ->next;top ->next = p; return 1;§出栈int Pop ( LinkStack *top, StackData &x ) StackNode * p = top->next;if (p=null ) return 0;top ->next= p->next;x = p->data;free (p);return 1;3.2 栈的应用

11、举例3.2.1 数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+n mod d( 其中:div为整除运算,mod为求余运算)例如 (1348)10=(2504)8，其运算过程如下：n n div 8 n mod 81348 168 4168 21 021 2 52 0 2上述过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应该从高位到低位进行，恰好和计算过程相反。因此可以用栈来解决首先，初始化一个栈输入要转换的十进制数当n不等于零时重复执行取余操作，将商值赋给n,将余数压入栈中。直到N等于

12、零然后循环出栈直到栈空。void conversion( )initstack(s);scanf (“%”,n);while(n)push(s,n%8);n=n/8;while(! Stackempty(s)pop(s,e);printf(“%d”,e); 3.2.2 括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例： （）（） （）n int match(char *exp)n char st20;int top=0,i=0;/注意：与前面top=-1相比较 n int nomatch=0;n While(expi!=0&&am

13、p;nomatch=0)n switch(expi)n case(: sttop=expi; top+; break; n case: sttop=expi; top+; break; n case: sttop=expi; top+; break; nn case): if (sttop=() top-;n else nomatch=1; break; n case: if (sttop=) top-;n else nomatch=1; break; n case: if (sttop=) top-;n else nomatch=1; break; n i+;n if (nomatch=o&

14、amp;&top=0) return 1;n else return 0;3.2.3switch(ch)case # : pop(s,c);case : clearstack(s); default : push(s,ch); ch=getchar( );clearstack(s);if(ch!=eof)ch=gethar( );destroystack(s);队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。§链队列中，有两

15、个分别指示队头和队尾的指针。§链式队列在进队时无队满问题，但有队空问题l 我们将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型： 链式队列的定义typedef int Qelemtype;typedef struct QNode Qelemtype data; /队列结点数据struct QNode *next; /结点链指针 QNode,*QueuePtr;typedef struct QueuePtr rear, front; LinkQueue;下面给出链队列上实现的基本运算：§初始化void InitQueue ( LinkQueue &a

16、mp;Q )Q.rear = Q.front = (QueuePtr) malloc( sizeof ( QNode ) );if(!Q.front) exit(OVERFLOW);Q.front->next = NULL;Return OK;队空Status QueueEmpty ( LinkQueue Q )if(Q.front = NULL)return(true);else return(false);§取队头元素Status GetFront ( LinkQueue Q, Qelemtype &e ) if ( QueueEmpty (Q) ) return

17、ERROR;e = Q.front->next->data;return OK;入队的算法§ 入队的算法Status EnQueue ( LinkQueue &Q, Qelemtype e ) p = (QueuePtr) malloc( sizeof ( QNode ) );if(!p) exit(OVERFLOW);p->data = e;p->next= NULL;Q.rear->next = p; /入队Q.rear =p;return OK;§出队 的算法Status DeQueue ( LinkQueue &Q, Q

18、elemtype &e) /删去队头结点，并返回队头元素的值if (Q.front=Q.rear) return ERROR; /判队空p = Q.front ->next;e = p->data; /保存队头的值Q.front->next = p->next; /新队头if (Q.front = NULL) Q.rear = Q.front ;free (p);return OK;注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。3.4.3 循环队列队列的顺序表示和

19、实现顺序队列中存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue）。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。§队头、队尾指针加

20、1，可用取模(余数)运算实现。§队头指针进1: front = (front+1) %maxsize;§队尾指针进1: rear = (rear+1) % maxsize;§队列初始化：front = rear = 0;因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。§思考：§如何来判断队空与队满解决此问题的方法:少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；类型定义#d

21、efine MAXQSIZE 100Typedef structQElemType *base;int front;int rear; SqQueue;初始化队列Status InitQueue ( SeqQueue &Q ) /构造空队列Q. base =(QElemType *)malloc(MAXQSIZE *sizeof(QElemType);If(! Q.base) exit(OVERFLOW);Q.rear = Q.front = 0;Return OK;§入队Status EnQueue ( SqQueue &Q, QElemType e )if ( Q

22、ueueFull (Q) ) return ERROR;Q. baseQ.rear = e;Q.rear = ( Q.rear+1) % MAXQSIZE;return OK;§出队Status DeQueue ( SqQueue &Q, QElemType e )if ( QueueEmpty (Q) ) return ERROR;e = Q.baseQ.front;Q.front = ( Q.front+1) % MAXQSIZE;return OK;队列的实际应用一、打印机软件设计二、在智能排队系统中的队列n char data10;n struct node *nex

23、t;n qtype;n typedef struct qpn qtype *front,*rear;n queue;n void seedoctor()n n flag=1;n q=(queue*)malloc(sizeof(queue);n q->front=(qtype*)malloc(sizeof(qtype);n q->front->next=null;n q->rear=q->front;n while(flag=1)n n printf("nnn1:queue 2:seedoctor 3:seequeue 0:stopwork please select:"); n scanf("%d",&sel);n switch(sel)n n case 0:if(q->front!=q->rear)n printf("nplease see doctor tomorrow!");n flag=0;n br