《算法(第4版)》背包、队列和栈读书笔记

第1章 1.3背包、队列和栈。
页数74~107

背包(Bag)、队列(Queue)和栈(Stack)都是一组对象的集合,不同之处在于删除或者访问对象的顺序不同。

背包是一种不支持删除元素的集合数据类型。
队列是一种基于先进先出(FIFO)策略的集合类型。
栈是一种基于后进先出(LIFO)策略的集合类型。

定义API

背包

方法 说明
Bag() 构造方法,创建一个空背包
void add(Item item) 添加一个元素
boolean isEmpty() 背包是否为空
int size() 背包中的元素数量

队列

方法 说明
Queue() 构造方法,创建空队列
void enqueue(Item item) 添加一个元素(入队)
Item dequeue() 删除最早添加的元素(出队)
boolean isEmpty() 判断队列是否为空
int size() 队列中的元素数量

方法 说明
Stack() 创建一个空栈
void push(Item item) 添加一个元素
Item pop() 删除最近添加的元素
boolean isEmpty() 栈是否为空
int size() 栈的元素数量

装箱拆箱

自动将一个原始数据类型转换为一个封装类型被称为自动装箱,自动将一个封装类型转换为一个原始数据类型成为自动拆箱

1
2
3
Stack<Integer> stack = new Stack<Integer>();
stack.push(10);//自动装箱(int->Integer)
int i = stack.pop();//自动拆箱(Integer ->int)

栈的实现和优化

定容字符串栈的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FixedCapacityStackOfStrings{
private Stirng [] a;
private int N;//size
public FixedCapacityStackOfStrings(int cap){
a = new String[cap];
}
public boolean isEmpty(){
return N ==0
}
public int size(){
return N;
}
public void push(String item){
a[N++] = item;
}
public String pop(){
return a[--N];
}
}

边界值优化

书中说是调整数组大小,在我看来属于边界优化问题。

定义resize方法,实现在栈要溢出的时候进行扩容。
同时在push方法中检测数组是否太小需要扩容,但是容量过大会造成空间浪费,所以在pop时如果栈大小小于数组四分之一时就对原容量长度减半的操作,维持在状态半满左右。

动态大小栈实现

这是一个可以动态调整大小的栈的实现,并且这个实现中也实现了迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Iterator;
pulbbic class ResizingArrayStack<Item> implements Iterable<Item>{
private Item[] a = (Item[]) new Object[1];//栈元素
private int N = 0;
public boolean isEmpty(){
return N == 0;
};
public int size(){
return N;
}
public void resize(int max){
//将栈移动到一个大小为max的数组
Item[] temp = (Item[]) new Object[max];
for(int i=0;i<N;i++){
temp[i] = a[i];
}
a = temp;
}
public void push(Item item){
//将元素添加到栈顶
if(N == a.lenth) resize(2*a.lenth);
a[N++] = item;
}
public Item pop(){
//从栈顶删除元素
Item item = a[--N];
a[N] = null;//释放内存,书中说是防止对象游离
if(N>0 && N == a.lenth/4) resize(a.lenth);
return item;
}
public Iterator<Item> iterator(){
return new ReverseArrayIterator();
}

private class ReverseArrayIterator implements Iterator<Item>{
private int i = N;
public boolean hasNext(){
return i>0;
}
public Item next(){
return a[--i];
}
public void remove(){

}
}
}

链表

链表是一种递归的数据结构,可以为空或者是指向一个节点的引用,这个节点含有一个泛型元素和一个指向林一条链表的引用。

链表的数据结构:

1
2
3
4
private class Node{
Item item;
Node next;
}

在表头插入节点

假设头节点为first:

  1. 新实例化一个tempFirst,将first保存在里面
  2. 新实例化一个first
  3. 将item设置为插入的内容值,next指向tempFirst

从表头删除节点

假设头节点为first:

  1. 将first指向first.next

在表尾插入节点

简单三步操作:

  1. 保存指向尾节点的链接
  2. 创建新的尾节点
  3. 将尾链接指向新节点

链表的遍历

for循环为例:

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

}

用链表实现栈

思路:
用链表实现的栈最大好处是可以灵活利用空间。站的顶部就是表头,first指向栈顶。当调用push()压入一个元素是,实际上是在链表头部插入一个节点的操作。当调用pop()出栈一个元素时,实际上是从链表的表头删除一个节点的操作。要实现size()方法,可以用一个变量N记录,当进栈时加一,出栈时减一。而isEmpty()方法更简单,只需要判断first节点是否为空即可(或者检测N是不是0)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Iterator;

public class Stack<Item> implements Iterable<Item> {
private Node first;
private int N;

private class Node {
Item item;
Node next;
}

public boolean isEmpty() {
return first == null;
}

public int size() {
return N;
}

public void push(Item item) {
// 向栈顶添加元素
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}

public Item pop() {
// 从栈顶删除元素
Item item = first.item;
first = first.next;
N--;
return item;
}

@Override
public Iterator<Item> iterator() {
// 迭代器实现省略
return null;
}
}

用链表实现队列

思路:
基于链表实现的队列中,实例变量first指向队列开头,实例变量last指向队列结尾。
如果要将一个元素入列,进行enqueue()操作,实际上相当于在链表末端插入一个元素,要进行出队操作dequeue(),实际上是将链表的表头节点删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Iterator;

public class Queue<Item> implements Iterable<Item> {
private Node first;// 指向最早添加的节点
private Node last;// 指向最近添加的节点
private int N;

private class Node {
Item item;
Node next;
}

public boolean isEmpty() {
return first == null;
}

public int size() {
return N;
}

public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty())
first = last;
else
oldlast.next = last;
N++;
}

public Item dequeue() {
Item item = first.item;
first = first.next;
if (isEmpty())
last = null;
N--;
return item;
}

@Override
public Iterator<Item> iterator() {
// 省略迭代器的实现
return null;
}
}

用链表实现背包

因为背包是一种不支持删除元素的数据类型,所以实现上只需要将栈的实现中的push()方法改名为add(),然后删除pop()方法就可以了。

文章作者: Kevin Wu
文章链接: https://kevinwu.cn/p/cbe6c59b/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 KevinWu的博客
支付宝打赏