-
Notifications
You must be signed in to change notification settings - Fork 3
/
Queue.java
203 lines (166 loc) · 4.96 KB
/
Queue.java
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
package DataStructure;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Queue<Item> implements Iterable<Item> {
private Node first;
private Node last;
private int size;
private class Node {
private Node next;
private Item item;
}
/**
* Provided a queue, that is, an ordered object.
* Through enqueing and dequeuing, this object
* provides a first-in first-out(FIFO) ordering.
*/
public Queue() {
first = null;
last = null;
size = 0;
}
/**
* Provided a queue, that is, an ordered object,
* initialized with the provided items.
* Through enqueing and dequeuing, this object
* provides a first-in first-out(FIFO) ordering.
*/
public Queue(Iterable<Item> items) {
size = 0;
first = null;
for (Item item : items) {
enqueue(item);
}
}
/**
* Provided a queue, that is, an ordered object,
* initialized with the items in the provided bag.
* Through enqueing and dequeuing, this object
* provides a first-in first-out(FIFO) ordering.
*/
public Queue(Queue queue) {
buildQueue(queue, false);
}
/**
* Since it will first add the items in the wrong direction,
* we must do it a second time to put the
* items in the correct order
*
* @param queue
* @param goodDirection
*/
private void buildQueue(Queue queue, boolean goodDirection) {
size = 0;
first = null;
Iterator<Item> iterator = queue.iterator();
while (iterator.hasNext()) {
Item next = iterator.next();
enqueue(next);
}
if (!goodDirection) buildQueue(this, true);
}
/**
* Enqueue an item to the queue.
*
* @param item, the item
*/
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;
size++;
}
/**
* Returns the first object enqueued that is left on
* this queue. Throws an exception if the queue is empty.
*
* @return the first enqueued element in this queue.
* @throws NoSuchElementException, if the queue is empty
*/
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Empty queue.");
Item i = first.item;
first = first.next;
size--;
if (isEmpty()) last = null;
return i;
}
/**
* Return the size of the queue.
*/
public int size() {
return size;
}
/**
* Returns the the first object enqueued that is left on
* this queue, but doesn't remove it.
*
* @return the last queued element in this queue
* @throws NoSuchElementException, if the queue is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Empty queue.");
return first.item;
}
/**
* Returns {@code true} if the queue is empty, otherwise, return {@code false}.
*/
public boolean isEmpty() {
return size == 0;
}
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
for (Node node = first; node.next != null; node = node.next) {
stringBuilder.append(node.item.toString()).append(" ");
}
return stringBuilder.toString();
}
/**
* Returns an iterator over the items contained in this queue.
* The items are iterated over in the order they have been enqueue,
* that is, first-in first-out order.
*/
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
Node current = first;
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException("Iterator has traversed all items");
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
Queue<Integer> q = new Queue<Integer>();
for (int i = 0; i < 10; i++) {
q.enqueue(i);
}
Iterator<Integer> it = q.iterator();
for (int i = 0; i < 10; i++) {
int l = q.dequeue();
if (l != i) throw new Error("Difference between elements.");
}
while (it.hasNext()) {
Integer i = it.next();
System.out.print(i + " ");
}
try {
q.dequeue();
} catch (NoSuchElementException e) {
System.out.println("Passed exception tests.");
}
q.enqueue(1);
if (q.peek() != 1) throw new Error("Peek is incorrect");
}
}