基本的数据结构及其实现
本节的主要问题是:如何用java来实现基础数据结构:背包
,队列
,栈
?
定容栈
首先从一个只能存储String的简单的定容栈
的设计开始: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
41public class FixedCapacityStackOfStrings {
private String[] a;
private int N;
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];
}
//测试
// 输入:to be or not to - be - - that - - - is
public static void main(String[] args) {
FixedCapacityStackOfStrings s = new FixedCapacityStackOfStrings(100);
while(!StdIn.isEmpty()) {
String item = StdIn.readString();
if(!item.equals("-")) s.push(item);
else if(!s.isEmpty()) StdOut.print(s.pop() + " ");
}
StdOut.println(" ---- " + s.size() + "left on stack");
}
}
- 合情合理的使用了数组,push就是N+1,pop就是–N
在测试中直接new了一个100的数组,很明显是欠妥的,如果压栈数超过100不够用,不到100又会太过浪费,所以开始进化为“可变容量的栈”
定容栈 -> 可变容栈
基本思路:在push时,如果超过Max则扩充;如果不到则缩减Max
但是java的数组并不支持直接的扩充和缩减,所以这里需要在节点时刻创建新的数组,这里创建一个新方法,然后对push和pop方法进行更改:
1 |
|
这样就实现了栈的大小总处在最合适的大小,完成了从定容
到变容
自适应的进化
String栈 -> T栈
已经得到了一个自适应的String栈,但利用java的范型就能将其变为万能栈,只需要将String变为
1 | // 范型化 |
这样就完成了T栈
的进化
=====================================
补充一个栈
的具体使用:如计算(2 * (2 + 4) - (2 + 1) / 2)这样的计算,是如何按顺序得到想要的结果的?
其实,早在60年代的计算机发展之初就有前辈利用2个栈简单的解决了这个问题:一个栈用来存运算符号,一个栈用来放数值,根据)
来区隔,没遇到一个)
,运算符栈弹出运算符,数值栈弹出数值计算得到结果,再将结果入栈,如此就完成了包含括号优先级的计算
链表
链表
: 一种由node
链接的数据结构,每个node
含有一个范型的元素,和一个可指向另一节点的引用
回忆在上面处理可变容栈
时,由于使用的数组容量不能随意变更,为此我们专门设计了一个resize()
方法,而链表能够随意增删节点的特性就是专门解决这样的问题
1 | private class Node { |
对于链表的学习,最好的方式就是可视化表达,留意一些特殊节点并熟练以下操作:表头节点,表尾节点,插入节点,删除节点,遍历量表,再引申到双向链表,环行链表等等,这些是我们实现各种高级算法的基础,会逐渐都接触到
链表实现栈(Stack)
先让我们把上次设计的栈
改为使用链表
而不是数组
来实现
1 | publci class StackDemo { |
使用链表能保证栈的大小根链表分配的大小一致,不存在浪费和不够的问题
只使用first节点就足够了,栈只有一个IO口,对于链表来说操作first节点是最容易的
链表实现队列(Quene)
然后链表来实现队列(Queue)
,是再合适不过了,入列就是添加last节点,出列就是first节点删除,size,isEmpty等等根栈中的一致,就不再写了
1 | public class QueueDemo { |
- 队列的实现需要first和last两个节点
- 注意队列只有一个元素时,
first = last
- 注意队列为空就是
last = null
链表实现背包(Bag)
背包其实最简单的集合,它只支持添加和查找,不支持删除
其实现也很简单基本跟栈
相同,只用一个first节点就足够了,所以重点不在它的add上,而在于对其中元素的查找
在java中,使用的就是迭代(Iterator)
,允许你使用foreach()
语句来遍历集合,那迭代到底是如何实现的呢
?
首先需要实现Iterator
接口:引入import java.util.Iterator
并implement Iterator<Item>
实现其所有方法
具体代码如:
1 | public class BagDemo |