chapter3栈.ppt

第三章：栈 3.1 基本概念 3.2 栈的存储结构和操作 3.3 栈的应用 3.1 基本概念 栈（Stack） 是一种特殊的线性表，是操作受限的线性表。 栈的应用： 程序设计、调试和运行等。 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表。 表尾—栈顶。 表头—栈底。 不含元素的空表称空栈。 特点： 先进后出（FILO）或后进先出（LIFO）。 3.2 栈的存储结构和操作 3.2.1 顺序栈 3.2.2 链栈 3.2.1 顺序栈 3.2.2 链栈 3.3 栈的应用 3.3.1 数制转换 3.3.2 表达式求值 3.3.3 过程的嵌套调用 3.3.4 递归 3.3.1 数制转换 3.3.2 表达式求值 3.3.3 过程的嵌套调用 3.3.4 递归 = = LOGO an a1 a2 ... 栈底 栈顶 出栈 进栈 1.顺序栈的实现 用一维数组实现 #define Stack_INTSIZE 50 DataType s [Stack_INTSIZE]; int top; //定义栈顶指针 1 2 3 . . . 50 0 A B C top D S 思考： 栈顶指针top与前面所讲的指针有什么区别？ 用结构体实现 #define Stack_INTSIZE 50 //设定栈的最大存储空间 typedef struct { DataType s[Stack_INTSIZE]; int top; }SeqStack; SeqStack *st； 1 2 3 . . . 50 0 A B C top D st 1 2 3 4 5 0 A B C D E F top= =-1 1 2 3 4 5 0 栈空 栈顶指针top,初值为-1。 top 1 2 3 4 5 0 进栈 A top 出栈 栈满 B C D E F 设数组元素个数为M top= = -1,栈空，此时出栈，则下溢（underflow) top= =M-1,栈满，此时入栈，则上溢（overflow) top top top top top top top top top top top 栈空 2. 顺序栈的操作示意图 判断栈是否为空 int IsEmpty(SeqStack* st ) { return ( st-top= = -1 ) ? 1: 0; // 栈为空返回1，否则返回0 } 3.顺序栈的基本操作 进栈 void Push(SeqStack* st, DataType x) { if (st-top= = Stack_INTSIZE-1) printf(\n栈满，不能入栈!); else { st-top++; //先修改指针，后赋值 st-s[st-top]=x; } } top 1 2 3 4 5 0 A B top 出栈 void Pop(SeqStack* st) /*出栈函数，没有返回栈顶元素值，必要时须补上*/ { if ( IsEmpty (st) ) printf(\n栈空，不能出栈!\n); else st-top--; } 1 2 3 4 5 0 A B C D top top top 读栈顶元素 DataType ReadTop(SeqStack* st) /*读栈顶元素的值*/ { DataType x; if ( IsEmpty (st) )//判断是否为空栈 { printf(\n栈中无元素); return (0); } else //取栈顶元素的值 x=st-s[st-top]; return x ; } 1. 结点定义 struct node { DataType data; struct node *next; } ; LinkStack *top; //栈顶指针 typedef LinkStack data next 结点 top ^ data next 栈底 栈顶 …... top 2.链栈操作示意图 ^ …... 栈底 top top x p top 栈底 ^ …... q p-next=top; top=p; q= top;