首页  思维笔记  详情

数据结构与算法-第3章.表栈队列

2021-09-07 20:35:18   38  举报





数据结构与算法分析-java语言描述这本书的学习总结,持续学习更新中

学霸笔记

数据结构与算法

Collection 集合

作者其他创作

大纲/内容

一.介绍抽象数据类型的概念

抽象数据类型(abstract data type, ADT)是带有一组操作的一些对象的集合

对于集合ADT,可以有像添加/删除以及包含这样的一些操作,当然也可以只要两种操作并和查找,这两种操作又在这个集合上定义了一种不同的ADT

本章将要讨论的这三种数据结构是ADT的最基本的例子. 我们将会看到它们中的每一种是如何以多种方法实现的. 

二.阐述如何有效地执行表的操作

1. 表的简单数组实现

1.1 数组在必要时进行扩容

1.2 数组的实现可以使得printList以线性时间执行

1.3 findKth操作则花费常数时间

1.4 插入和删除潜藏着昂贵的开销

1.5 使用它的最好场景是,通过在高端进行插入操作,其后只发生对数组的访问.

2. 简单链表

2.1 结构

2.2 printList  只要从表的第一个节点开始然后用一些后继的next遍历该表即可. 花费线性时间,和在数组是现实一样,不过其中的常数可能会比用数组实现时要大.

2.3 find(x) 遍历方法同上,不如数组实现时效率高.

2.4 remove可以通过修改一个next引用来实现

2.5 insert方法需要new一个新的节点,此后执行两次引用的调整.

2.6 如果知道变动将发生的地方,那么想链表中插入或删除一项的操作只涉及常数个节点链的改变.实际上删除最后一项比较复杂,因为必须找出指向最后节点的项,因为必须找出执行最后节点的项,把它的next链改成null,然后再更新持有最后节点的链.

所以我们的做法是,让每个几点持有一个指向它在表中的前驱节点的链.,即双链表.

3. Java Collections Api 中的表(方法及算法复杂度介绍)

3.1 Collection接口

java.util包中Collection接口的子集

扩展了Iterable接口. 可以拥有增强的for循环

3.2 Iterator接口

3.2.1 概述

3.2.2 next 给出集合的(尚未见到的)下一项

3.2.3 hasNext 给出是否存在下一项.

3.2.4 remove 删除由next最新返回的项(此后,我们不能再调用remove,知道对next再一次调用以后).

3.3 List接口

3.3.1 ArrayList:List ADT的一种可增长数组的实现

优点:对get和set的调用花费常数时间

缺点:插入和删除代价昂贵,除非是在末端进行

3.3.2 LinkedList : List ADT的双向链表实现

优点:假设变动项的位置是已知的,那么插入和删除开销很小.

缺点:不容易索引,get的调用时昂贵的.

3.3.3 两者在一些方法上的时间复杂度区别

在末端添加项来构造List: ArrayList和LinkedList的运行时间都是O(N)

在标的前端添加项来构造List: ArrayList运行时间是O(N的平方), LinkedList是O(N).

计算List中的数的和: ArrayList是O(N),LinkedList是O(N的平方)

搜索方面两种List都是抵消的,对Collection的contains和remove两个方法的调用均花费线性时间.

3.4 通过remove方法的使用来理解

需求:讲一个表中所有具有偶数值的项删除.于是,如果表包含6,5,1,4,2, 则在该方法调用之后,表中仅有元素5,1.(不考虑构造一个包含所有的奇数的新表,然后清除原表,并将这些奇数拷贝回原表的方法)希望写一个干净的避免拷贝的表,并在遇到那些偶数值的项时将它们从表中删除.

第一种思路:通过get来删除项. ArrayList和LinkedList都是花费二次时间.

第二种思路:使用迭代器一步步遍历: 使用迭代器一步步遍历该表,本身是高效的,但是我们使用Collection的remove方法必须再次搜索该项后才能删除,本身会花费线性时间,所以这也不高效,并且该程序会产生一个异常,因为当一项被删除时,由增强for所有使用的基础迭代是非法的. 因为增强for循环不懂得仅一项不被删除时它才能往前推进.

