数据结构(java)-第3章剖析

《数据结构(java)-第3章剖析》由会员分享，可在线阅读，更多相关《数据结构(java)-第3章剖析（35页珍藏版）》请在金锄头文库上搜索。

1、,基本内容,第3章 栈（Stack）和队列 (Queue),1、栈的定义 栈（Stack）是一种特殊的线性表，它限定其中的元素只允许在线性表的一端进行插入和删除操作。允许操作的一端称为栈顶（top），不允许操作的另一端称为栈底（bottom）。,一.栈的定义和运算,2、栈的运算 栈的基本运算主要有以下几种： （1）创建栈：initiate(s) 初始条件：栈不存在 操作结果：构造一个空栈s （2）判栈空：isEmpty() 初始条件：栈已存在 操作结果：若栈为空栈，返回true，否则返回false。 （3）判栈满：isFull() 初始条件：栈已存在 操作结果：若栈为满栈，返回true，否则返

2、回false。,（4）进栈：push(x) 初始条件：栈已存在且未满 操作结果：插入一个新元素x进栈，并使栈顶指针指向它。 （5）出栈：pop() 初始条件：栈已存在且非空 操作结果：删除栈顶元素，并返回其值。 （6）取栈顶元素：peek() 初始条件：栈已存在且非空 操作结果：返回栈顶元素，这一操作并不改变栈的当前状态。,栈的抽象数据类型用Java接口描述如下： /* * 栈接口 */ public interface Stack boolean isEmpty(); boolean isFull(); boolean push(Object element); Object pop();

3、Object peek(); ,二、栈的存储和实现,1、顺序栈 采用顺序存储结构实现的栈简称为顺序栈，它利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设栈顶指针top指示栈顶元素的位置。下图演示了从一个空栈开始，在依次执行一系列入栈、出栈操作的过程中，顺序栈中数据元素的变化。,A进栈操作 进栈操作是在栈顶位置插入一个新元素element，其基本步骤如下： （1）判断待插入的新元素引用是否为null，如果是则算法结束并返回false，表示进栈失败。否则继续执行第（2）步； （2）判顺序栈是否已满，如果是如果是则算法结束并返回false，表示进栈失败。否则继续执行第（3）步； （

4、3）栈顶指针top加1； （4）将新元素element存入top所指向的位置，使其成为新的栈顶元素。进栈成功，算法结束并返回true。,B出栈操作 出栈操作是将栈顶元素从栈中移去，并返回其值。其基本步骤如下： （1）判顺序栈是否为空，如果是则算法结束并返回null，表示出栈失败。否则继续执行第（2）步； （2）栈顶指针top减1； （3）返回原来的栈顶元素，算法结束。,/* * 顺序栈 */ public class SeqStack implements Stack final int MAX_STACK=100;/栈的最大容量 private Object value;/数组value用来

5、存储栈的元素 private int top;/栈顶指针，其值为栈顶元素在数组中的下标 public SeqStack() /构造顺序栈 value = new ObjectMAX_STACK; top = -1;/初始状态，空栈 ,public boolean isEmpty()/判断顺序栈是否为空 return top=-1; public boolean isFull()/判断顺序栈是否已满 return top=MAX_STACK-1; public boolean push(Object element)/元素element入栈 if(element=null) return fal

