《数据结构》课件-项目三 栈

用栈实现迷宫探路项目概述栈是计算机术语中比较重要的概念，在计算机中有广泛的运用。程序员无时无刻不在应用栈，函数的调用是间接使用栈的最好例子，可以说栈的一个最重要的应用就是函数的调用。栈典型的应用还有判断平衡符号、实现表达式的求值（中缀表达式转后缀表达式的问题以及后缀表达式求值问题）、在路径探索中实现路径的保存。本章中的迷宫探路问题就是用栈保存搜索的路径的实例。。项目目标序号学习目标知识要点1理解栈的逻辑结构栈的基本概念、基本操作、抽象数据类型2理解栈的顺序与链式存储结构及其算法实现栈的顺序存储：顺序栈栈的链式存储：链式栈3熟悉Java中栈的实现类栈的顺序存储实现类：Stack<E>栈的链式存储实现类：LinkedList<E>4能在实际问题中找出栈并用栈解决实际问题使用栈解决迷宫探路问题项目情境-编程实现诗词大赛

1．情境描述

迷宫（maze）是一个矩形区域，它有一个入口和一个出口，入口位于迷宫的左上角，出口位于迷宫的右下角，在迷宫的内部包含不能穿越的墙或障碍物，如图3-1所示。迷宫探路问题是寻找一条从入口到出口的路径，该路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居，如图所示。2．基本要求

编写程序搜索迷宫通路，如果找到通路，显示“找到可到达路径”，并显示路径的位置信息；如路径没有找到，提示“没有可到达路径”。迷宫探路的基本思路是从迷宫的入口出发，沿正东方向顺时针对当前位置相邻的东、南、西、北4个位置依次进行判断，搜索可通行的位置。如果有，移动到这个新的相邻位置上，如果新位置是迷宫出口，那么已经找到了一条路径，搜索工作结束；否则从这个新位置开始继续搜索通往出口的路径。若当前位置四周均无通路，则将当前位置从路径中删除出去，顺着当前位置的上一个位置的下一方向继续走，直到到达出口（找到一条通路）或退回到入口（迷宫没有出路）时结束。用栈实现迷宫探路项目概述栈是计算机术语中比较重要的概念，在计算机中有广泛的运用。程序员无时无刻不在应用栈，函数的调用是间接使用栈的最好例子，可以说栈的一个最重要的应用就是函数的调用。栈典型的应用还有判断平衡符号、实现表达式的求值（中缀表达式转后缀表达式的问题以及后缀表达式求值问题）、在路径探索中实现路径的保存。本章中的迷宫探路问题就是用栈保存搜索的路径的实例。。项目目标序号学习目标知识要点1理解栈的逻辑结构栈的基本概念、基本操作、抽象数据类型2理解栈的顺序与链式存储结构及其算法实现栈的顺序存储：顺序栈栈的链式存储：链式栈3熟悉Java中栈的实现类栈的顺序存储实现类：Stack<E>栈的链式存储实现类：LinkedList<E>4能在实际问题中找出栈并用栈解决实际问题使用栈解决迷宫探路问题项目情境-编程实现诗词大赛

1．情境描述

迷宫（maze）是一个矩形区域，它有一个入口和一个出口，入口位于迷宫的左上角，出口位于迷宫的右下角，在迷宫的内部包含不能穿越的墙或障碍物，如图3-1所示。迷宫探路问题是寻找一条从入口到出口的路径，该路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居，如图所示。2．基本要求

编写程序搜索迷宫通路，如果找到通路，显示“找到可到达路径”，并显示路径的位置信息；如路径没有找到，提示“没有可到达路径”。迷宫探路的基本思路是从迷宫的入口出发，沿正东方向顺时针对当前位置相邻的东、南、西、北4个位置依次进行判断，搜索可通行的位置。如果有，移动到这个新的相邻位置上，如果新位置是迷宫出口，那么已经找到了一条路径，搜索工作结束；否则从这个新位置开始继续搜索通往出口的路径。若当前位置四周均无通路，则将当前位置从路径中删除出去，顺着当前位置的上一个位置的下一方向继续走，直到到达出口（找到一条通路）或退回到入口（迷宫没有出路）时结束。任务一

分析线性表的逻辑结构学习目标熟悉栈的逻辑结构熟悉栈的基本操作12熟悉栈的抽象数据类型3

为完成迷宫探路编程任务，首先对问题抽象，建立问题的抽象数据类型。一是确定数据对象的逻辑结构，找出构成数据对象的数据元素之间的关系。二是确定为求解问题需要对数据对象进行的操作或运算。最后将数据的逻辑结构及其在该结构上的运算进行封装得到抽象数据类型。任务描述步骤一：分析栈的逻辑结构任务实施

