在第二周的学习当中,主要学习了Stack和Queue这两种基本数据结构和其算法实现。
本周的作业也是以上面两种学习到的数据结构为基础,设计一个双端队列(Deques)和一个随机队列(Randomized Queues)。

题目原文点击这里

Deques

双端队列的设计要求是,支持在数据结构的前端与后端进行元素的删除、添加操作。对应的给出了应该实现的API:

1
2
3
4
5
6
7
8
9
10
11
public class Deque<Item> implements Iterable<Item> {
public Deque() // construct an empty deque
public boolean isEmpty() // is the deque empty?
public int size() // return the number of items on the deque
public void addFirst(Item item) // add the item to the front
public void addLast(Item item) // add the item to the end
public Item removeFirst() // remove and return the item from the front
public Item removeLast() // remove and return the item from the end
public Iterator<Item> iterator() // return an iterator over items in order from front to end
public static void main(String[] args) // unit testing (optional)
}

同时要求在满足时间复杂度与空间复杂度的同时,对应的对客户端的错误操作做出处理(抛出对应的异常即可)。

  • Throw a java.lang.IllegalArgumentException if the client calls either addFirst() or addLast() with a null argument.
  • Throw a java.util.NoSuchElementException if the client calls either removeFirst() or removeLast when the deque is empty.
  • Throw a java.util.NoSuchElementException if the client calls the next() method in the iterator when there are no more items to return.
  • Throw a java.lang.UnsupportedOperationException if the client calls the remove() method in the iterator.

下面我给出我实现的代码,其中还有很大的优化空间,仅仅作于实现思路的参考:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
package net.sunzhenyu.miscellaneous.dsa.other.deques_randomized_queues;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Deques<T> implements Deque<T> {

private Node f, l;
private int size;

public Deques() {
this.f = null;
this.l = null;
this.size = 0;
}

@Override
public boolean isEmpty() {
return size == 0;
}

@Override
public int size() {
return size;
}

@Override
public void addFirst(T element) {
nullPointerCheck(element);
Node oldF = f;
f = new Node();
f.item = element;
if (isEmpty()) {
l = f;
f.next = null;
} else {
oldF.previous = f;
f.next = oldF;
}
size++;
}

@Override
public void addLast(T element) {
nullPointerCheck(element);
Node oldL = l;
l = new Node();
l.item = element;
if (isEmpty()) {
f = l;
f.previous = null;
} else {
oldL.next = l;
l.previous = oldL;
}
size++;
}

@Override
@SuppressWarnings("all")
public T removeFirst() {
emptyRemoveCheck();
T element = f.item;
if (size == 1) {
f = null;
l = null;
} else {
f = f.next;
}
size--;
return element;
}

@Override
@SuppressWarnings("all")
public T removeLast() {
emptyRemoveCheck();
T element = l.item;
if (size == 1) {
f = null;
l = null;
} else {
l = l.previous;
}
size--;
return element;
}

private void nullPointerCheck(T element) {
if (element == null) {
throw new IllegalArgumentException("The argument cannot be null.");
}
}

private void emptyRemoveCheck() {
if (f == null && l == null && size == 0) {
throw new NoSuchElementException("The deque is empty.");
}
}

@Override
public Iterator<T> iterator() {
return new DequesIterator<>();
}

class DequesIterator<E> implements Iterator<E> {

private Node node = f;
private int index = 0;

@Override
public boolean hasNext() {
return index < size;
}

@Override
@SuppressWarnings("unchecked")
public E next() {
if (!hasNext()) {
throw new NoSuchElementException("No more items has return.");
}
E element = (E) node.item;
node = node.next;
index++;
return element;
}

@Override
public void remove() {
throw new UnsupportedOperationException(
"The deque unsupported remove operation in iterator.");
}
}

class Node {

T item;
Node previous;
Node next;
}
}

Randomized Queues

这个题目初看会觉得很困惑,什么才是随机队列,其实看了题目简介之后很简单:
A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure.
要求实现一个队列,不过在此队列中,出队操作并不是像通常出队队首的元素,而是需要随机选出队列中的一个元素让其出队。
这里我的实现思路是:既然要求的是随机出队队列中的一个元素,但又要保证这个数据结构是一个队列,严格遵守FIFO的规则,我随机从队列中选取的元素将会和当前队首的元素进行swap(交换),然后让其出队。
下面是给出的API,我们要将其实现:

1
2
3
4
5
6
7
8
9
10
public class RandomizedQueue<Item> implements Iterable<Item> {
public RandomizedQueue() // construct an empty randomized queue
public boolean isEmpty() // is the randomized queue empty?
public int size() // return the number of items on the randomized queue
public void enqueue(Item item) // add the item
public Item dequeue() // remove and return a random item
public Item sample() // return a random item (but do not remove it)
public Iterator<Item> iterator() // return an independent iterator over items in random order
public static void main(String[] args) // unit testing (optional)
}

下面是我的实现代码,同样,仅仅用于参考:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package net.sunzhenyu.miscellaneous.dsa.other.deques_randomized_queues;

import edu.princeton.cs.algs4.StdRandom;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class RandomizedQueue<T> implements Queue<T> {

private Object[] elements;
private int size;
private final int DEFAULT_CAPACITY = 10;

public RandomizedQueue() {
elements = new Object[DEFAULT_CAPACITY];
size = 0;
}

public RandomizedQueue(int initialCapacity) {
if (initialCapacity <= 0) {
throw new IllegalArgumentException("The initial capacity cannot be equal zero.");
}
elements = new Object[initialCapacity];
this.size = 0;
}

@Override
public boolean isEmpty() {
return size <= 0;
}

@Override
public int size() {
return size;
}

@Override
public void enqueue(T element) {
nullPointerCheck(element);
ensureCapacity(elements.length << 1);
elements[size++] = element;
}

@Override
@SuppressWarnings("unchecked")
public T dequeue() {
noSuchElementCheck();
if (size == (elements.length >> 4)) {
expandOrShrink(this.elements.length >> 1);
}
int index = StdRandom.uniform(size);
T element = (T) elements[index];
elements[index] = elements[size - 1];
elements[--size] = null;
return element;
}

@Override
@SuppressWarnings("unchecked")
public T sample() {
noSuchElementCheck();
int index = StdRandom.uniform(size);
return (T) elements[index];
}

private void ensureCapacity(int newCapacity) {
if (newCapacity <= 0) {
throw new IllegalArgumentException("The new capacity cannot smaller than zero.");
}
if (size >= elements.length) {
expandOrShrink(newCapacity);
}
}

@SuppressWarnings("all")
private void expandOrShrink(int newCapacity) {
Object[] newElementsArray = new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElementsArray[i] = elements[i];
}
elements = newElementsArray;
}

private void nullPointerCheck(T element) {
if (element == null) {
throw new IllegalArgumentException("The argument cannot be null.");
}
}

private void noSuchElementCheck() {
if (size == 0) {
throw new NoSuchElementException("The queue is empty.");
}
}

@Override
public Iterator iterator() {
return new RandomizedIterator();
}

class RandomizedIterator<E> implements Iterator<E> {

private int[] randomSeq = StdRandom.permutation(size());
private int size = randomSeq.length;

@Override
public boolean hasNext() {
return size > 0;
}

@Override
@SuppressWarnings("unchecked")
public E next() {
if (!hasNext()) {
throw new NoSuchElementException("No item returned.");
}
return (E) elements[randomSeq[--size]];
}

@Override
public void remove() {
throw new UnsupportedOperationException(
"The randomized queue doesn't support this operation.");
}
}
}