6、se; if(isFull() return false; top+; valuetop=element; return true; ,public Object pop()/出栈，栈顶指针下移 if(!isEmpty() return valuetop-; else return null; public Object peek()/读取栈顶元素 if(!isEmpty() return valuetop; else return null; ,2、链栈 采用链式存储结构实现的栈简称为链栈。链栈的容量可以动态增长和缩小，这里用单链表来描述。单链表的第一个结点为栈顶结点，链栈中结点的定义与第二

7、章中单链表相同。,A.入栈操作 设top指向栈顶结点，将一个新结点X插入链栈的操作如下： （1）实例化一个新的结点对象，其值为X； （2）修改X结点的指针域，使其指向原来的栈顶结点； （3）更新top指针，指向X结点。,B.出栈操作 设top指向栈顶结点，链栈的出栈操作如下（参考图3.5）： （1）修改top指针，使其指向原来的栈顶结点的直接后继； （2）返回原来的栈顶结点值。,/* * 链栈 */ public class LinkedStack implements Stack private Node top;/栈顶指针 public LinkedStack() /构造链栈，初始为空 t

8、op = null; public boolean isEmpty()/判断链栈是否为空 return top=null; ,public boolean isFull()/判断栈是否已满 return false; public boolean push(Object element)/元素element入栈 if(element=null) return false; top=new Node(element,top); return true; ,public Object pop()/出栈 if(!isEmpty() Object tmp=top.getData(); /取得栈顶元素值

9、 top=top.getNext(); /出栈，指针后移， return tmp; else return null; public Object peek()/读取栈顶元素 if(!isEmpty() return top.getData(); else return null; ,三、队列的定义和运算,1、队列的定义 队列是一种“先进先出”（First In First Out）的线性表。假设有n个元素的队列Q=（a1，a2，an），队列中的元素按a1，a2，an的次序入队，将同样按a1，a2，an的次序出队。入队是指向队列插入元素，出队是指删除队列中的元素。,2、队列的运算 队列的基本运

10、算主要有以下几种： （1）创建队列：initiate(q) 初始条件：队列不存在。 操作结果：构造一个空队列q。 （2）判队列空：isEmpty() 初始条件：队列已存在。 操作结果：若队列为空队列，则返回true，否则返回false。 （3）判队列满：isFull() 初始条件：队列已存在。 操作结果：若队列为满队列，则返回true，否则返回false。该运算适用于队列采用顺序存储结构时。,（4）入队：enQuene(element) 初始条件：队列已存在且未满。 操作结果：插入某一个新元素element进入队尾，同时将队列的长度加1。 （5）出队：deQueue() 初始条件：队列已存在且

11、非空。 操作结果：删除队列头元素，同时将队列的长度减1。 （6）取队列头元素：peek() 初始条件：队列已存在且非空。 操作结果：返回队列头元素的值。 （7）求队列长度：getSize() 初始条件：队列已存在。 操作结果：返回队列的长度。,/* * 队列接口 */ public interface Queue boolean isEmpty(); boolean isFull(); boolean enQuene(Object element); Object deQueue(); Object peek(); int getSize(); ,四、队列的顺序存储结构,1、顺序队列 用内存中

12、一组连续的存储单元按顺序存放队列中的数据元素，简称顺序队列，通常用一维数组来实现。同时附设两个指针front和rear，front指向队列头元素的位置，rear指向队列尾元素的位置。,2、循环队列 构造一个循环队列Q。队列中有3个元素：2、0、11。,循环队列的入队和出队操作 （a）“2”出队 （b）“5”入队 （c）“22”入队,/* 循环队列 */ public class SeqQueue implements Queue private final int MAX_QUEUE=100;/数组的默认容量 private Object value;/对象数组 private int fro

13、nt;/队头指针 private int rear;/队尾指针 private int count;/计数器 public SeqQueue() /构造空队列 value=new ObjectMAX_QUEUE; front=0; rear=MAX_QUEUE-1; count=0; ,public boolean isEmpty() /判断队列是否为空 return count=0; public boolean isFull() /判断队列是否已满 return count=MAX_QUEUE; public boolean enQuene(Object element)/入队 if(!i

14、sFull() valuerear=element; rear=(rear+1)%MAX_QUEUE; count+; return true; return false; ,public Object deQueue()/出队 if(!isEmpty() Object temp=valuefront; front=(front+1)%MAX_QUEUE; count-; return temp; return null; public Object peek()/取队头元素 if(!isEmpty() return valuefront; return null; ,/查询队列长度 publ

15、ic int getSize() return count; ,五、队列的链式存储结构,1、链队列 队列的链式存储结构简称链队列，通常用带头指针（front）和尾指针（rear）的单链表来实现。,A.入队操作的步骤如下： （1）实例化新结点对象X，其next指针域为null； （2）修改rear指向的当前队尾结点的next指针域，使其指向新结点X； （3）更新rear指针，使其指向新的队尾结点X。,B.出队操作的步骤如下： 修改队头指针front，使其指向当前队头结点的下一个结点。 若队列中仅有1个结点，front=null，同时还需要将rear也重置为null。,/* 链队列*/ public class LinkedQueue implements Queue private Node front;/指向队头 private Node rear;/指向队尾 /构造空队列 public LinkedQueue() front=null; rear=null; /判断队列是否为空 public boolean isEmpty() return front=null; /判断队列是否已满 public boolean isFull() return false; ,public boolean enQuene(Object e