第三种思路:这是一个正确思路,使用迭代器来删除. ArrayList仍然是二次,而对LinkedList却是线性的.

3.5 ArrayList类的实现(书里是自己实现了一个MyArrayList来了解它的实现方式)

3.5.1 主要细节

(1) MyArrayList将保持基础数组,数组的容量,以及存储在MyArrayList中的当前项数.

(2) MyArrayList将提供一种机制,以改变基础数组的容量. 通过获得一个新数组, 将老数组拷贝到新数组中来改变数组的容量,允许虚拟机回收老数组

(3) MyArrayList将提供get和set的实现.

(4) MyArrayList将提供基本的例程,如size,isEmpty和clear,它们是典型的单行程序. 还提供remove,以及两种不同版本的add. 如果竖着的大小和容量相同,那么这两个add例程将增加容量.

(5) MyArrayList将提供一个实现Iterator接口的类. 这个类将存储迭代序列中的下一项的下标,并提供next,hasNext和remove等方法的实现.MyArrayList的迭代器方法直接返回实现Iterator接口的该类的新构造的实例.

3.5.2 基本类

简单短例程

ensureCapacity容量的扩充

add方法

remove方法

3.5.3 迭代器,java嵌套类和内部类

版本一(有问题)

(1)ArrayListIterator是泛型类,它存储当前位置.

(2)程序在next方法中使用当前位置作为下标访问数组元素,然后将桑倩位置向后推进.

(3)这个程序的问题是theItems[current++]是非法的,因为theItems不是ArrayListIterator的一部分,它是MyArrayList的一部分.所以我们准备使用版本二

版本二(有问题)

(1)这段程序确实解决了迭代器中没有数组的这个问题.

(2)问题在于theItems是MyArrayList中的私有域

(3)间接的办法是修改theItems在MyArrayList中的可见性,但是这违反了良好的面向对象编程的基本原则,它要求数据应尽可能地隐蔽.

版本三(正确运行)_嵌套类版本

(1)这种方案是使ArrayListIterator作为嵌套类

(2)外层的MyArrayList即为外部类

(3)用static修饰便是嵌套类,无static修饰即为内部类.

(4)改成这样后,即使theItems在MyArrayList中为private也可以被嵌套类访问了.因为嵌套类被认为是外部类的一部分,所以不存在可见性问题.

(5)仍然存在问题:不能直接引用其所在的MyArrayList.

版本四(正确运行)_内部类版本

当声明一个内部类时,编译器则添加对外部类对象的一个隐式引用,该对象引起内部类对象的构造.

theList.theItems不再需要,可以由MyArralyList.this.theItems代替,更简化一点可以直接简写为theItems.

由于迭代器的remove可能与MyArrayList的remove冲突,因此必须使用MyArrayList.this.remove.注意该项被删除后,一些元素需要移动,因此current被视为同一元素也必须移动.

3.6 LinkedList类的实现(书里自己实现了一个MyLinkedList以了解它的实现方式)

3.6.1 主要细节

LinkedList将作为双向链表实现,保留到该表两端的引用.并包含表的大小及一些方法

Node类,它可能是一个私有的嵌套类.一个节点包含数据,前一个节点的链,下一个节点的链,以及适当的构造方法

LinkedListIterator类,该类抽象了位置的概念,是一个私有类,并实现接口Iterator.它提供了next,haseNext和remove的实现.

3.6.2 头节点和尾结点

头结点和尾节点都是额外节点,里面没有数据,头结点链接着我们的第一个数据节点,尾节点链接着我们的最后一个数据节点.

带有头节点和尾节点的双链表结构

空链表结构

3.6.3 Node节点

3.6.4 数据成员

beginMarker:头节点引用

endMarker:尾节点引用

size:数据大小

modeCount:代表自从构造依赖对链表所做的改变的次数.

3.6.5 clear 

3.6.6 add

方法: 下面的方法可以合并一下 p.prev = p.prev.next = new Node(x,p.prev,p)

图解: 

3.6.7 remove

方法

图解: 如果删除p仅需要p的前一个节点和p的后一个几点的链变动一下.

3.6.8 getNode

3.6.9 LinkedListIterator

okToRemove : 这个字段初始值为false,调用next方法后会变成true,调用remove方法后还会变成false

