栈和队列61.pptVIP

3.1 栈　　　　　　　　　　　　　　　　　　　 第3章 栈和队列;3.1 栈 数据结构 第3章 栈和队列;3.1 栈 数据结构 第3章 栈和队列;3.1 栈 数据结构 第3章 栈和队列;　　栈是一种特殊的线性表，因此栈也可采用两种存储结构： 　　顺序存储结构 　　链式存储结构;　　1. 顺序栈 　　（1）顺序栈的存储结构 　　顺序栈是指采用顺序存储结构存储的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针（下标）top，指示栈顶元素的当前位置。 　　对于用C语言描述的顺序栈通常用top=-1表示空栈；入栈时，栈顶指针top增1；出栈时，栈顶指针top减1。 ;3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列;顺序栈的类型定义如下： #define MAXSIZE 100 typedef int ElemType; typedef struct stack { 　 ElemType elem[MAXSIZE]; //存栈顺序表 int top; 　 //栈顶下标 　} SQSTACK;; （2）顺序栈的基本操作 ① 栈的初始化（即构造一个空栈） void InitStack(SQSTACK *ps) { ps-top=-1; } ② 判栈空 int StackEmpty (SQSTACK s) { if (s.top==-1) return 1; else return 0; }; ③ 入栈 int Push(SQSTACK *ps, ElemType e) { if (ps-top==MAXSIZE-1) //判栈满 { cout Stack is full“ endl; return 1; } ps-top++; ps-elem[ps-top]=e; return 0; }; ④出栈 int Pop(SQSTACK *ps, ElemType *pe) { if (ps-top==-1) //判栈空 { cout Stack is empty“ endl; return 1; } *pe=ps-elem[ps-top]; ps-top--; return 0; };⑤读取栈顶元素 int GetTop(SQSTACK s, ElemType *pe) { if (s.top==-1) //判栈空 { printf (Stack is empty\n); return 1; } *pe=s.elem[s.top]; return 0; };2. 链栈 （1）链栈的存储结构 链栈是指采用链式存储结构存储的栈。 链栈是一种特殊的单链表，即限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。; （1）链栈中指针的方向是从栈顶指向栈底（区别于顺序栈，顺序栈是将表尾作为栈顶）。 （2）链栈中没必要附加一个表头结点（因为在表头进行插入、删除操作，带头结点和不带头结点都是一样的）。 ;3.2 栈的存储结构及其基本运算的实现 数据结构 第3章 栈和队列;（2）链栈的基本操作 ① 入栈 链栈的入栈操作，相当于在单链表的第一个结点之前进行插入操作。由于是链式存储，不需要像顺序存储那样需要判断栈是否为满。 void push (SNODE **pps, ElemType e) { SNODE *p; p=new SNODE; p-data=e; p-next=*pps; *pps=p; };② 出栈 链栈的出栈操作相当于在单链表中删除第一个结点。 int pop (SNODE **pps, El