栈与队列课件ppt课件.ppt

文档介绍：栈与队列
Tel:[phone] QQ;106159278
栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说，它们也是线性结构， 与线性表不同的是它们所支持的基本操作是受到限制的，它们是操作受限的线性bj = elements[top]; elements[top--] = null; return obj;
}
//取栈顶元素
public Object peek() throws StackEmptyException {
if (getSize()<1)
throw new StackEmptyException("错误，堆栈为空。");
return elements[top];
}
Tel:[phone] QQ;106159278
栈的链式存储实现
链栈即采用链表作为存储结构实现的栈。当采用单链表存储线性表后，根据单链表的操 作特性选择单链表的头部作为栈顶，此时，入栈、出栈等操作可以在Ο(1)内完成。由于堆 栈的操作只在线性表的一端进行，在这里使用带头结点的单链表或不带头结点的单链表都可 以。使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；使用不带头结点的 单链表时，结点的插入和删除都在链表的首结点上进行。
下面以不带头结点的单链表为例实现堆栈，图 4-2 给出了使用不带头结点的单链表实现堆栈的示意图。
Tel:[phone] QQ;106159278
图 4-2 中，top 为栈顶结点引用，始终指向当前栈顶元素所在结点。若 top 为 Null，则 表示空栈。入栈操作是在 top 所指结点之前插入新的结点，对照图 4-2 可以看到，当链表为 空和不为空时，入栈操作的实现都一样，可以使用以下语句来实现
SLNode q = new SLNode(e,top); //结点 q 的 next 域指向 top，不管 top 是否为 Null top = q;
同样对于出栈操作而言，不管堆栈在删除栈顶元素之后，栈是否为空，出栈操作都是将top 后移。
Tel:[phone] QQ;106159278
思考题
Stack 的链式存储实现
Tel:[phone] QQ;106159278
队列
队列（queue）简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许 在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）。向队尾插入元素称为进队或入队，新元素 入队后成为新的队尾元素；从队列中删除元素称为离队或出队，元素出队后，其后续元素成 为新的队首元素。
由于队列的插入和删除操作分别在队尾和队首进行，每个元素必然按照进入的次序离 队，也就是说先进队的元素必然先离队，所以称队列为先进先出表（First In First Out,简称 FIFO）。队列结构与日常生活中排队等候服务的模型是一致的，最早进入队列的人，最早得 到服务并从队首离开；最后到来的人只能排在队列的最后，最后得到服务并最后离开。
Tel:[phone] QQ;106159278
下面给出队列的抽象数据类型定义。
ADT Queue{
数据对象：D = {ai | ai∈D0，i=0, 1, 2…n-1，D0为某一数据对象}
数据关系：R = {<ai, ai+1> | ai, ai+1∈D，i=0, 1, 2 … n-2}
基本操作：
Tel:[phone] QQ;106159278
Tel:[phone] QQ;106159278
队列的顺序存储实现
队列的顺序存储实现中，我们可以将队列当作一般的表用数组加以实现，但这样做的 效果并不好。尽管我们可以用一个指针 last 来指示队尾，使得 enqueue 运算可在Ο(1)时间内 完成，但是在执行 dequeue 时，为了删除队首元素，必须将数组中其他所有元素都向前移动 一个位置。这样，当队列中有 n 个元素时，执行 dequeue 就需要Ο(n)时间。
为了提高运算的效率，我们用另一种方法来表达数组中各单元的位置关系。设想数组A[0.. capacity-1]中的单元不是排成一行，而是围成一个圆环，即 A[0]接在 A[capacity-1]的后 面。这种意义下的数组称为循环数组，如图 4-3 所示。
Tel:[phone] QQ;106159278
用循环数组实现的队列称为循环队列，我们将循环队列中从队首到队尾的元素按逆时针 方向存放在循环数组中一段连续的单元中。