ArrayLists, LinkedLists, Stacks and Queues

Gtx CS1332x I Notes

• Reference Equality: 查看两个对象是否为同一个对象（处于同一片内存区域），使用 == 检测
• Value Equality：按照用于自定义的规则来判断两者是否等价。使用自定义的，重写自 Object 类的 equals() 方法来判断。

上面两种比较的主要应用发生在 Primitives type 与 Object type 之间。

• primitive type：没有值和引用相等的区别，因此都用 == 来判断：

int one1 = 1;
int one2 = 1;
int two1 = 2;
one1 == one2; // => true
one1 == two1; // => false

String literal = "This is a string.";
literal == "This is a string.";              // => true

//ref equality
String object = new String("This is a string.");
object == "This is a string.";

//value equality
object.equals("This is a string.");          // => true

• Object 是否为 null 使用 == 来确定（null & 非 null 对象均可使用）

String nullObject = null;
nullObject == null;   // => true

• 如果对象为 null，调用 equal() 会导致 NPE （NullPointerException ）异常
  • 非 null 对象可以调用 equal() 与 null / null 对象比较

String normalObject = "normal";
normalObject.equals(null);       // => false
nullObject.equals(normalObject);  // causes NullPointerException

• 某些场景需要使用 primtive type 对应的对象。这类对象被称为 Wrapper Objects
• Java 会通过 autoBoxing / unboxing 自动进行转换

Wrapper Objects的比较 与 String Literal 类似，也分值等价和引用等价两种情况：

• Literal 的比较是值的比较

Integer primitive = 1;
Integer object = new Integer(1);
primitive == 1;             // => true
object == 1;                // => true

• Object 的比较是引用的比较

primitive == object;        // => false
primitive.equals(object);                 // => true
object.equals(primitive);                 // => true

• Pass By Value：传递的是值，更改 parameter 不影响 argument
• Pass By Reference：传递的是引用，更改 parameter 影响 argument

指在运行期，对象类型与生命类型不匹配。解决方式：使用带 type parameter 的特化版本：

public class Container<T> {
    private T t;
    public void set(T t) {
        this.t = t;
    }
    public T get() {
        return t;
    }
}

• Declaring Generic Classes

//def
class ArrayList<T> { ... }
//declar
ArrayList<Integer> listOne = new ArrayList<>();

//declar
T[] backingArray = (T[]) new Object[10];

class HashMap<K, V> { ... }
HashMap<String, Integer> map = new HashMap<>();

ArrayList<BSTNode<T>> nodeList = new ArrayList<>();

Java 提供了 Iterable 接口；任何实现该接口的类都可以使用 for-each loop。使用需要导入 java.util.iterator

实现上：

• 需要重写 iterator() 方法，该方法会返回一个 iterator 对象。

Iterator 也可以单独使用。需要重写的方法：

• 需要重写 next() 方法：返回当前 iterator 指向的对象，然后将 iterator 移动至下一个对象
• 需要重写 hasNext() 方法：当 iterator 指向的对象值不为 null 时，返回 true
• 可选重写 remove() 方法：移除 next() 返回的对象

两种简单的示例如下：

• 显式的使用 Iterator：

import java.util.Iterator;
public class BookList<Book> implements Iterator<Book> {
    
    //override
    public void next() {}
    public boolean hasNext() {}

public static void main(String[] args) {
    //usage suppose bookList is an object with type BookList<Book>
    while(bookList.hasNext())
    {
        System.out.println(BookList.next());
    }
}
}

• 使用 Iterable：

public class BookList<Book> implements Iterable<Book> {
    
    //In this case, Iterator function needs to be override
    public Iterator<Book> Iterator() {....}

public static void main(String[] args) {

}
    for(Book book : bookList) {
        System.out.println(book);
    }
}

• 两者都是独立实现的，并不互相依赖
• Comparable 允许直接将自身与目标进行比较（使用 comareTo 方法，单参数）
  • 允许实现类基于返回值定义 Nature Ordering（升序）

//public int compareTo(T y) ;
x.compareTo(y);

• Comparator 并不比较自身与目标，而是比较两个参数（使用 compare() 方法，双参数）
  • 允许实现类基于返回值定义 Ordering。这个顺序可以是基于任何值自定义的，与 Nature Ordering 有区别：
    • 比如基于学生的年龄进行降序排列
    • 比如基于学生专业的第一个字母进行基于 alphabet 的顺序排列

