“算法与数据结构”-栈队列1.ppt

数 据 结 构 主讲人：李志芳 主讲单位：软件技术教研室 时间：2008~2009第二学期 知识点介绍 逻辑结构----栈 1）逻辑结构栈的数据元素的特点及基本操作 2）顺序栈的实现及基本操作 3）链栈的实现及基本操作 4）栈的应用 逻辑结构----队列 1）逻辑结构队列的数据元素的特点及基本操作 2）队列的顺序实现及基本操作 * 3）队列的链式实现及基本操作 * 4）队列的应用 ** 逻辑结构----数组（简单介绍） 1）逻辑结构数组的数据元素的特点及基本操作 2）数组的寻址操作 栈 栈的定义和运算 栈是特殊的线性表，限定只能在一端进行插入和删除的线性表。 栈的特殊概念。能进行插入和删除的一端称为栈顶，另一端称为栈底。（栈只能在栈顶进行插入和删除） 栈 栈的基本操作 栈 栈的基本操作 1）初始化栈：Init_Stack(S) 2）判断栈是否为空：IsNull_Stack (S) 3）取栈顶元素的值：GetTop_Stack (S) 4）压栈：Push_Stack(S,x) 5）出栈：Pop_Stack(S) 6）判断栈是否为满：IsFull_stack (S) 栈的存储结构 顺序栈 以顺序存储方式存储的栈叫做顺序栈。一般情况下用数组来表示，结合栈的特性，最好的方法是把数组的尾设置为栈顶，同时为了方便数据的操作，设置top来指示栈顶元素的位置。 栈的存储结构 顺序栈的基本操作实现 1）初始化栈 void Init_Stack ( Se_Stack *S) {s-top = -1; } 2）判断栈是否为空 int IsNull_Stack(Se_Stack *S) { if(s-top==-1) return 1; else return 0; } 3）取栈顶元素的值 int GetTop_Stack(Se_Stack *S) { if(IsNull_Stack(S) ） return 0； else return s-data[s-top]; } 栈的存储结构 顺序栈的基本操作实现 4）出栈 int Pop_Stack (Se_Stack *S,int *x) {if(IsNull_Stack(S)) return 0； else *x=s-data[s-top ]; s-top --; return 1; } 5）判断栈是否为满 int IsFull_stack(Se_Stack *S ) { if(s-top==MAX_STACK-1) return 1; else return 0; } 6） 压栈 int Push_Stack (Se_Stack *S,int x) { if(IsFull_stack(S )) return 0； else { s-top++; s-data[s-top]=x; } return 1; } 栈的存储结构 链栈 采用链表存储的栈称为链栈。 栈的存储结构 入栈 Stack_Node *Push_LStack(Stack_Node *top,int x) {Stack_Node *s; s=(Stack_Node *)malloc(sizeof(Stack_Node )) if(s==NULL) return NULL; s-d