第3章特殊线性表栈、队列和串.DOC

PAGE 14 数据结构电子笔记 第 3 章 特殊线性表——栈、队列和串 PAGE 13 第 3 章 特殊线性表——栈、队列和串 3.1 栈 3.1.1 栈的逻辑结构 1. 栈的定义 栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。 栈的示意图： 栈的示意图： 栈的操作特性 生活中栈的例子： 计算机中栈的例子： 2. 栈的抽象数据类型定义 ADT Stack Data 栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系 Operation 栈的抽象数据类型可定义为抽象类： InitStack 栈的抽象数据类型可定义为抽象类： 前置条件：栈不存在 输入：无 功能：栈的初始化 输出：无 后置条件：构造一个空栈 DestroyStack 前置条件：栈已存在 输入：无 功能：销毁栈 输出：无 后置条件：释放栈所占用的存储空间 Push 前置条件：栈已存在 输入：元素值x 功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素 Pop 前置条件：栈已存在 输入：无 功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈顶减少了一个元素 GetTop 前置条件：栈已存在 输入：无 功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变 Empty 前置条件：栈已存在 输入：无 功能：判断栈是否为空 输出：如果栈为空，返回1，否则，返回0 后置条件：栈不变 endADT 3.1.2 栈的顺序存储结构及实现 1. 栈的顺序存储结构——顺序栈 1．把数组中下标为0的一端作为栈底，同时附设指针top指示栈顶元素在数组中的位置。2． 设存储栈元素的数组长度为StackSize，则栈空时栈顶指针top＝- 1．把数组中下标为0的一端作为栈底，同时附设指针top指示栈顶元素在数组中的位置。 2． 设存储栈元素的数组长度为StackSize，则栈空时栈顶指针top＝-1； 栈满时栈顶指针top＝StackSize-1。 3．入栈时，栈顶指针top加1；出栈时，栈顶指针top减1。 顺序栈的操作示意图： 1. 顺序栈的实现 const int StackSize=10; //10只是示例性的数据，可以根据实际问题具体定义 template class T //定义模板类SeqStack class SeqStack { public: private: }; template class T 札记： template class T 札记： void SeqStack::Push(T x) { } 顺序栈入栈算法Push template class T 札记： template class T 札记： T SeqStack:: Pop( ) { } 顺序栈出栈算法Pop 3. 两栈共享空间 提出问题：在一个程序中如果需要同时使用具有相同数据类型的两个栈时，如何处理呢？ 解决方案一：为每个栈开辟一个数组空间； 解决方案二：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸，如图3-3所示。 下标：0 1 i-1 下标：0 1 i-1 a1 a2 …… ai