解决堆栈的编程问题

1、使用堆栈解决编程问题数据结构(C#语言版)解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)目标目标在本章中,你将学到:识别堆栈的特性实施堆栈运用堆栈来解决编程问题解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)学习情境学习情境用堆栈解决火车车厢重排问题的编程用堆栈解决火车车厢重排问题的编程问题描述问题描述一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 -n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次

2、序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。图3.1a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。在图3.1a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。图3.1b 给出了按所要求的次序重新排列后的结果。解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)学习情境学习情境用

3、线性表解决学生成绩表的编程用线性表解决学生成绩表的编程问题描述问题描述(续续)根据上面的描述，编写程序实现下面的功能：编写一算法实现火车车箱的重排；编写程序模拟图3.1所示的具有9节车厢的火车入轨和出轨的过程。程序主界面设计如图3.2所示。解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)让我们来玩Rummy（拉米纸牌）的游戏。堆栈堆栈777777776666666666666666认识堆栈认识堆栈分析堆栈的逻辑结构分析堆栈的逻辑结构解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)堆栈(Stack)是一种特殊的线性表,是一种只允许在表的一端进行插入

4、或删除操作的线性表。 堆栈就是一个只能访问其末尾数据的数据集，这一端也叫做顶部。 数据仅能在顶部进行插入和删除操作。 最新插入的数据将被最先删除。因此，堆栈也被称为后进先出数据结构（Last-In-First-Out）。认识堆栈认识堆栈分析堆栈的逻辑结构分析堆栈的逻辑结构1. 堆栈的定义堆栈的定义2. 堆栈的特征堆栈的特征堆栈也被称为后进先出数据结构（Last-In-First-Out）。解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)初始化栈：也就是产生一个新的空栈； 入栈操作Push(T x):将指定类型元素x进到栈中； 出栈操作TPop(): 将栈中的栈顶元素取出

5、来，并在栈中删除栈顶元素； 取栈顶元素GetTop():将栈中的栈顶元素取出来，栈中元素不变； 判断栈空IsEmpty():若栈为空，返回true，否则返回false； 清空操作Clear ( )：从栈中清除所有的数据元素。认识堆栈认识堆栈识别堆栈的基本操作识别堆栈的基本操作堆栈的基本操作有以下几种：堆栈的基本操作有以下几种：解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)下面描述堆栈的进栈操作下面描述堆栈的进栈操作PUSH：它是在堆栈顶部插入新元素的过程。Empty Stack1Push an Element 1认识堆栈认识堆栈识别堆栈的基本操作识别堆栈的基本操作解决

6、堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)PUSH：它是在堆栈顶部插入新元素的过程。下面描述堆栈的进栈操作下面描述堆栈的进栈操作1Push an Element 22Push an Element 33认识堆栈认识堆栈识别堆栈的基本操作识别堆栈的基本操作解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)POP：它是从堆栈顶部删除元素的过程。下面描述堆栈的出栈操作下面描述堆栈的出栈操作1POP an Element 323POP an Element 2认识堆栈认识堆栈识别堆栈的基本操作识别堆栈的基本操作解决堆栈的编程问题解决堆栈的编程问题数据结构

7、数据结构(C#语言版语言版)堆栈中的元素按 _基础进行添加和删除。课间思考课间思考答案：LIFO解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈(Sequence Stack)。 类似于顺序表，用一维数组来存放顺序栈中的数据元素 。 栈顶指示器top设在数组下标为0的端，top随着插入和删除而变化，当栈为空时，top=-1 。 用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题用顺序栈表示堆栈用顺序栈表示堆栈解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)初始化顺序栈就是创建一个空栈，

8、即调用SeqStack的构造函数，在构造函数中执行下面的步骤：1. 初始化顺序栈初始化顺序栈用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1初始化maxsize为实际值2为数组申请可以存储maxsize个数据元素的存储空间，数据元素的类型由实际应用而定3初始化top为的值为-1解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)Push操作是将一个给定的项保存在堆栈的最顶端，顶端元素的索引保存在变量top中，因此要进行Push操作，需要执行下面的步骤：2.入栈操作：入栈操作：Push(T elem)用顺序栈解决堆栈的编程

9、问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1判断堆栈是否是满的，如果是，停止操作；否则执行下面的步骤2将top的值加13设置索引为top的数组元素的值为elem解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)Pop操作就是从堆栈的顶部取出数据。要进行Pop操作，需要执行以下的步骤：3. 出栈操作：出栈操作：T Pop( )用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1检查堆栈中是否含有元素，如果没有，停止操作；否则执行下面的步骤2获取索引top中的值3将索引top的值减1解决堆栈

10、的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)取栈顶元素操作与出栈操作相似，只是取栈顶元素操作不改变原有堆栈，不删除取出的元素。4. 取栈顶元素：取栈顶元素：GetTop()用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1检查堆栈中是否含有元素，如果没有，停止操作；否则执行下面的步骤2获取索引top中的值解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)用链式存储结构存储的栈称为链栈(Linked Stack)。链栈通常用单链表来表示，它的实现是单链表的简化 。链栈结点的结构与单链表结点的结构一样 。

11、 LinkStack类中有一个字段top表示栈顶指示器和一个字段size表示栈的大小 。 用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题用链栈表示堆栈用链栈表示堆栈解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)初始化链栈就是创建一个空链栈，即调用LinkStack的构造函数，在构造函数中执行下面的步骤：1. 初始化链栈初始化链栈用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1栈顶指示器top为null2栈的元素个数size为0解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)Push操作

12、是将一个给定的项保存在堆栈的最顶端，在链栈中，就是在单链表的起始处插入一个结点。需要执行下面的步骤：2.入栈操作：入栈操作：Push(T elem)用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1创建一个新结点2如果栈为空，将栈顶指示器top指向新结点，否则执行下面步骤3将新结点的next指向栈顶指示器top所指向的结点4将栈顶指示器top指向新结点5栈元素个数size加1解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)Pop操作就是从堆栈的顶部取出数据，即从链栈的起始处删除一个结点。要进行Pop操作，需要执行以下的

13、步骤：3. 出栈操作：出栈操作：T Pop( )用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1检查堆栈中是否含有元素，如果没有，停止操作；否则执行下面的步骤2获取栈顶指示器top所指向结点的值3将栈顶指示器top指向单链表中下一个结点4栈元素个数size减1解决堆栈的编程问题解决堆栈的编程问题数据结构数据结构(C#语言版语言版)取栈顶元素操作与出栈操作相似，只是取栈顶元素操作不改变原有堆栈，不删除取出的元素。4. 取栈顶元素：取栈顶元素：GetTop()用顺序栈解决堆栈的编程问题用顺序栈解决堆栈的编程问题对顺序栈进行操作对顺序栈进行操作步骤步骤操作操作1检查堆栈中是否含有元素，如果没有，停止操作；否则执行下面的步骤2获取索引top中的值解决堆栈的编程问题解决堆栈的编程问题数据结