public int compare(T x, T y);
comp.compare(x, y);

• 负数：x < y
• 0：x = y
• 正数：x > y

实现上：

• Comparable 的实现需要实现 Comparable 接口，并重写 compareTo 方法
• Comparable 已经包含在 java.uitl 中，因此不需要任何导入

public class HDTV implements Comparable<HDTV>{
    ....
    public int compareTo(HDTV tv) {
        ....
    }
}

• Comparator 的实现需要导入 java.uitl.Comarator
• Comparator 需要实现的接口是 Comparator，需要重写 compare()，接收的是两个参数

class SizeComparator implements Comparator<HDTV> {
    public int compare(HDTV tv1, HDTV tv2) {
        //....
    }
}

• 算法&数据结构的效率通过时间和空间两个方面进行衡量
• 衡量是独立的，与平台无关。
• 衡量只研究输入规模变更时，算法的变化

算法在高级层面上通过如下的基础操作（primitive instruactions）进行衡量：

• 赋值
• 算术运算
• 比较两个实体
• 函数的调用、函数的返回
• 访问、引用数据结构

这些基础操作的共同点是，都能在常数时间内完成。因此，统计他们的总次数，就能直观的反应算法的复杂度。

• $f(n)$ 代表了在输入大小为 $n$ 时，基础操作的总数
• 三种要考虑的情况：
  • worst case （本课主要的讨论点）
  • best case
  • Avergae case

• $o(f(n))$：long-term performance is significantly upperbounded by f(n)。主要强调的是算法复杂度增长的很慢。
• $\Omega(f(n))$：$f(n)$ 被当做了衡量解决一个问题的难度；也就是告诉我们，解决该问题付出什么样的成本是合理的。
• $\Theta(f(n))$：$f(n)$ 同时作为 upperbound 和 lowerbound。不是所有的算法都有该复杂度，因为该复杂度需要算法足够稳定。

• 常量因子会被省略：比如 $O(5n)$ = $O(n)$
• 非 domiate 的项会被省略：比如 $O(n^2+100n-3) = O(n^2)$
• $log(n)$ 的 base 通常是 $2$

• 在内存中连续存储
• 通过 index 访问元素，访问的复杂度是 $O(1)$
• 内存是静态分配的，如果超出了需要申请新的，更大的连续空间，然后将元素全部拷贝过去。拷贝的复杂度是 $O(n)$

• 抽象数据类型（ADT）是一种描述数据类型的模型，通过其行为和操作定义。在 Java 中，ADT 与 Interface 类似（有定义，但没有具体的实现）。
• ADT 避免了在讨论需求的时候过多的陷入细节
  • 不涉及算法的具体实现和效率（数据结构才做这些讨论）
• 数据处理的具体实现被称为数据结构

• Generic type（只支持 object 类型）；使用时需要指定对象类型（可以被视作是 array 的 wrapper）
• 基于 Array 实现的 List，会自动 resize，空间增长会申请全新的空间，并将旧元素拷贝过来
• 数据是连续存储的，初始大小为 10
• 定义于 java.util

ArrayList<String> list = new ArrayList<>();

• Size 指 ArrayList 中已经存在的元素数量
• Capacity 指 ArrayList 中可以存放的元素上限

• 存储是连续性的（中间有 null 是不行的）
• zero-aligned（必须存在首元素）

• $O(1)$
• 如果要求 resize，则是 $O(n)$

• $O(n)$：需要移动元素的同时保证已有元素内容不被覆盖。

• remove from the back: $O(1)$
• remove from elsewhere $O(n)$

Amortized Analysis 是一种关注于平均计算成本的分析方法。通常的方法是以操作为单位来衡量计算成本，但有的时候某些高成本的操作出现的几率并不是很大，因此这种情况下使用此类操作来作为 worst case 讨论该算法的意义并不是很大。

以之前的 addToTheBack 为例，通常操作的复杂度为 $O(1)$，而 resize 时的复杂度为 $O(n)$；由于 resize 并不是很常见，那么以 $O(n)$ 来衡量 addTOTheBack 的复杂度显然不太精确。这种情况下，我们可以采用 Amortized Analysis 的方法来进行分析

