云南师范大学信息学院数据结构课件第3章 栈和队列（2）.pptVIP

第3章 栈和队列 * * 栈的逻辑结构 * 栈的顺序存储结构 栈的链式存储结构 3.1 栈 栈 (stack) 是限定仅在表尾进行插入或删除操作的线性表，因此，对于栈来说，表尾端有其特殊的含义。 在栈中，插入元素叫作入栈，删除元素叫作出栈。通常将允许进行插入或删除操作的一端称为栈顶 (top)，栈顶将随着栈中的数据元素的增减而浮动，通过栈顶指针指明当前元素的位置；另一端称为栈底 (bottom)，栈底指针并不随着栈中的元素的增减而移动，栈底是固定的。不含元素的空表称为空栈。 * 3.1.1 栈的逻辑结构 1. 栈的定义 an a2 a1 栈顶 栈底 出栈 进栈 (a) 非空栈 (b) 空栈 * * 2. 栈的基本操作 ? InitStack (S ) 操作结果：构造一个空栈 S。 ? Push (S, x) 初始条件：栈 S 已经存在。 操作结果：插入元素 x为新的栈顶元素。 ? Pop (S,x) 初始条件：栈 S 已经存在且非空。 操作结果：删除栈 S 栈顶元素，并用 x返回其值。 栈的顺序存储结构（简称顺序栈）是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。 * 3.1.2 栈的顺序存储结构 1. 栈的顺序存储表示 # define STACK_SIZE 50; /* 存储空间初始分配量*/ typedef struct /* 顺序栈存储结构定义*/ { StackElementType elem[Stack_Size]; /* 用来存放栈中元素的 一维数组*/ int top; /* 栈顶指针,top为-1表示空栈*/ } SeqStack ; /* 顺序栈的类型名*/ * S-top 称为栈顶指针，初值为-1, 可作为栈空的标记。假定 1 个元素占 1 个存储单元：当插入新元素时，先使指针 S-top 增 1再插入；当删除元素时，先删除元素再使指针 S-top 减 1 ，因此，非空栈中的栈顶指针top始终指向栈顶元素。 栈顶指针的初值也可以为0。此时：当插入新元素时，先插入再使指针S-top增1；删除元素时，先使指针S-top减1，再删除。此时，栈中的栈顶指针始终指向当前栈顶元素的下一个位置。 2. 栈的初始化操作 * 3. 基本操作在顺序栈上的实现 void InitStack ( SeqStack *S ) /* 构造一个空栈 S*/ { S.top = -1； return OK; } /* InitStack*/ * (1) 初始化 InitStack 算法的时间复杂性为 O(1)。 Status GetTop ( SeqStack *S, StackElementType *x) /* 如果栈空，则返回 FALSE*//* 如果栈不空，则用 x返回 S 的栈顶元素，并返回 TRUE。*/ (2) 取栈顶元素 { if ( S-top = = -1) return FALSE; /* 如果栈 S 为空，则返回FALSE*/ * else { *x= S-elem[ S-top]; /*栈顶指针所指向的单元内的值赋给x指向的单元中*/ return (TRUE); } } /* GetTop*/ GetTop 算法的时间复杂性为 O(1) (3) 将元素弹出栈 int Pop ( SeqStack *S, StackElementType *x ) /*若栈空，则返回 FASLE*/；/* 若栈不空，将栈S的栈顶元素弹出，放到x所指的存储空间中*/ { if ( S－＞top ==-1） return FALSE; /* 如果栈 S 为空，则返回FALSE*/ else { *x=S-elem[S-top]; /*将栈顶指针所指单元内的值赋给 e*/ S-top--; /* 栈顶指针减 1*/ } return OK; }/* Pop*/ * Pop算法的时间复杂性为 O(1) Int Push ( SeqStack *S; StackElementType x) /* 插入元素 x为新的栈顶元素*/ { if ( S-top ==Stack_Size-