数据结构第四讲栈实际应用队列.pptVIP

栈 栈的应用 队列 队列的应用; 在下面的结构中，用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下： # define StackSize 100 struct { char data[stacksize]; int top; }seqstack; ;;栈就是这个样子，操作受限的线性表而已 ; 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–data[0]是栈底元素，那么栈顶指针s–top是正向增加的，即进栈时需将s–top加1，退栈时需将s–top 减1。因此，s–top0表示空栈， s–top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。 ;1、置空栈 void initstack(seqstack *s) { s–top=-1; } 2、判断栈空 int stackempty(seqstack *s) { return(s–top==-1); };3、判断栈满 int stackfull(seqstack *s) { return(s–top==stacksize-1); } 4、进栈 void push(seqstack *s，datatype x) { if (stackfull(s)) error(“stack overflow”); s–data[++s–top]=x; } ;例： 对于一个栈，给出输入项A、B、C，如果输入项序列 由ABC组成，试给出所有可能的输出序列。 ;链栈 栈的链式存储结构称为链栈，它的运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下： ;栈的链接存储结构;栈的链接表示 — 链式栈;两个堆栈共享空间;链栈的进栈算法 linkstack *PUSHLSTACK(linkstack *top, datatype x) { linkstack *p; p＝malloc(sizeof(linkstack)); p-data＝x; p-next＝top; return p; };链栈的出栈算法 linkstack *POPLSTACK(linkstack *top, datatype datap) { linkstack *p; if (top==NULL) {printf(“under flow\n”); return NULL;} else { *datap＝top-data; p＝top; top＝top-next; free(p); return top; } };栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。 栈的应用举例-----数制转换 十进制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 21 0 21 2 5 2 0