• 首先需要分析 worst case 的情况分哪几种：
  
  • 如果没有 resize，每次 addToTheBack 只有两次操作：添加元素和增加 size 的计数。 那么 addToTheBack 的复杂度为: $$\texttt{Amortized Cost} = \frac{\texttt{Total cost of all operations}}{\texttt{times of operations}} = \frac{2n}{n} = 2 = O(1).$$
  • 如果发生了 resize：如果存在 $n$ 个元素，那么 resize 之后的 capacity 是 $2n$，那么对于每个元素来说，包含了 4次操作：
    • resize 有两次操作：访问元素，将元素拷贝到新的 arrayList
    • addToTheBack 有两次操作：添加元素，size 计数加一
  • 因此对于 $n$ 次操作，其 Amortized Cost 的计算方式为：$$\begin{align*} \texttt{Amortized Cost} &= \frac{\texttt{Total cost of all operations}}{\texttt{times of operations}} \\ &= \frac{\texttt{Resize Cost} + \texttt{Normal Operation Cost}}{n} \\ &= \frac{2n + 2n}{n} = 4 = O(1). \end{align*}$$ <WRAP center round box 100%> 以上两种复杂度都可以用于描述 addToTheBack 。如果需要强调该算法是基于 //Amortized Analysis// ，通常使用 $O(1)^*$ 来标注。

</WRAP>

• Soft Removals: 被删除的数据会被保留在数据结构中
• Hard Removals：被删除的数据会被完全移除出数据结构，并在必要的时候手动设置 null 作为代替

函数调用自身的方式被称为 Recursion。

• Base Case：必须至少有一个，作为递归终结的条件。
• Recursive Case：用于调用自身。当递归调用发生的时候，当前层的递归会暂停，知道调用返回结果以后才会继续运行。
• Progress to Base Case：所有的递归调用必须都往终结条件方向前景。

if (baseCase) {
   //termination
}
else {
    // recursive call logic
}

递归的一大重点就是将问题分解为子问题。一些策略：

• 先写出 base case, 再写出其他的递归方法
• 避免 base case 重复
• 将程序清晰的分解为不同的 case

使用递归形式的辗转相除法（Euclidean algorithm）：

• Base case: 余数 x mod y== 0
• Recursive case: gcd(x,y) = gcd(y, x mod y)

• 链表（LinkedLists ）由一系列的节点（Node）组成。数据存放在节点中。
• 链表中，前后节点通过指针链接。
• 链表不需要连续的存储空间。

• head：指向链表的头元素
• current：在遍历中，指向当前元素
• （可选）tail：指向链表的尾部元素

• size：记录链表的长度
  • 添加元素的时候 size 加一
  • 删除元素的时候 size 减一

• 成员：数据 T data，指向下个节点的指针 Node<T> next
• 方法：构造函数

链表的遍历基于 head 和 current：

• 起始条件（位置）为 current = head
• 结束条件（位置）为 current == null
• 循环条件：当当前节点的下一个节点不为空时，将下一个节点作为当前节点。

while (current != null) {
    current = current.next;
}

算法步骤：

1. 创建需要插入的节点
2. 将创建的节点的 next 指向 head 指向的内容
3. 将 head 原有的指向变更为被创建的节点

边界条件：
无。

public void addingToFront(T data) 
{   
    Node<T> newNode = new Node<>(data);
    newNode.next = head;
    head = newNode;
}

算法步骤：

1. 判断 list 是否为空。如果为空，直接创建节点
2. 否则，遍历到 List 的最后一个元素（while(current.next != null)）
3. 循环结束后，创建节点，并将最后一个元素的 next 指向新创建的节点

边界条件：

• 链表为空的时候不需要遍历，直接将 head 指向新创建的节点即可。

public void addingToBack(T data)
{
    if(head == null) {
        head = new Node<T> (data);
    } 
    else {
        Node<T> current = head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = new Node<T> (data);
    }
}

算法步骤：

1. 如果链表为空，返回 null
2. 将 head 重新指向第二个节点即可

边界条件：

• 链表为空，返回 null

public void removingFromFront()
{
    if(head == null) {
        return;
    }
    else {
        head = head.next;
    }
}

算法步骤：

1. 如果链表为空，返回 null
2. 如果链表只有一个节点，删除节点后 head = null
3. 否则，遍历链表到倒数第二个节点
   1. 将倒数第二个节点的 next 指向设置为 null

边界条件：

• 链表为空，返回 null
• 链表只有一个节点，删除节点后 head = null

