-
Notifications
You must be signed in to change notification settings - Fork 0
/
ArrayDeque.java
187 lines (168 loc) · 4.27 KB
/
ArrayDeque.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
/**
* Created by havinleung on 2017-06-27.
*/
public class ArrayDeque<Item> {
private Item[] list;
private int size;
private int first;
private int last;
public ArrayDeque() {
list = (Item[]) new Object[2];
size = 0;
first = 0;
last = 0;
}
/*
* Methods
* */
/**
* Adds an item to the front of the Deque.
**/
public void addFirst(Item y) {
checksize();
if (isEmpty()) {
//initialise
list[0] = y;
first = 0;
last = 0;
} else {
first = moveIndexLeft(first);
list[first] = y;
}
size++;
}
/**
* Adds an item to the back of the Deque.
**/
public void addLast(Item y) {
checksize();
if (isEmpty()) {
//initialise
list[0] = y;
first = 0;
last = 0;
} else {
last = moveIndexRight(last);
list[last] = y;
}
size++;
}
/**
* Returns true if deque is empty, false otherwise.
**/
public boolean isEmpty() {
return (size == 0);
}
/**
* Returns the number of items in the Deque.
**/
public int size() {
return size;
}
/**
* Prints the items in the Deque from first to last, separated by a space.
**/
public void printDeque() {
int index = first;
while (index != last) { //runs loop until index = last
System.out.print(list[index]);
System.out.print(" ");
index = moveIndexRight(index);
}
System.out.print(list[index]);
System.out.print(" ");
}
/**
* Removes and returns the item at the front of the Deque. If no such item exists, returns null.
**/
public Item removeFirst() {
if (isEmpty()) {
return null;
}
Item x = list[first];
list[first] = null;
first = moveIndexRight(first);
size--;
checksize();
return x;
}
/**
* Removes and returns the item at the back of the Deque. If no such item exists, returns null.
**/
public Item removeLast() {
if (isEmpty()) {
return null;
}
Item x = list[last];
list[last] = null;
last = moveIndexLeft(last);
size--;
checksize();
return x;
}
/**
* Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth.
* If no such item exists, returns null. Must not alter the deque!
**/
public Item get(int index) {
if (index < 0 || index >= size) {
return null;
}
index = first + index;
index = index % list.length;
return list[index];
}
/*
* Helper Methods
* */
//Doubles the size of the array.
private void upsize() {
Item[] x = (Item[]) new Object[list.length * 2];
int index = first;
int i = 0;
while (index != last) { //copies every item except last
x[i++] = list[index];
index = moveIndexRight(index);
}
x[i] = list[index]; //copies last item
first = 0;
last = size - 1;
list = x;
}
//Halves the size of the array.
private void downsize() {
Item[] x = (Item[]) new Object[list.length / 2];
int index = first;
int i = 0;
while (index != last) { //copies every item except last
x[i++] = list[index];
index = moveIndexRight(index);
}
x[i] = list[index]; //copies last item
first = 0;
last = size - 1;
list = x;
}
private void checksize() {
if (size != 0 && size < (list.length / 4)) {
//only using 25% or less of the array
downsize();
} else if (size == list.length) {
//array is maxed out
upsize();
}
}
private int moveIndexRight(int x) {
x++;
x = x % list.length;
return x;
}
private int moveIndexLeft(int x) {
x--;
x = x % list.length;
if (x < 0) {
x += list.length; //since it's not the modulus but the remainder...
}
return x;
}
}