堆栈和队列都可以通过链表和数组分别来实现。

在堆栈和队列的实现过程中,使用到了泛型和接口的技术。

堆栈

堆栈是一种先进后出的存储结构(FILO)。

在用数组实现堆栈的时候需要在一定情况下调整数组大小。

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
public class ArrayStack<Item> {
private Item[] s;
private int N = 0;
public ArrayStack() {
s = new Item[1];
}
public void push(Item item) {
if (N == s.length) resize(2 * s.length);
s[N++] = item;
}
// 避免反复调整数组大小,选择1/4
public Item pop() {
if (N == 1/4 * s.length) resize(s.length/2);
Item item = s[--N];
s[N] = null;
return item;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
private resize(int capacity) {
Item[] copy = new Item[capacity];
for (int i = 0; i < N; i++)
copy[i] = s[i];
s = copy;
}
}

链表的实现方式比较简单。

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
public class LinkedStack<Item> {
private Node first = null;
private int N = 0;
private class Node {
Item item;
Node next;
}
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;
return item;
N--;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
}

队列

队列是一种先进先出的存储结构(FIFO)。

数组实现

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
public class ArrayQueue<Item> {
private Item[] q;
private int tail = head = N = 0;
public ArrayQueue() {
q = new Item[1];
}
public enqueue(Item item) {
if (N == q.length) resize(2 * q.length);
if (tail == q.length) tail = 0;
q[tail++] = item;
N++;
}
public Item dequeue() {
Item item = q[head];
q[head++] = null;
N--;
if (head == q.length) head = 0;
if (N == s.length/4) resize(s.lenght/2);
return item;
}
private resize(int capacity) {
Item copy = new Item[capacity];
for (int i = 0; i < N; i++)
copy[i] = q[(i + head)%s.length];
s = copy;
head = 0;
tail = N;
}
public int size() {
return N;
}
public boolean isEmpty() {
return 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
public class LinkedQueue<Item> {
private Node first, last;
private int N;
private class Node {
Item item;
Node next;
}
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;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
}

课程作业——双端队列和随机队列

shuffle算法(Fisher-Yates shuffle and Knuth shuffle)

水塘抽样算法(Reservoir sampling)

算法实现

未完待续