public void removingFromBack()
{
    if(head == null) {
        return;
    }
    else if (head.next == null) {
        head = null;
    }
    else {
        Node<T> current = head;
        while(current.next.next != null) {
            current = current.next;
        }
        current.next = null;
    }
}

• tail 指针指向链表中最后一个节点。维护该指针可以在使用 addingToBack() 的时候避免重复遍历链表（$O(n)$ to $O(1)$）
• tail 指针对 removeFromBack() 没有任何优化。该方法需要访问倒数第二个节点，而不是最后一个节点。
• tail 指针使用的边界条件：
  • 当链表为空时：head 和 tail 都应该为 null
  • 当链表只有一个节点时：head 和 tail 都指向该节点。如果试图删掉该节点，那么 head 和 tail 都应该为 null

• 需要一个实现 Iterable 的类
• 需要一个实现 Iterator 的类，用于支持 Iterable 中的 Iterator() 方法的重写
• 在实现 Iterator 的时候需要重写：
  • next()
  • hasNext()

结构如下：

问题描述：

给定有序链表，以递归的方式移除列表中所有重复的元素。

相关思考：

递归的关键点就是将大问题分解为性质相同但规模更小的子问题。这个问题中，判断是否重复的行为最终都会转变为两个对象之间的比较。那么在递归的设计上，主要需要实现两点：

• 如何通过递归的方式来进行比较
• 比较的逻辑

实现思路：

首先应该对递归的状态进行建模。具体的问题就是：

• 递归的输入是什么？输出是什么？
• 递归是如何通过输入输出来缩小目标问题的规模的？

对于 list 的来说，子问题通常来说就是其 sublist。本例中的数据结构是链表，那么不难想到的是：

• 本题的 sublist 都应该是与目标链表 head 相同，但长度不同的子链表
• 缩减链表的方向因该是自尾部向头部进行

根据这个思路，再来考虑一下递归的输入和输出。sublist 是通过移除重复的对象来进行缩减的，而重复的判定是通过相邻的两个对象比较来进行的。如果希望递归完成这个过程，那么递归的参数和返回值都应该是进行比较的对象：

• 接收的参数参与当前的比较
• 返回值作为下一轮的值进行比较

按照这个思路往下看，base case 也可以明确了。当没有东西可以比的时候，也就是参数值为 null 时，就是我们的递归最终开始返回的时候。联系到之前，我们讨论过缩减规模的方向是从链表的尾部开始，因此有两个状态需要讨论：

• 当参数值为 null，也就是当前比较位置已经越过链表最后一位时，此时没有办法比较，直接返回 null
• 此时位置位于链表最后一位的栈接收到了 null，但 null 依然没法与当前元素比较，因此只能返回当前元素 curr

当这一层返回本层对象时，由于下一层的栈中已经有其对应对象在等待了，因此可以进行正常的比较了。因此，我们的比较逻辑可以确认为：

• 如果参数对象的值为 null，则返回 null
• 如果函数返回值为 null，则返回当前对象
• 否则，则判断当层栈中对象与返回的对象是否相等。如果相等，继续返回函数的返回值；否则则返回当层栈中的对象。

实现：

• wrapper 函数：公共接口，封装使用。

public void removeDups() {
    head = rRemove(head);
}

• 核心函数

private Node<T> rRemove(Node<T> curr) {
    if(curr == null) {
        return null;
    }
    else {
        curr.next = rRemove(curr.next);
        if(curr.next != null && curr.data.equals(curr.next.data)) {
            return curr.next;
        }
        return curr;
    }
}

1. 首先通过 head = rRemove(head) 开始调用。此时的 curr 在 head 处，值是 2
   1. 此时获取相邻的元素进行比较：curr.next = rRemove(curr.next)；由于 curr 不为 null，因此会进行下一次的 rRemove 调用。