栈(stack)是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入和删除操作的一端称为栈顶，最下面的那一端称为栈底。栈顶是动态的，它由一个称为栈顶指针的位置指示器指示。当栈中没有数据元素时，称之为空栈。栈的插入操作也称为进栈或入栈，栈的删除操作称为出栈或退栈。栈的定义栈中元素按a1,a2，a3，…，an

的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an,an-1，…，a1

栈的特点后进先出一堆盘子。放一个盘子的时放在这堆盘子的最上面，拿的时侯也是拿最上面的盘子。一堆书。只有顶部的那本书封面可见，要看到其他书的封面，要从最上面的书开始，依次移除它上面的每本书。步骤二：分析栈的基本运算任务实施初始栈：创建一个空栈入栈：在栈顶添加一个数据元素出栈：删除栈顶数据元素取栈顶元素：获取栈中当前栈顶的数据元素，栈中数据元素不变求栈长度：获取栈中的数据元素个数判断栈空：判断栈中是否有数据元素ABC栈顶栈的基本操作步骤三：定义栈的抽象数据类型任务实施栈的抽象数据类型ADT栈（Stack）数据对象：

D={ai|0≤i≤n-1,n≥0,ai为E类型}数据关系:

R={<ai,ai+1>|ai,ai+1∈D,i=0,...,n-2}数据操作：

将对栈的基本操作定义在接口IStack中，代码如下:public

interface

