数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源03栈和队列

栈和队列,栈的定义和基本运算/ 顺序栈/ 链栈/ 队列的定义和基本运算/顺序队列/链式队列/实训,唐懿芳,数据结构与算法,目录,CONTENTS,栈的定义和基本运算,1、栈的定义 2、栈的基本运算,01,数据结构与算法,第一节：栈的定义和基本运算,数据结构与运算,生活中的栈与队列 栈和队列是特殊的线性表 栈与队列的特征 LIFO(Last In First Out) FIFO(First In First Out),栈的定义,堆栈简称为栈，是限定只能在表的一端进行插入和删除操作的线性表。 在表中，允许插入和删除的一端称作“栈顶”，另一端称作“栈底”。通常将元素插入栈顶的操称作为“入栈”（进栈或压栈），称删除栈顶元素的操作为“出栈”,栈底,栈顶,入栈,出栈,图3.1 堆栈,a1,a2,an,第一节：栈的定义和基本运算,栈的基本运算,堆栈的基本运算如下。 (1) StackInit()初始化堆栈。 (2) StackEmpty(s) 判定栈s是否为空。 (3) StackLength(s) 求堆栈s的长度。 (4) GetTop(s) 获取栈顶元素的值。 (5) Push(s, e) 将元素e进栈。 (6) Pop(s)，出栈（删除栈顶元素）。,数据结构与运算,第一节：栈的定义和基本运算,栈的存储结构,两种存储结构： (1) 顺序栈采用顺序结构存储 (2) 链栈采用链式结构存储,数据结构与运算,顺序栈,1、顺序栈的存储结构 3、顺序栈的案例 2、顺序栈的基本运算,02,数据结构与算法,第二节：顺序栈,顺序栈的存储结构,MaxSize-1,#define MaxSize 堆栈可能达到的最大长度 typedef struct ElementType elemMaxSize; int top; /*栈顶位置*/ SeqStack;,栈底,栈顶,a0,a1,an-1,备 用 空 间,栈满和栈空的条件是什么？,栈满：top=Maxsize-1 栈空：top=-1,数据结构与运算,SeqStack StackInit() SeqStack s; s.top=-1; return(s); ,顺序栈的基本运算,初始化堆栈 StackInit(),int StackEmpty(SeqStack s) return(s.top=-1); ,判定栈s是否为空StackEmpty(s),int StackLength(SeqStack s) return(s.top+1); ,求堆栈s的长度StackLength(s),ElementType GetTop(SeqStack s) if (StackEmpty(s) /*空栈*/ return(nil); return(s.elems.top); ,获取栈顶元素的值GetTop(s),void Push(SeqStack *s, ElementType e) if (s-top= MaxSize-1) /*栈满*/ printf(“Full”); else s-top+; s-elems-top=e ; ,进栈Push(s, e),ElementType Pop(SeqStack *s) if (s-top= -1) /*栈空*/ return(nil); /* 返回空值*/ else e=s-elems-top; s-top-; return (e); ,出栈Pop(s),第二节：顺序栈,数据结构与运算,顺序栈案例1,【例1】假设有两个栈共享一个一维数组空间0,MaxSize1，其中一个栈用数组的第0单元（元素）作为栈底，另一栈用数组的第MaxSize1号单元（元素）作为栈底（即两个堆栈从两端向中间延伸），其对应的类型描述如下： #define MaxSize 堆栈可能达到的最大长度 typedef struct ElementType elemMaxSize; int top1, top2; /*栈顶位置*/ ShareStack;,第二节：顺序栈,数据结构与运算,顺序栈案例2,则栈1的栈顶表示为:s-top1，栈2的栈顶表示为:s-top2; 栈1的进栈操作使得栈顶1右（后）移，即s-top1+，栈2进 栈操作使得栈顶2左（前）移，即s-top1-; 栈满时两个栈顶相邻，即s-top1+1s-top2。,图3.2 共享堆栈,栈1,栈顶2,a1,an,b1,bm,栈2,栈底1,栈底2,0,MaxSize-1,栈顶1,第二节：顺序栈,数据结构与运算,顺序栈案例3 进栈,void Push(ShareStack *s, ElementType e, int i) /*将元素e压入栈i(i=1,2)*/ if (s-top1+1=s-top2) /*栈满*/ printf(“Full”); else if (i=1) s-top1+; s-elems-top1=e ; else s-top2-; s-elems-top2=e ; ,第二节：顺序栈,数据结构与运算,顺序栈案例4出栈,ElementType Pop(ShareStack *s, int i) /*栈i(i=1,2)出栈*/ if (i=1) if (s-top1=-1) /*栈1空*/ return(nil); else e=s-elems-top1; s-top1-; return(e); if (i=2) if (s-top2= MaxSize) /*栈2空*/ return(nil); else e=s-elems-top2; s-top2+; return(e); ,第二节：顺序栈,数据结构与运算,链栈,1、栈的链式存储结构 2、链栈的基本运算,03,数据结构与算法,第三节：链栈,链栈的存储结构,#define MAX_SIZE 100 /设置最大元素个数 typedef int Elemtype; typedef struct snode ElementType data; struct snode *next; StackNode; typedef StackNode *LinkStack; / * LinkStack为指向StackNode 的指针类型* /,.,图3.6 链栈,栈顶,a1,an,an-1,栈底,data,next,s,数据结构与运算,第三节：链栈,链栈的基本操作,1栈初始化 栈的初始化实现比较简单，算法如下： LinkStack StackInit() LinkStack s=(LinkStack)malloc(sizeof(StackNode); s-next=0; return (s); /* StackInit */ 2判断栈是否为空 在判断栈是否为空时，只需将栈顶指针s-next值与null相比即可，算法实现如下： int StackEmpty(LinkStack s) return(s-next=NULL); /* StackEmpty */,数据结构与运算,第三节：链栈,链栈的基本操作,3求栈的长度 int StackLength(LinkStack s) LinkStack p=s-next; int length=0; while (p) length+; p=p-next; return(length); /* StackLength */ 4进栈操作 /插入元素e为新的栈顶元素 void Push(LinkStack s, int e) LinkStack p=(StackNode *)malloc(sizeof(StackNode); p-data=e; p-next=s-next; /如图把当前的栈顶元素赋值给新结点的直接后继 s-next =p; /如图将新的结点p赋值给栈顶指针 /* Push*/,数据结构与运算,第三节：链栈,链栈的基本操作,5出栈操作 /若栈不空，则删除栈顶元素，用e返回值 int Pop(LinkStack s) if (StackEmpty(s) /*栈空*/ return(nil); /* 返回空值*/ else LinkStack p=s-next; /*如图将栈顶结点赋值给p*/ int e=0; s-next= p-next; /*如图使得栈顶指针下移1位，指向后一结点*/ e=p-data; free(p); /*释放结点p*/ return(e); /* Pop*/,数据结构与运算,第三节：链栈,链栈的基本操作,6获取栈顶元素 根据栈顶指针s，可以直接获取最后入栈的元素。应该注意的是，在进行读取之前，也要进行栈空检查。 相关的算法实现如下： int GetTop(LinkStack s) if (StackEmpty(s) return(nil); return(s-next-data); /* GetTop*/,数据结构与运算,队列,1、队列的定义 3、队列的存储结构 2、队列的基本运算,04,数据结构与算法,第4节：队列,队列的定义,队列简称为队，是限定只能在表的一端作插入运算、在另一端作删除运算的线性表； 在表中，允许插入的一端称作“队尾”，允许删除的另一端称作“队首”（或“队头”）； 通常将元素插入队尾的操作称作为入队列（或入队），称删除队首元素的操作为出队列（或出队）。,数据结构与运算,第4节：队列,队列的基本运算,数据结构与运算,队列的基本运算如下。 (1) InitQueue() 初始化队列。 (2) QueueEmpty(q) 判定队列q是否为空。 (3) QueueLength(q) 求队列q的长度。 GetHead(q) 获取队列q队首元素的值。 (5) AddQueue (q, e) 将元素e入队。 (6) DeleteQueue (q) 删除队首元素。,第4节：队列,队列的存储结构,两种结构： (1) 顺序队列采用顺序结构存储 (2) 链式队列采用链式结构存储,数据结构与运算,顺序队列,1、队列的顺序存储结构 2、顺序队列的基本运算,05,数据结构与算法,第5节：顺序队列,队列的顺序存储结构 1,#define MaxSize n 队列可能达到的最大长度n typedef struct ElementType elemMaxSize; int front, rear; /*队首、队尾指示器*/ Queue;,数据结构与运算,第5节：顺序队列,队列的顺序存储结构 2,数据结构与运算,图3.12 队列操作,a,b,c,e,rear=4,d,front=-1,b,c,e,rear=4,d,front=0,front=rear=4,front=rear=-1,