2. 第二次调用，当前栈中的 curr ，也就是上一层的 curr.next，为 3()，依然不为 null，因此继续展开
3. 第三次调用，当前栈中的 curr 为 3,依然不是 null，因此展开
4. 第四次调用，此时 curr 的值已经为 null （3 已经是链表的最后一位）。至此整个递归调用拿到了第一个返回值，开始向下返回。
5. 第二次返回，此时 curr 是之前的 3(1st, 逆序）。因为 3(1st) 是链表最后一位，因此 curr.next == null，因此返回值为本层的 curr，也就是 3(1st)。
6. 第三次返回，此时 curr 是 3(2rd)。将其与返回的 3(1st) 比较，相等，因此返回 3(2rd.) 的 curr.next，也就是 3(1st) 。
7. 第四次返回，此时 curr 是 2。将其与返回的 3(1st) 比较，不等，因此返回 2。至此栈清空，递归结束。

Doubly-Linked Lists（双链表）在单链表的基础上添加了一个 previous 指针，用于指向之前的节点。双链表要求同时维护 head 与 tail。

算法步骤：

1. 创建新的节点
2. 指向下个节点：将新节点的 next 指针指向 head
3. 指向上个节点：将 head 所在节点的 previous 指针指向新节点
4. 重置 head：将 head 指向新节点

边界条件：

• 起始为空链表时，head 与 tail 都需要指向新创建的节点

算法步骤：

1. 创建新的节点
2. 指向上个节点：将新节点的 previous 指针指向 tail 所在节点
3. 指向下个节点：将 tail 所在节点的 next 指向新节点
4. 重置 tail：将 tail 指向新节点

边界条件：

• 起始为空链表时，head 与 tail 都需要指向新创建的节点

算法步骤：

1. 重置 head：将 head 指向 head.next 指向的节点（第二个节点）
2. 将 head 的前置信息清空：将 head.prev 指向设置为 null（第二个节点的 prev）

边界条件：

• 双链表长度为 1 时，移除节点需要 head 与 tail 同时被设置为 null

算法步骤：

1. 重置 tail：将 tail 指向 tail.previous 指向的节点（倒数第二个节点）
2. 指向下个节点：将倒数第二个节点的 next 指向设置为 null（也就是当前的 tail.next）

边界条件：

• 双链表长度为 1 时，移除节点需要 head 与 tail 同时被设置为 null

该算法基于 index 移除内容。

算法步骤：

1. 判断删除节点的位置否位于首尾 (0，或者 size-1)
   1. 如果是 0，删除节点为首节点，调用 removeToFront
   2. 如果是 size-1，删除节点为尾节点，调用 removesToBack
2. 如果都不是，那么添加位置处于链表中部。此时需要遍历到被移除节点的前置节点。根据 index 的位置靠前还是靠后，有两种选择：
   1. 如果被移除节点位置靠前 (index < size / 2)，那么从链表前端，也就是 head 开始遍历。遍历结束的位置为被移除节点的前一个节点
   2. 否则，被移除节点位置靠后，那么从 tail 开始遍历，遍历结束的位置为被移除节点的后一个节点
   3. 遍历使用 index 作为循环条件：$[0, index)$ 和 $[size-1, index)$
3. 缓存被移除的数据
4. 更新链接。以被移除节点为中心：
   1. 其前节点的 next 指向其后节点
   2. 其后节点的 previous 指向其前节点
5. 维护 size，返回被移除的数据

Circularly-Linked Lists (CLL) (环链表) 指尾部节点的 next 指向 head 的链表。

• 通常不包含 tail
• 循环终止的条件是 curr.next.equals(head)

算法步骤：

1. 创建新节点
2. 指向下个节点：将新节点的 next 指向 head 所在节点
3. 重置 head：将 head 指向新节点
4. 重置指向 head 的尾节点：需要再进行一次遍历。更新尾部节点的 next，使其指向更新后的 head（$O(n)$）

算法步骤：

1. 创建新节点：创建一个空的新节点
2. 插入节点：将新节点插入到 head 之后（index 1）
   1. 将新节点的 next 指向原来的第二个节点
   2. 将 head 的 next 重定向到新节点
3. 转移数据：将 head 内的内容拷贝到新节点中
4. 添加数据：将新的数据写入到 head 对应的节点中

算法步骤：

1. 创建新节点：创建一个空的新节点
2. 插入节点：将新节点插入到 head 之后（index 1）
3. 转移数据：将 head 内的内容拷贝到新节点中
4. 添加数据：将新的数据写入到 head 对应的节点中
5. 重置 head：将新节点作为新的 head，这样一来原有的 head 就成为了尾部节点。

与单链表不同，环链表中的移除的主要思路是从内容上替代节点。整体的逻辑可以描述为：

• 使用第二个节点代替头节点被移除
• 使用头节点模拟第二个节点
• 改变头节点的指向到第三个节点

算法步骤：

1. 转移数据：将第二个节点的内容拷贝到 head 节点中。此处不需要考虑数据覆盖的问题，因为 head 节点需要被移除。
2. 指向下个节点：将 head 的 next 指向从第二个节点改变为第三个节点。

边界条件：

• 当链表的长度为 1 时：
  • head 需要设置为 null
  • head.next 需要指向其自身

算法步骤：

1. 定位新的尾部节点：遍历到倒数第二个节点
2. 更新链接：将倒数第二个节点的 next 指向 head

算法步骤：

1. 遍历到需要被移除节点的前一个节点
2. 将该节点的 next 指向被移除节点的 next

• Linear：
  • 有限
  • 每个对象只有一个前置对象
  • 每个对象只有一个后置对象
• ADT：
  • 包含了有限数量的数据结构
  • 被存储的对象之间存在联系
  • 运算（行为）定义了 ADT

Stack（栈） 是 ADT 一种，通常使用 Array 或者 SLL 实现。名如其意， Stack 就是一种看上去是堆起来的数据结构（比如薯片筒就是一种 stack）。因此，Stack 通常都包含了两种基本操作：

• Push：将对象添加到 Stack 中的操作（把薯片放进桶里）
• Pop：将对象从 Stack 中移除的操作（把薯片拿出来）

值得注意的是，根据 Stack 的概念，无论是添加还是移除，我们处理的对象都只能是栈顶的对象（最上面的薯片），这导致了一下的几个事实：

• Stack 是一个 LIFO （Last In First Out ，后进先出的数据结构）（最先放进去的薯片肯定在最底下）
• Stack 中不存在 random access & remove。唯一能够操作的就是栈顶的，最后 push 进去的对象。（只能拿到最上面的薯片）
• Stack 无法支持搜索

• void push(x)：添加对象
• T pop()：移除栈顶元素并返回
• T peek or T top：返回栈顶元素（只读）
• boolean isEmpty()：通过 size，或是 top 是否为 null 来判断栈是否为空。
• clear()：设置 top 为 null 并清空栈。

• undo 功能
• 手机 app 的多开

链表是实现 Stack 最高效的手段，所有的操作复杂度都是 $O(1)$。一些实现细节：

• 链表的 head 用于模拟 Stack 的 top
• 空栈的情况下，head 为 null
• 不需要 tail

使用链表实现时，head 总是代表 top。因此每 push 一个对象，head 指向的节点就会更新到最新推送的对象。 算法步骤：

1. 建立新（对象）节点
2. 将新节点的 next 指向原来的 head 所代表的节点
3. 更新 head ，将其指向新的节点

算法步骤：

1. 将 head 指向下一个节点即可。

边界条件：

• 当 Stack 大小为 1 时，移除元素需要将 head 设置为 null

实现细节：

• 是否为空通过检查 size 是否为 0 来确认。
• 从效率的角度出发，不实现物理上的栈顶：
  • 将最右边的元素视作栈顶（size - 1），避免了每次 push / pop 都要做 $o(n)$ 的移动操作
• clear 的方式：
  • （不推荐）将 size 归零
  • （不推荐）手动将所有数组元素以新数据覆盖（比如 0）, $O(n)$ 复杂度
  • 使用该数组名指向新的数组，利用 java 的GC 功能清除数据 ,$O(1)$ 复杂度

Queues（队列） 的结构类似于一个两边都开口的薯片桶；一边是入口，另一边是出口。Queues 遵循 FIFO (First in First Out 先进先出) 原则。与 Stack 类似，Queues 不支持任何的随机访问和操作。

• void enqueue(x)：添加 x 到队列的最后
• x dequeue()：从队列中移除最先进入的元素
• x peak() & x top()：返回队列的最新 dequeue 的元素
• boolean isEmpty()：检查 size 是否为 0 或者 front 是否为 Null
• void clear()：将 front 设置为 null

• 由于 Queues 出入口不同，因此需要同时维护 head 和 tail 两个指针
• 鉴于链表在尾部的 remove 操作总是 $O(n)$ 复杂度，处于效率考虑，Queues 的添加入口在尾部，而删除出口在头部（addToBack & removeFromFront）。这样能保证添加删除的操作的复杂度都是 $O(1)$

算法步骤：

1. 同链表的 addToBack()

算法步骤：

1. 同链表的 removeFromFront()

与链表数列相似，Queue 的数组实现主要依靠的是一前以后的两个指针 front & back 来体现出“队列”的概念。Queue 可以被视作存储于数组中的，以 Back 开头，以 Front 结尾的队列。需要注意的是，对效率的考虑给数组数列的组成方式带来了很大的影响：

由于 Array 的 AddToFront() 操作必须要求 Shifting 移位，因此数组队列的 enqueue 是在数组中对象序列的后方，而 dequeue 是在对象序列的前方。那么通常 back 会被视作是队列的入口，而 front 会被视作是队列的出口。

我们之前的设想是将队列视作存储在数组中的，有头有尾的一个对象序列。这意味着其占用数组的位置只与数组的 capcity 有关系，而与数组的 Index 没有关系。因此，我们很可能会遭遇如下的存储分布：



无论是哪种，我们都没有办法用 ArrayList 来实现。因为 ArrayList 要求首元素不能为空，且必须连续存储。因此，数组队列只能使用 Array 来实现。

再观察一下第二种情况。以图为例，这种例子出现的情况是：数列 [6,3,11] 存储在数组的最后三位。假设我们此时希望对该数列进行 enqueue 的操作；此时 capcity 为 7，数列长度为 3，即便添加一个元素也没有超过数组的容量。但由于存储的位置处于数组的末端，我们没有办法再往里插入新的元素了。

为了解决这个问题，数组数列的实现引入了循环（WrapAround）的机制。如果 enqueue 的位置超出了数组的上限，但数组本身还有空可以做 enqueue 的话，我们就将 enqueue 的位置（back 的位置）往数组前方的空闲位置插入。具体的计算方式为：
$$ \texttt{back = Index mod Capacity} $$ 以上图为例，我们原来希望插入的位置是 index = 7（当然没有 7），通过上述转换之后就是在 index = 0 处 enqueue 了。

Priority queues 是另外一种线性的 ADT。其特点是，当前移除的对象是优先级最高的对象 。这种 ADT 通常用于搜寻最大最小值。 由于有大小的存在，Priority queues 中的对象必须是 Comparable 的。

Priority queues 会分为两个区：一个 Priority 区和一个备选区。Priority 区中存放优先级最高的数据用于操作。当 Priority 区中的数据移除后，备选区需要通过另一轮筛选选出下一个优先级最高的数据推送到 Priority 区中，以便接下来的操作。

可以注意到，每处理一轮 Priority 区中的数据，备选区中的数据就需要排序一次，为了更好的效率，具体实现是基于 heap 的。

Deques，指 Double-ended queue。Deque 允许在队列的两端添加和删除元素。Deque 不支持随机访问（添加删除）以及搜寻操作。

• void addFirst(x)：在 Deque 队首添加元素
• void addLast(x)：在 Deque 队尾添加元素
• x removeFirst()：在 Deque 队首删除元素
• x removeLast()：在 Deque 队尾删除元素
• boolean isEmpty()
• int size()

Deque 的数组实现同样需要使用到循环的方式。

• addLast() 通过 back % capacity 维护插入位置
• removeFirst() 通过 front % capacity 维护删除位置

这两个方法也需要通过循环的方式进行位置的维护。但由于其进出方向与之前的两个方法完全相反，如果使用同样的 back & front 指针，那么指针移动的操作是减而不是加。这意味着指针指向的 Index 很可能会变为负数，也就是会出现向前循环的情况。这种情况下，我们需要进行手动判断并做出以下处理：

//this applied to back as well
if (front < 0) {
    front  = capacity - front;
}

通常情况下，末除是一个分类的过程。所有余数相同的数字都会被放入到一个类中。在这个类中，最小的，非负的成员会成为余数。这导致了负数做末除时存在着不同。比如 $9 % 5 = 4$；但进行 $-9 % 5$ 时，因为要保证余数非负，取余的方向实际上需要更往负数方向上进行。比如这里，如果之间按正数的取余方式 $-9$ 去除 $(-1)\times5$ 还有 $-4$，但由于需要余数为正，因此需要再去除一个 $(-1)\times5$。因此余数是 $1$。

但在 Java 中，余数的结果并不要求为正，而是最接近 0 的数。这种情况是我们之前讨论的第一种情况：9 % -5 = -4。

Deque 的实现需要使用双链表（DLL）：

• add first & remove first 均在 head 处操作
• add fisrt & remove last 均在 tail 处操作

由于使用双链表，所有的操作都是 ($O(1)$)