第3章栈和队列

1、o队列的应用队列的应用 3.1栈3.1.1 栈的定义及基本运算 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来

2、实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下： # define StackSize 100 typedef char datatype; typedef struct datatype datastacksize; int top; seqstack; top6 5 4 3 2 1 0-1例、一叠书或一叠盘子。 栈的抽象数据类型的定义如下：P44 a

3、n a n-1 a2 a1栈顶 栈底 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即sdata0是栈底元素，那么栈顶指针stop是正向增加的，即进栈时需将stop加1，退栈时需将stop 减1。因此，stoptop =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。1、置空栈 void initstack(seqstack *s) stop=-1; 2、

4、判断栈空 int stackempty(seqstack *s) return(stop=-1); 3、判断栈满 int stackfull(seqstack *s) return(stop=stacksize-1); 4、进栈 void push(seqstack *s，datatype x) if (stackfull(s) error(“stack overflow”); sdata+stop=x; 5、退栈 datatype pop(seqstack *s) if(stackempty(s) error(“stack underflow”); x=sdatatop; stop-; re

5、turn(x) /return(sdatastop-); 6、取栈顶元素 Datatype stacktop(seqstack *s) if(stackempty(s) error(“stack is empty”); return sdatastop; 例：例：对于一个栈，给出输入项对于一个栈，给出输入项A、B、C，如果输入项序列，如果输入项序列由由ABC组成，试给出所有可能的输出序列。组成，试给出所有可能的输出序列。A进 A出 B进 B出 C进 C出 ABCA进 A出 B进 C进 C出 B出 ACBA进 B进 B出 A出 C进 C出 BACA进 B进 B出 C进 C出 A出 BCAA进 B

6、进 C进 C出 B出 A出 CBA不可能产生输出序列CAB3.1.3 链栈 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下： 栈的链接存储结构链栈的结点定义链栈的结点定义typedef int datatype;typedef struct node datatype data; struct node *next; linkstack; 栈的链接表示 链式栈 链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于

7、多栈操作两个堆栈共享空间两个堆栈共享空间0maxsize-1lefttoprighttop链栈的进栈算法链栈的进栈算法linkstack *PUSHLSTACK(linkstack *top, datatype x) linkstack *p; pmalloc(sizeof(linkstack); p-datax; p-nexttop; return p;链栈的出栈算法链栈的出栈算法linkstack *POPLSTACK(linkstack *top, datatype datap) linkstack *p; if (top=NULL) printf(“under flown”); ret

8、urn NULL; else *dataptop-data; ptop; toptop-next; free(p); return top; 3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。栈的应用举例-数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 2

9、1 0 21 2 5 2 0 2 void conversion( ) initstack(s); scanf (“%”,n); while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e); printf(“%d”,e); 栈的应用举例文字编辑器栈的应用举例文字编辑器seqstack s;EDIT() char c; SETNULL(&s); cgetchar(); while (c!=*) if (c=#) POP(&s); else if (c=) SETNULL(&s); else PUSH(&s

10、,c); cgetchar(); 栈的应用举例表达式计算栈的应用举例表达式计算中缀表达式：A + ( B C / D) E后缀表达式：ABCD/E+后缀表达式特点1、与相应的中缀表达式中的操作数次序相同2、没有括号后缀表达式的处理过程后缀表达式的处理过程操作顺序后缀表达式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A + T3T4中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式()#(#next=q.rear-next=null; q.frontq.rearnull置队空*q队列的判空：int queueempty(linkqueue *q)

11、return (q.front-next= =null & q.rear-next= =null); void enqueue(linkqueue *q,datatype x)queuenode *p p=(queuenode * )malloc(sizeof(queuenode); pdata=x; pnext=null; if(queueempty(q) q.front-next=q.rear=p; else q.rearnext=p; q.rear=p; 入队操作null*qq.frontq.rear入队xnullp出队操作：Datatype dequeue(linkqueue

12、*q) datatype x; queuenode *p if(queueempty(q) error(“queue underflow”); p=q.front-next; x=pdata; q.front-next=pnext; if(q.rear = =p) q.rear=q.front; free(p); return x; null*qq.rearxnullq.frontp存储池出队n队列应用举例 划分子集问题o问题描述：已知集合A=a1,a2,an，及集合上的关系R= (ai,aj) | ai,ajA, ij，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(k