数据结构第三章(栈和队列)串讲+复习要点.docx

第三章栈和队列3．1栈3．1．1 栈的定义及基本运算栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表(LIFO 表)插入、删除端称为栈顶，另一端称栈底表中无元素称空栈基本运算有：1) initstack(s),构造一个空栈；2) stackempty(s),判栈空；3) stackfull(s),判栈满；4) push(s,x)，进栈；5) pop (s),退栈；6) stacktop (s),取栈顶元素3．1．2顺序栈栈的顺序存储结构称顺序栈顺序栈的类型定义为：#define stacksize 100typedef char datatype;typedef struct{datatype data[stacksize];int top;}seqstack;当栈满时,做进栈运算必定产生空间溢出,称“上溢” 当栈空时,做退栈运算 必定产生空间溢出,称“下溢”上溢是一种错误应设法避免,下溢常用作程序控 制转移的条件在顺序栈上的基本运算：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;}5)退栈Datatype pop(seqstack *s){if(stackempty(s)) error(“stack underflow”);return S->data[s->top--];}6)取栈顶元素Dtatatype stacktop(seqstack *s){if(stackempty(s)) error(“stack underflow”);return S->data[s->top];}3.1.3 链栈栈的链式存储结构称链栈栈顶指针是链表的头指针链栈的类型定义 typedef struct stacknode{datatype data;struct stacknode *next;}stacknode; typedef struct{ stacknode *top;}linkstack; 链栈上的基本运算：1) 建栈。

Void initstack(linkstack *s){ s->top=NULL;}2) 判栈空Int stackempty (linkstack *s){return s->top==NULL;}3) 进栈Void push(linkstack *s,datatype x){stacknode *p=(stacknode *)malloc(sizeof(stacknode)); p->data=x;p->next=s->top;s->top=p;}4) 退栈Datatype pop(linksatck *s){datatype x;stacknode *p=s->top;if(stackempty(s))error(“stack underflow”);x=p->data;s->top=p->next;free(p);return x;}5) 取栈顶元素Datatype stacktop(linkstack *s){ if(stackempty(s)) error(“stack is empty”);return s->top->data;}3.2 队列3．2．1 队列的基本定义和计算。

队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾 队列又称为先进先出线性表，FIFO表队列的基本运算：1) initqueue(q),置空队；2) queueempty(q),判队空；3) queuefull(q),判队满；4) enqueue(q,x)，入队；5) dequeue©)，出队；6) queuefront(q),返回队头元素3．2．2 顺序队列队列的顺序存储结构称顺序队列设置front和rear指针表示队头和队尾元素在 向量空间的位置顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指 针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能 入队为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队 列称循环队列 i=(i+1)%queuesize循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”解 决的方法有：1) 另设一个布尔变量以区别队列的空和满；2) 少用一个元素，在入队前测试rear在循环意义下加1是否等于front；3) 使用一个记数器记录元素总数循环队列的类型定义：#define queuesize 100typedef char datatype;typedef struct{int front;int rear;int count;datatype data[queuesize];}cirqueue;1) 置队空。

Void initqueue(cirqueue *q){q->front=q->rear=0; q->count=0;}2) 判队空Int queueempty(cirqueue *q){return q->count==0;}3) 判队满Int queuefull(cirqueue *q){return q->count==queuesize;}4) 入队Void enqueue(cirqueue *q ,datatype x) {if(queuefull(q)) error(“queue overfolw”); q->count++;q->data[q->rear]=x; q->rear=(q->rear+1)%queuesize;}5) 出队Datatype dequeue(cirqueue *q){datatype temp;if(queueempty(q)) error(“queue underflow”); temp=q->data[q->front]; q->count--;q->front=(q->front+1)%queuesize;return temp;}6) 取队头元素。

Datatype queuefront(cirqueue *q){if(queueempty(q)) error(“queue is empty”); return q->data[q->front];}3．2．3 链队列队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定 链队列的定义：typedef struct queuenode{datatype data;struct queue *next;}queuenode;typedef struct{queuenode *front; queuenode *rear;}linkqueue;1) 建空队Void initqueue(linkqueue *q){ q->front=q->rear=NULL;}2) 判队空Int queueempty(linkqueue *q){return q->front==NULL&&q->rear==NULL;}3) 入队Void enqueue(linkqueue *q,datatype x){queuenode *p=(queuenode *)malloc(sizeof(queuenode)); p->data=x;p->next=NULL; if(queueempty(q)) q-front=q->rear=p;else{ q->rear->next=p;q->rear=p;}}4) 出队。

Datatype dequeue(linkqueue *q){datatype x;queuenode *p;if(queueempty(q))error(“queue is underflow”);p=q->front;x=p->data;q->front=p->next;if(q->rear==p) q->rear=NULL;free(p);return x;}5) 取队头元素Datatype queuefront(linkqueue *q){if(queueempty(q)) error(“queue is empty”); return q->front->data;}附二:第三章 栈和队列#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一 端为栈顶，另一端称为栈底。

表中无元素时为空栈栈的修改是按后进先出的原 则进行的，我们又称栈为LIFO表(Last In FirstOut)通常栈有顺序栈和链栈两种 存储结构J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*栈的基本运算有六种：•构造空栈：InitStack(S)•判栈空:StackEmpty(S)•判栈满： StackFull(S)•进栈： Push(S,x)•退栈： Pop(S)•取栈顶元素： StackTop(S)在顺序栈中有"上溢"和。