背包,队列和栈

它们都是一些数据对象的集合

1. 特点

1.1 背包

  • 不支持 删除元素
  • 使用其来收集元素,遍历和递归它们
  • 元素的顺序是不确定的

1.2 队列(先进先出)

这里所说的队列指的是先进先出的队列。

  • 数据元素相对此集合的顺序是先进先出
  • 队列能收集数据,同时保持它们的相对顺序

1.3 栈

  • 正好与队列相反,数据元素在栈中是后进先出的。
  • 栈也会保持数据元素的相对顺序

1.4 例子:算数表达式的表示法

使用两个栈来表达算数表达式

当接收到一个算数表达式的时候:

  1. 将数值压入数值栈
  2. 将操作符压入操作符栈
  3. 忽略左括号
  4. 当遇到右括号的时候,弹出一个操作符,和所需要的数值,并且将计算结果压入数值栈

2. 实现

2.1 使用数组实现栈

  • push() 方法需要检查当前栈是否是满的,如果满,则进行扩容
  • resize() 方法会将当前数组的空间加倍(或减半)
  • pop() 方法需要检查当前栈的大小是否小于数组的 1/4,如果成立,则将数组的空间减少为它的一半。
  • 需要防止对象游离,当数据对象被弹出后,将其声明为 null
  • 缺点
    • 时间复杂度与数组的大小相关
    • 所需要的空间是不可预知的

如果当前栈的大小小于数组的 1/4,那么即使 pop() 方法使其减少了,它仍然比当前栈的大小还要大一倍,所以我们依旧有空间储存数据,为了防止空间的浪费,将数组的空间减少。

当一个数据对象被弹出栈后,它就再也不会被栈使用了,但是数据的引用依旧存在,所以 Java 不会将这块内存回收。这种情况就被叫做对象游离

2.2 链表

链表是一个递归的数据结果,它可以是空,或者是一个指向一个节点的引用;
这个节点储存一个数据元素和一个指向下一个节点或列表的引用;
Node(节点)类经常被用于内部类。

2.2.1 创建

1
2
3
4
5
private class Node
{
Item item;
Node next;
}
  • 只要声明一个 Node 变量,我们就能表示一个链表
    因为 Node 被用作内部类,所以我们能直接地声明其成员。
1
2
3
4
5
6
7
8
9
10
11
12
Node first = new Node();
Node second = new Node();
Node thrid = new Node();

//Items
first.item = "to";
second.item = "be";
thrid.item = "or";

//Nexts
first.next = second;
second.next = thrid;

Build linked List

2.2.2 在头部插入

使用另一个引用(例如 oldfirst) 来储存头结点,然后建立新节点来储存数据,然后将 next 指向头结点

Insert at beginning

2.2.3 从头部删除

将头指针first直接指向 first.next 即可
Java 的 garbage collector 会将内存回收。

Remove from the beginning

2.2.4 在尾部插入

就像在头部插入一样,用一个另外的引用 oldlast 来保存尾部节点,然后建立一个新的节点来储存数据,然后将 oldlast.next 声明为 last

注意,对于单链表,尾部节点的引用可能要通过从头结点的层层遍历才能取到,这也是为什么一般仅使用头节点来作为主要的操作节点。

Insert at the end

2.2.5 在其他地方插入和删除

进行这个操作,我们必须要拿到所需要插入位置的前一个节点的信息来辅助我们的插入删除操作,因此我们需要遍历 链表来取得指定插入位置的前一个位置。

2.2.6 遍历

一般来说,我们使用 foreach 语句来进行遍历操作。

使用这个语句的类必须要实现 IterableIterator 接口来返回一个迭代器和定义迭代方法。

但是对于链表这种简单结构来说,我们只需要使用一般的 for 语句即可。

1
2
3
for(Node x = first; x != null; x = x.next) {
//handle x.item
}

3. 链表的使用

使用链表可以:

  • 处理任何数据
  • 需求的空间仅仅和集合的大小成正比
  • 时间复杂度和集合的大小无关

链表的插入和删除操作仅仅是变量的赋值,以及对象的构建,它们的时间复杂度都是常数级别

3.1 实现栈

将链表的头部设定为栈顶

  • 当压入数据的时候,我们在头部插入数据元素
  • 当弹出数据的时候,我们在头部删除数据元素

选择链表头部而不是尾部进行操作的原因:链表的插入和删除操作都是在一端进行的;

链表的尾部元素一般不好获取,特别是对于单链表而言,如果采用尾部作为栈顶,那么当删除栈顶元素之后,我们无法很快的获取新的栈顶元素的引用(因为要从头部进行遍历,或者维护两个指针,这都是不必要的);

而采用头部作为栈的顶部,仅仅需要一句声明语句 newTop = top.next; 即可获取到新的栈顶元素。

3.2 实现队列

  • 设定链表的头部为队列的头部,链表的尾部为队列的尾部。
  • 当插入元素时,在尾部插入数据。
  • 当删除元素时,在头部删除数据。

由于队列插入和删除的位置不同,在尾部删除元素很麻烦,但是相应的插入操作却变得十分简单,仅需要改变其 next 域即可,而不是类似删除操作还要返回前一个数据的引用。

3.3 背包的实现

将栈或队列的 pop() 操作去掉,就是一个背包结构。

0%