IStack<E>{void

init();//创建一个空的栈Epush(Ea);//入栈Epop();//出栈Epeek();//取栈顶元素intsize();//返回栈中元素的个数booleanempty();//判断栈是否为空}数据结构中的栈，类似生活中的积木塔，遵循后进先出（LIFO）的规则。它以高效且有序的方式管理数据，确保最后放入的元素最先被取出。这种结构在编程中广泛应用，从函数调用到撤销操作，栈以其简洁而强大的特性，为复杂问题提供了一种高效而优雅的解决方案。任务二

用顺序栈实现迷宫探路学习目标掌握栈的顺序存储结构掌握顺序栈的实现方法12能用顺序栈实现迷宫探路3

在任务一中，己分析出迷宫探路问题中通路的逻辑结构为栈，并定义了栈的抽象数据类型。接下来考虑将逻辑结构为栈的通路存储到计算机中去，进行存储结构的设计。存储结构有顺序存储结构和链式存储结构两种，本任务将栈的逻辑结构映射成顺序存储结构，并基于顺序存储结构实现栈的基本运算，最后，将实现的顺序栈应用在迷宫探路问题中，编写程序实现迷宫探路。任务描述步骤一：将栈的逻辑结构映射成顺序存储结构任务实施栈的顺序存储结构用一片连续的存储空间来存储栈中的数据元素，这样的栈称为顺序栈(sequencestack)。栈顶指示器top设在数组最后一个元素所在的位置，top随着插入和删除而变化。当栈为空时，top=-1

创建一个顺序栈创建一个顺序栈类SeqStack<E>，该类实现接口IStack<E>。定义3个类变量data、maxsize、top：data：为一维数组，用来存储栈中的数据元素，元素类型为泛型。maxsize：为表示顺序栈的最大容量，预先为顺序栈分配最大存储空间。top：设置一个变量top表示栈顶，随栈顶元素变动而变动，top的范围是0~maxsize-1，如果顺序栈为空，top=-1。importjava.lang.reflect.Array;publicclassSeqStack<E>implementsIStack<E>{privateE[]data;//存储顺序栈中数据元素的数组private

int

maxsize;//顺序栈的最大容量private

int

top;//顺序栈的栈顶指示器//初始化线性表

……//实现接口的代码……}初始化顺序栈初始化顺序栈就是创建一个空栈，即调用SeqStack<E>的构造函数，申请顺序存储空间：maxsize：初始化maxsize为实际值。data：为数组申请可以存储maxsize个数据元素的存储空间，数据元素的类型由实际应用而定。top：初始化top的值为-1

importjava.lang.reflect.Array;publicclassSeqStack<E>implementsIStack<E>{privateE[]data;//存储顺序栈中数据元素的数组private

int

maxsize;//顺序栈的最大容量private

int

top;//顺序栈的栈顶指示器//初始化线性表

publicSeqStack(Class<E>type,int

size){

maxsize=size;data=(E[])Array.newInstance(type,size);

top=-1;}//实现接口的代码……}顺序栈是一种高效的数据结构，通过数组实现，遵循“后进先出”的原则。入栈时，新元素按顺序紧密衔接，不断充实栈的深度；出栈时，顶部元素率先离开，为新内容腾出空间。凭借高效的操作，顺序栈在程序运行中，稳定支撑数据处理，助力代码稳健前行。步骤二：完成顺序栈的基本运算任务实施求栈长度、判断为空、判断为满//求顺序栈长度public

intsize(){return

top+1;}//判断顺序栈是否为空public

booleanisEmpty(){return

top==-1;}//判断顺序栈是否为满public

booleanisFull(){return

top==maxsize-1;}求表长度：返回栈中所有数据元素的个数。

参数：无。返回值：一个整数top+1，表示顺序栈中元素的数量。解释：由于数组索引通常是从0开始的，而元素数量是从1开始计数的。当top为0时，表示栈中只有一个元素；当top为1时，表示栈中有两个元素，以此类推。所以，栈中元素的数量就等于top+1。

判断为空：如栈中不包含任何数据元素，则返回true，否则返回false。

参数：无。返回值：布尔值。若顺序栈为空（top==-1），返回true；否则返回false。解释：如果top的值等于-1，说明当前顺序栈中没有元素，表达式的结果为true；如果top的值不等于-1，说明顺序栈中存在元素，表达式的结果为false。判断为满：如栈中数据元素个数己达到最大容量，返回true，否则返回false。

参数：无。返回值：布尔值。若顺序栈已满（top==maxsize-1），返回true；否则返回false。解释：top==maxsize-1是一个条件判断表达式。由于数组索引是从0开始的，所以当栈中存储了maxsize个元素时，栈顶元素的索引top就等于maxsize-1。

假设顺序栈顶端元素的索引保存在变量top中，栈中己有top+1(0≤(top+1)≤maxsize-1)个数据元素，将一个给定的数据元素保存在栈的最顶端入栈操作push(Ea)（1）判断栈是否是满的，如果是，返回null；否则执行下面的步骤。（2）设置top的值为top+1，top指向要入栈元素的位（3）设置top所指向的位置的值为入栈元素的值a，返回a//入栈操作publicEpush(Ea){

if(isFull())

return

null;++top;

data[top]=a;

return

a;}top-1取栈顶元素peek()出栈操作pop()（1）检查栈中是否含有元素，如果无，返回null；否则执行下面的步骤。（2）获取栈顶指针top指向的元素。//获取栈顶数据元素publicEpeek(){Ea=null;

if(!empty()){ a=data[top];}

returna;}步骤三：对顺序栈实现的基本运算算法进行测试任务实施使用栈数据结构进行元素的入栈和出栈操作。测试顺序栈publicclassTestStack{

public

static

void

main(String[]args){

int[]data={23,45,3,7,6,945};IStack<Integer>stack=new

SeqStack<Integer>(Integer.class,data.length);

//入栈操作

System.out.println("*******入栈操作*******");

for(inti=0;i<data.length;i++){ stack.push(data[i]);

System.out.println(data[i]+"入栈");

}

intsize=stack.size();

//出栈操作

System.out.println("*******出栈操作*******");

for(inti=0;i<size;i++){

System.out.println(stack.pop()+"出栈

");

}}}类定义:定义了一个名为TestStack的公共类。主方法:定义了程序的入口点，即主方法。数据初始化:定义并初始化了一个整型数组data，包含六个整数。栈的创建:创建一个栈实例。入栈操作:通过一个for循环，代码遍历data数组，并使用stack.push(data[i]);将每个元素依次入栈。同时，每次入栈后都会打印出当前入栈的元素值。获取栈的大小:获取栈中当前元素的数量，并将其存储在变量size中。出栈操作:通过另一个for循环，代码执行出栈操作size次。每次出栈后，都会打印出被移除的元素值。顺序栈，犹如数据结构中的璀璨明珠，凭借其独到之处彰显卓越操作风采。其入栈之举，恰似学识的沉淀，逐级堆砌，坚如磐石；而出栈之行，则如智谋的施展，井然有序，环环相扣。无论是探查栈顶奥秘，还是审视栈之虚实，顺序栈均以精确无瑕的执行力，演绎着数据处理之精妙与高效。任务三

用链栈实现迷宫探路学习目标掌握栈的链式存储结构掌握链栈的实现方法12能用链栈实现迷宫探路3

前面用顺序栈实现了迷宫探路，但在用顺序栈存储通路时，是有容量限制的，最大容量为maxsize，如果超过了这个容量，新探到的位置就无法加入通路中。为了解决这个问题，可以采用链式存储结构存储迷宫通路，本任务将栈的逻辑结构映射成链式存储结构，基于链式存储结构实现栈的基本运算，并将链栈应用在迷宫探路问题中。任务描述步骤一：将栈的逻辑结构映射成链式存储结构任务实施栈的链式存储结构用链式存储结构存储的栈称为链栈(linkedstack)。链栈通常用单链表来表示。链栈结点的结构与单链表结点的结构一样，由数据域data和引用域next两部分组成。栈顶指示器top指向最后一个入链的元素

链栈的结构示意图链栈的结点结构创建一个链栈创建一个链栈类LinkStack<E>，该类实现接口IStack<E>，接口中定义的基本运算的算法实现在步骤二完成。创建一个内部类Node,表示链栈的结点类型，包含两个成员变量：data是结点数据域，类型为泛型；next是下一个结点的引用域，类型为Node。定义一个类变量top，为栈顶指示器，指向单链表的头结点。public

classLinkStack<E>implementsIStack<E>{

private

classNode{Edata;Nodenext;

publicNode(Edata){

this.data=data;}

}

privateNodetop;//栈顶指示器//初始化链栈

……//IStack接口中定义的运算方法

……}初始化链栈初始化链栈就是创建一个空栈，即调用LinkStack<E>类的构造函数，初始化类变量设置栈顶指示器top为null。

public

classLinkStack<E>implementsIStack<E>{

private

classNode{Edata;Nodenext;

publicNode(Edata){

this.data=data;}

}

privateNodetop;//栈顶指示器//初始化链栈publicLinkStack(){

top=null;}//IStack接口中定义的运算方法

……}链栈作为数据结构的瑰宝，其基本操作闪耀着智慧的光芒。入栈时，元素如晨星般依次升起，井然有序；出栈时，它们又如落日般缓缓退场，不留遗憾。链栈的灵活性，如同舞者轻盈的步伐，在算法世界中翩翩起舞，引领我们探索更高效的编程之道，激发我们追求卓越的无限热情。步骤二：完成链栈类中栈的基本运算算法任务实施求栈长度、判断为空、判断为满//求链栈的长度public

intsize(){

int

size=0;Nodep=top;

while(p!=null){

size++;

p=p.next;}

return

size;} //判断链栈是否为空public

booleanisEmpty(){return

top==null;}求表长度：返回栈中所有数据元素的个数。初始化计数器：定义一个整型变量size并初始化为0，用于记录栈中节点的数量。设置起始节点：定义一个Node类型的变量p，并将其初始化为top，即栈顶的节点。遍历栈：使用while循环遍历栈中的节点。只要p不为null，即只要p指向一个有效的节点，循环就会继续。计数器递增：在循环体内，每次迭代都会使size的值增加1，以反映遍历到的每个节点。移动到下一个节点：将p更新为当前节点的下一个节点，以便在下一次迭代中处理。返回结果：当遍历完所有节点后，循环结束，方法返回size的值，即栈中元素的数量。判断为空：如栈中不包含任何数据元素，则返回true，否则返回false。

方法体只包含一行代码，检查top引用是否为null。如果top为null，则意味着栈中没有节点，则方法返回true,否则返回false。

入栈操作是将一个给定的数据元素保存在栈的最顶端，链栈中在单链表头部插入新节点。。入栈操作push(Ea)（1）创建一个新结点，为新结点分配内存和值。（2）如果栈不为空，将新结点的next指向栈顶指示器top所指向的结点。（3）将栈顶指示器top指向新结点。（4）返回新入栈的数据元素。//入栈操作publicEpush(Ea){Nodenewnode=newNode(a);

if(!empty())newnode.next=top;

top=newnode;

return

a;} 出栈操作是从栈的顶部取出数据，即从链栈的起始处删除一个结点出栈操作pop()（1）如果栈不为空，获取栈顶指示器top所指向结点的值。（2）将栈顶指示器top指向单链表中下一个结点。（3）返回获取的栈顶结点的值，栈为空时返回null。//出栈操作

publicEpop(){Ea=null;

if(!empty()){

a=top.data;

top=top.next;}

return

a;}取栈顶元素操作与出栈操作相似，只是取栈顶元素操作不改变原有栈，不删除取出的元素。出栈操作pop()（1）如果栈不为空，获取栈顶指示器top所指向结点的值。（2）返回获取的栈顶结点的值，栈为空时返回null。//获取栈顶数据元素publicEpeek(){Ea=null;

if(!empty()){

a=top.data;}

return