blob: d27629f53042cb94a73de520da07849b25c0640a (
plain)
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
|
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
import java.util.Iterator;
public class Deque<Item> implements Iterable<Item>
{
private Node head;
private Node tail;
private int n;
private class Node
{
private Item item;
private Node next;
private Node prev;
}
// construct an empty deque
public Deque()
{
head = null;
tail = null;
n = 0;
}
// is the deque empty?
public boolean isEmpty() { return n == 0; }
// return the number of items on the deque
public int size() { return n; }
// insert the item at the front
public void addFirst(Item item)
{
if (item == null) throw new java.lang.NullPointerException();
Node node = new Node();
node.item = item;
node.next = head;
node.prev = null;
if (head == null)
tail = node;
else
head.prev = node;
head = node;
n++;
}
// insert the item at the end
public void addLast(Item item)
{
if (item == null) throw new java.lang.NullPointerException();
Node node = new Node();
node.item = item;
node.next = null;
node.prev = tail;
if (tail == null)
head = node;
else
tail.next = node;
tail = node;
n++;
}
// delete and return the item at the front
public Item removeFirst()
{
if (head == null) throw new java.util.NoSuchElementException();
Item item = head.item;
if (head == tail) // head.next == null
{
head = null;
tail = null;
}
else
{
Node prevHead = head;
head = head.next;
head.prev = null;
prevHead.next = null;
}
n--;
return item;
}
// delete and return the item at the end
public Item removeLast()
{
if (tail == null) throw new java.util.NoSuchElementException();
Item item = tail.item;
if (head == tail) // tail.prev == null
{
head = null;
tail = null;
}
else
{
Node prevTail = tail;
tail = tail.prev;
tail.next = null;
prevTail.prev = null;
}
n--;
return item;
}
// return an iterator over items in order from front to end
public Iterator<Item> iterator() { return new DequeIterator(); }
private class DequeIterator implements Iterator<Item>
{
private Node current = head;
public boolean hasNext()
{ return current != null; }
public void remove()
{ throw new java.lang.UnsupportedOperationException(); }
public Item next()
{
if (current == null) throw new java.util.NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}
|
