数据结构.第3章.栈和队列.1.栈

top
e d c b a
§3.2 栈的表示和实现
栈在抽象类型中的几种操作举例
例4：删除栈顶元素（即出栈）
Status Pop(SqStack & s, SElemType &e) { // 若栈不空，删除S的栈顶元素，用e返回其
top base ERROR
// 值 ，并返回0K，否则返回ERROR if (s.top = = s.base) return (ERROR); e = * - - s.top; //--s.top; e=*stop;栈顶指针始终在栈顶元素的下一位置 return OK; } // Pop;
3.存储结构
4.运算规则 5.实现方式
§3.1 栈的类型定义
栈与一般线性表有什么不同
栈与一般线性表的区别：仅在于运算规则不同。
一般线性表
逻辑结构：一对一 存储结构：顺序表、链表
栈
逻辑结构：一对一 存储结构：顺序栈、链栈
运算规则：随机存取
运算规则：后进先出(LIFO)
“进” ＝压入=PUSH（x) “出” ＝弹出=POP ( y )
§3.2 栈的表示和实现
栈在抽象类型中的几种操作举例
top
例2：取栈顶元素
Status GetTop(SqStack s, SElemtype &e) { //若栈不空，用e返回S的栈顶元素 if (s.top = = s.base) return ERROR; e = * (s.top - 1); //操作后s.top不变，并将当前栈顶元素赋给e return OK; } // GetTop; 等同于删除栈顶元素（出栈），区别在于： e = * - - s.top; //操作后stop减１，并将当前出栈的元素赋给e
e=D
top
D
C
B base
A
§3.2 栈的表示和实现
栈的链式存储结构
栈的链式存储结构称为链栈，它是运算是
受限的单链表，插入和删除操作仅限制在 表头位置上进行。由于只能在表头进行操 作，故没必要附加头结点，栈顶指针就是 链表的头指针。
§3.2 栈的表示和实现
栈的链式存储结构
链栈示意图
Top an an-1
§3.2 栈的表示和实现
栈顶指针和栈中元素之间的关系
top
D C
top
top
B A A
base base
B A
top
base base
1）空栈中的栈顶指针的指向和栈底指针一致
2）非空栈中的栈顶指针始终在栈顶元素的下一个位置
§3.2 栈的表示和实现
栈在抽象类型中的几种操作举例
例1：构造一个空栈
§3.2 栈的表示和实现
链栈插入新栈顶元素（即入栈）
Status Push(LinkStack *s, ElemType e) { //插入元素e为新的栈顶元素 q=(StackNode*)malloc(sizeof(StackNode)); q–>data=e; q–>next=s–>top; s–>top=q;
§3.1 栈的类型定义
思考题
一个栈的入栈序列是a, b, c, d, e，则栈的不
可能的输出序列是（
A） e d c b a C） d c e a b
）。
B） d e c b a D） a b c d e
§3.1 栈的类型定义
栈的抽象数据类型定义
ADT Stack{ 数据对象：D={ai|ai∈ElemSet,i=1,2,...,n) 数据关系: R={<ai-1,ai>|ai-1,ai∈D,i=2,...,n) 约定an端为栈顶，a1端为栈底 基本操作： InitStack( &S ) 操作结果：构造空栈S DestroyStack( &S ) 初始条件：栈S已存在 操作结果：销毁栈S ClearStack( &S ) StackEmpty( S ) StackLength( S ) GetTop( S,&e ) Push( &S, e ) Pop( &S, &e ) } ADT Stack 初始条件：栈S已存在 操作结果：将S置为空栈 初始条件：栈S已存在 操作结果：判别栈S是否为空栈 初始条件：栈S已存在 操作结果：返回栈S中元素个数(栈长) 初始条件：栈S已存在且非空 初始条件：栈S已存在 操作结果：用e返回S的栈顶元素 操作结果：插入元素e为新的栈顶元素
初始条件：栈S已存在 操作结果：删除S的栈顶元素，用e返回值
§3.2 栈的表示和实现
栈的物理存储
栈的物理存储可以用顺序存储结构，也可
用链式存储结构。相应地，栈的存储方式 也分为两种，即顺序栈和链。§3.2 栈的表示和实现
顺序栈的定义
#define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; // base的初值为NULL，表明栈结构不存在 SElemType *top; // 栈顶指针，初值指向栈底， // 即top=base作为栈空的标记 int stacksize; // 当前已分存储空间，即指示当前栈 // 可使用的最大容量，以元素为单位 } SqStack; // 存储空间初始分配量 // 存储空间分配增量
}
§3.2 栈的表示和实现
链栈删除栈顶元素（即出栈）
Status Pop( LinkStack *s, ElemType &e) { //若栈不空，则删除链栈栈顶元素，用e返回其值 if (StackEmpty(s) return (Error); q=s–>top; e=q–>data; s–>top=q–>next; free(q); return OK; }
Top
Data next
an
an-1
……
a1
/\
§3.2 栈的表示和实现
链栈的基本操作
Void InitStack(LinkStack *s){ //初始化链栈 s–>top=null; } Int StackEmpty(LinkStack *s){ //判断是否空栈 return s–>top==null; } ElemType Gettop(LinkStack *s){ //返回栈顶元素 if(StackEmpty(s)) return (ERROR); return s–>top–>data; }
Status InitStack(SqStack &s) { //构造一个空栈S s.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemtype)); If (!s.base) exit (OVERFLOW); //存储分配失败 s.top=s.base; s.stacksize= STACK_INIT_SIZE; return OK; } // InitStack;
§3.1 栈的类型定义
栈的相关概念
栈 是仅在表尾进行插入、删除操作的线性表。
表尾(即an端)称为栈顶 Top；表头(即a1端)称为栈底Base
例如： 栈 s = (a1, a2, a3,……, an-1, an) a1称为栈底元素 an称为栈顶元素
插入元素到栈顶(即表尾)的操作，称为入栈。
从栈顶(即表尾)删除最后一个元素的操作，称为出栈。
武汉科技大学
Wuhan University of Science and Technology
张 凯 计算机学院 软件工程系
2011年3月12日
第3章
栈和队列
栈的类型定义 栈的应用举例 栈类型的实现 队列类型的定义和实现
§3.1 栈的类型定义
§3.1 栈的类型定义
§3.1 栈的类型定义
§3.1 栈的类型定义
§3.3 栈的应用举例
1.数制转换 2.括号匹配的检验 3.行编辑程序
4.迷宫求解
5.表达式求值
§3.3 栈的应用举例
数制转换
十进制数 N 和其它 D 进制数的转换 N = ( N div d )×d + N mod d (其中：div 为整除运算，mod 为求余运算）
§3.3 栈的应用举例
……
a1
/\
栈顶
栈底
§3.2 栈的表示和实现
链栈的类型说明如下
typedef struct StackNode{ ElemType data struct StackNode *next }StackNode; typedef struct { StackNode *top } LinkStack;
§3.3 栈的应用举例
括号匹配的检验
status matching(string &exp) { // 检验表达式中所含括弧是否正确嵌套， int state = 1; while ( i <= length(exp) && state) { swith of exp[i] { case “(”: { Push(&S,exp[i]); i++; break; } case “)”: { if ( ！StackEmpty(S) && GetTop(S) = = „(„ ) { Pop(&S,&e); i++; } else state = 0 ; break; } ．．．．．． } // swith } // while if ( state && StackEmpty(S) ) return OK else return ERROR;
[ „ ( „ ( „ ] „ [ „ ] „ ) „ ]