next方法返回当前current节点的同时,会把current向后一个节点推进.

三.介绍栈ADT及其在实现递归方面的应用

1. 概述

栈又叫做LIFO(后进先出)表,栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈的顶.也就是只有栈顶元素是唯一的可见元素.

对栈的基本操作有push(进栈)和pop(出栈),前者相当于插入,后者则是删除最后插入的元素.

对空栈进行pop或top一般被认为是栈ADT中的一个错误.

当运行push时空间用尽是一个实现限制,但不是ADT错误

2.实现

2.1 栈的链表实现

使用单链表来实现.通过在表的顶端插入来实现push,通过删除表顶端元素实现pop. top操作只是考查表顶端元素并返回它的值.有时pop操作和top操作合二为一.

2.2 栈的数组实现

模仿ArrayList的add操作,因此相应的实现非常简单.这样我们需要知道topOfStack(栈顶的索引).

对于空栈,栈顶索引是-1

push: 入栈x, 使topOfStack增1然后置theArray[topOfStack] = x. 

pop: 返回值为theArray[topOfStack],然后topOfStack减1.

这些操作以非常快的常熟时间运行.

3. 应用

3.1 平衡符号

可以用来检测语法错误,比如是否缺少符号.序列[()]是合法的,但[(]是错误的

算法描述:

做一个空栈,读入字符直到文件结束.

如果字符是一个开放符号,则将其推入栈中.

如果字符是个封闭符号, 将栈弹出(栈空时报错).

如果弹出的符号不是对应的开放符号,报错

在文件结尾,如果栈非空则报错.

3.2 后缀表达式

背景描述

比如我们有一个简单的便携式计算器想要计算一趟外出购物的花费.买了三种东西分别是4.99元,5.99元,6.99元. 其中两种需要上税.输入这些数据的自然的方式是:4.99 * 1.06 + 5.99 + 6.99 +1.06. 如果我们的计算器是简单计算器,不知道乘法优先于加法.那么需要我们记住中间的结构

过程描述

该例的典型计算书序可以是将4.99和1.06相乘并存为A1,然后将5.99和A1相加,再将加过存入A1;我们在将6.99和1.06相乘`并将答案存为A2.最后将A1和A2相加并将最后结果放入A1.我们可以将这种操作顺序书写如下: 4.99 1.06 * 5.99 + 6.99 1.06 * +,这个记法叫作后缀或逆波兰记法,其求值过程签好就是上面所描述的过程.

算法描述:这个问题最容易的方法就是使用一个栈

当见到一个数时就把它推入栈中

在遇到一个运算符时该运算符就作用于从该栈弹出的两个数上

再将上面的结果重新推入栈中

举例说明:

比如后缀表达式:6 5 2 3 + 8 * + 3 + *

计算过程:

前四个字符放入占中,此时栈变成

下面读到一个+号,搜一3和2从栈中弹出并且它们的和5被压入栈中

接着,8进栈

遇到一个*号,因此8和5弹出并且5*8=40进栈

接着遇到一个+号,因此40和5倍弹出并且5+40=45进栈

现在将3压入栈中

然后+使得3和45从栈中弹出并将45+3=48压入栈中

最后,遇到一个*号,从栈中弹出48和6,将结果6*48=288压进栈中

复杂度:O(N)

3.3 中缀到后缀的转化

背景描述

我们也可以使用栈,把一个正常的表达式(又称中缀表达式)转化成一个后缀表达式.(这里仅允许操作+ * ( ) ), 比如中缀表达式:a+b*c+(d*e+f)*g 转换后缀表达式,正确的答案是 abc*+de*f+g*+

算法描述:

当读到一个操作数的时候,立即把它输出.

操作符(右括号除外)是需要推入栈中,推入栈中之前要与栈顶元素的优先级大小进行比较,如果栈顶元素优先级高于当前操作符,则栈顶元素弹出并输出.继续与下一个栈顶元素比较,重复上述过程.直到栈顶元素的优先级低于当前操作符,当前操作符可以入站

左括号有些特殊,希望左括号既不引起操作符的出栈,也不会因为右括号之外的操作符出栈. 所以在入栈时,左括号的优先级可以看做最高,而在出栈比较时,左括号的优先级可以看做最低.

右括号也是特殊的,当前操作符是右括号时,栈内元素依次弹出并输出,直到弹出左括号为止.(左括号只弹出不输出)

举例说明

首先,符号a被读入,于是它被传向输出.然后,+被读入并放入栈中,接下来b读入并流向输出.这一刻的状态如下:

接着*号被读入.操作符栈的栈顶元素比*的优先级低,故没有输出且*进栈.接着c被读入并输出.至此,我们有

后面的符号是一个+号,检查一个栈我们发现,需要将*从栈弹出并把它放到输出中,弹出栈中剩下的+号,该算符不比刚刚遇到的+号优先级低而是有相同的优先级,然后,将刚刚遇到的+号压入栈中.

下一个被读到的符号是一个(,由于有最高的优先级,因此它被放进栈中.然后,d读入并输出.

继续进行,我们又读到一个*.由于除非正在处理右括号,否则左括号不会从栈中弹出,因此没有输出.下一个c,它被读入并输出

再往后读到的是+号.我们将*弹出并输出,然后将+压入栈中.这以后,我们读到f并输出.

现在我们读到了一个),因此将栈元素全部弹出直到(,我们讲一个+号输出

下面又读到一个+,该算符被压入栈中.然后g被读入并输出.

现在输入为空,因此我们将栈中的符号全部弹出并输出,知道栈变成空栈

复杂度:O(N)

3.4 方法调用

当存在方法调用的时候,需要存储所有的重要信息,诸如寄存器的值(对应变量的名字)和返回地址(它可以从程序计数器得到,一般情况是在一个寄存器中)等,都要以抽象的方式存在"一张纸上"并置于一个堆的顶部.然后控制转移到新的方法,该方法自由地用它的一些值代替这些寄存器.如果它又进行其他的方法的调用,那么它也遵循相同的过程.当该方法要返回时,它查看堆顶部的那张"纸"并复原所有的寄存器,然后进行返回转移.

显然全部的工作均可由一个栈来完成,而这正是实现递归的每一种程序设计语言中实际发生的事实.所存储的信息或称为活动记录,或叫做栈帧.

栈空间用尽的情况总是可能发生的,发生这种情况通常是由失控递归(忽视基准情形)的指向引起的.另一方面,某些完全合法并且表面上无问题的程序也可以越出栈空间.比如如下程序,如果这个集合含有20000个元素要打印,那么就要有表示第10行的嵌套调用的20000个活动记录的栈.一般这些活动记录由于它们包含了全部信息而特别庞大,因此这个程序很可能要越出栈空间.

这个程序是尾递归使用极端不当的例子,尾递归是涉及在最后一行的递归调用.尾递归可以通过将代码放到一个while循环中并用每个方法参数的一次赋值代替递归调用而被手工消除.它模拟了递归调用,因为它什么也不需要存储,在递归调用结束之后,实际上没有必要知道存储的值.因此,我们就可以带着在一次递归调用中已经用过的那些值转移到方法的顶部.

四.介绍队列ADT及其在操作系统和算法设计中的应用

1. 概述

像栈一样,队列也是表.然而,使用队列时插入在一端进行而删除则在另一个端进行.

2. 队列的数组实现

2.1 如同栈的情形一样,对于队列而言任何的表的实现都是合法的.对于每一种操作,链表实现和数组实现都给出快速的O(1)运算时间.这里讨论数组的实现方式.

2.2 简单数组实现队列(存在问题,经过不断的入队出队,就算当前队列里元素个数小于队列的长度,也不可避免的需要扩容)

保留一个数组theArray以及位置front和back,它们表示队列的两端.我们还要记录实际存在于队列中的元素的个数currentSize

操作描述

当一个元素x入队(即执行enqueue),我们让currentSize和back+1,然后置theArray[back] = x.

若使元素dequeue(出队),我们置返回值为theArray[front],且currentSize-1,而fron+1.

潜在问题:

经过10次enqueue后队列似乎是满了,因为back现在是数组的最后一个下标,而下一次再入队就会是一个不存在的位置.然而队列中也许只存在几个元素,远远小于队列的容量(因为可能有若干元素已经出队了).