数据结构和算法分析：第三章表、队列和栈

刺骨的言语ヽ痛彻心扉 2022-05-04 13:28 217阅读 0赞

# 3.1 抽象数据类型 #

**抽象数据类型** 是带有一组操作的一些对象的集合。对于集合ADT可以有像添加add、删除remove、包含contain这样的一些操作

# 3.2 表ADT #

## 3.2.1 表简单的数组实现 ##

只发生对数组的访问（即只有findKth操作）。在这种情况下数组是表的一种切当的的实现。然而，如果发生插入和删除操作，特别是对表的前端进行，那么数组就不是一个好的选择。

## 3.2.2 简单链表 ##

为了避免插入和删除的线性操作，我们介绍简单链表

链表好处：在实践中，如果我们知道变动将发生的地方，那么向链表中插入或者从链表中删除一项的操作不需要移动很多的项，而只涉及常数个节点链的改变。

**双向链表**  
![在这里插入图片描述][70]

# 3.3 Java Collection API 中的表 #

## 3.3.1 Collection 接口 ##

![在这里插入图片描述][70 1]

*  size 返回集合中的项数
 *  isEmpty 返回true当且仅当集合的大小为0.
 *  如果x在集合中，则contains返回true
 *  add 和remove 从集合中删除和添加元素

## 3.3.2 Iterator接口 ##

![在这里插入图片描述][70 2]

实现Iterator接口的集合必须提供一个iterator方法，该方法返回一个Iterator类型的对象。主要用于java 增强for循环。

Iterator接口还包含一个方法，叫做reomve方法。该方法可以删除由next最新返回的项。Iterator的remove方法的主要优点在于，Collection的remove方法必须首先找到要被删除的项，这样的开销很大。

## 3.3.3 List接口、ArrayList接口和LinkedList接口 ##

![在这里插入图片描述][70 3]

*  get和set方法使得用户可以访问或者改变通过由位置索引idx给定的表中指定位置的项。
 *  add使得在位置idx处置入一个新的项（并把其后的项向后移动一个位置）
 *  除了Collection提供的以AnyType作为参数的标准remove之外，remove还不重载以删除指定位置的项。

请简易说一下ArrayList和LinkedList的优点和缺点：

List的ADT有两种流行的实现方式。ArrayList提供了ListADT的一种可以增长数组的实现方式。使用ArrayList的优点在于，对get和set的调用花费常数的时间。其缺点是新项的插入和删除的代价昂贵。LinkedList提供了ListADT的双向链表的实现，它的优点在于，新项的插入和删除的开销很小，它的缺点是它不容易作为索引，因此对get的调用时昂贵的。

对于搜索来说，ArrayList和LinkedList都是低效的。

ArrayList中有一个容量的概念，它表示基础数组的大小。在需要的时候，ArrayList能够自动增加其容量来保证它至少具有表的大小。

## 3.3.5 关于ListIterator接口 ##

![在这里插入图片描述][70 4]

# 3.6 栈ADT #

## 3.6.1 栈模型 ##

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶部（top）。对战的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者则是删除最后插入的元素。

栈有时候有叫做（后进先出表）

## 3.6.2 栈的实现 ##

**栈的链表的实现**

栈第一种实现方法就是使用单链表。通过在表的顶端插入来实现push，通过删除表顶端元素来实现pop。top操作只是考察元素顶端并返回它的值。

**栈的数组的实现**

与每个栈相关联的操作是theArray和topOfStack。将某个元素压入栈中，我们使topOfStack增加1然后置theArray\[topOfStack\]=x。为了弹出栈元素，我们置返回值为theArray\[topOfStack\]然后使topOfStack减1.

# 3.7 队列ADT #

## 3.7.1 队列的基本模型 ##

队列的基本操作是enqueue（入队），它是在表的末端（叫做队尾（rear））插入一个元素，和dequeue（出队），他是删除并在表的开头（叫做队头（front））的元素。

## 3.7.2 队列的数组的实现 ##

对于每一个队列数据结构，我们保留一个数组theArray以及位置front和back，他们表示队列的两端。我们还要记录实际存在队列中的元素个数currentSize。  
![在这里插入图片描述][70 5]  
为了使一个元素x入队（即执行enqueue），我们让currentSize和back自增1，然后置theArray\[back\]=x。若使元素dequeue出队，我们置返回值theArray\[front\]，且currentSize减一，然后front自增1.  
**循环数组**

[70]: /images/20220504/b303524868664bf0a0b136d20fd27f35.png
[70 1]: /images/20220504/c72ec8c8d8744e4290fdac0e5770e72d.png
[70 2]: /images/20220504/45ea2e9de5b04973b6adfda797973e4e.png
[70 3]: /images/20220504/0dc19ebf87184ad9af6ed07617e9c13c.png
[70 4]: /images/20220504/2de43c5dbeb846b28d4a10adeaed60ce.png
[70 5]: /images/20220504/7457b17531f34656b47a2a86f39d30dc.png