|
| 1 | +packageDataStructures.Queues; |
| 2 | + |
| 3 | +/** |
| 4 | + * A [deque](https://en.wikipedia.org/wiki/Double-ended_queue) is short for a double ended queue |
| 5 | + * pronounced "deck" and sometimes referred to as a head-tail linked list. A deque is a data |
| 6 | + * structure based on a doubly linked list, but only supports adding and removal of nodes from the |
| 7 | + * beginning and the end of the list. |
| 8 | + * |
| 9 | + * @author [Ian Cowan](https://github.com/iccowan) |
| 10 | + */ |
| 11 | +publicclassDeques<T> { |
| 12 | +/** Node for the deque */ |
| 13 | +classDequeNode<S> { |
| 14 | +/** Value of the node */ |
| 15 | +Sval; |
| 16 | + |
| 17 | +/** Next node in the deque from this node */ |
| 18 | +DequeNode<S>next =null; |
| 19 | + |
| 20 | +/** Previous node in the deque from this node */ |
| 21 | +DequeNode<S>prev =null; |
| 22 | + |
| 23 | +/** Constructor */ |
| 24 | +DequeNode(Sval) { |
| 25 | +this.val =val; |
| 26 | + } |
| 27 | + } |
| 28 | + |
| 29 | +/** Head of the deque */ |
| 30 | +DequeNode<T>head =null; |
| 31 | + |
| 32 | +/** Tail of the deque */ |
| 33 | +DequeNode<T>tail =null; |
| 34 | + |
| 35 | +/** Size of the deque */ |
| 36 | +intsize =0; |
| 37 | + |
| 38 | +/** |
| 39 | + * Adds the specified value to the head of the deque |
| 40 | + * |
| 41 | + * @param val Value to add to the deque |
| 42 | + */ |
| 43 | +publicvoidaddFirst(Tval) { |
| 44 | +// Create a new node with the given value |
| 45 | +DequeNode<T>newNode =newDequeNode<T>(val); |
| 46 | + |
| 47 | +// Add the node |
| 48 | +if (head ==null) { |
| 49 | +// If the deque is empty, add the node as the head and tail |
| 50 | +head =newNode; |
| 51 | +tail =newNode; |
| 52 | + }else { |
| 53 | +// If the deque is not empty, insert the node as the new head |
| 54 | +newNode.next =head; |
| 55 | +head.prev =newNode; |
| 56 | +head =newNode; |
| 57 | + } |
| 58 | + |
| 59 | +size++; |
| 60 | + } |
| 61 | + |
| 62 | +/** |
| 63 | + * Adds the specified value to the tail of the deque |
| 64 | + * |
| 65 | + * @param val Value to add to the deque |
| 66 | + */ |
| 67 | +publicvoidaddLast(Tval) { |
| 68 | +// Create a new node with the given value |
| 69 | +DequeNode<T>newNode =newDequeNode<T>(val); |
| 70 | + |
| 71 | +// Add the node |
| 72 | +if (tail ==null) { |
| 73 | +// If the deque is empty, add the node as the head and tail |
| 74 | +head =newNode; |
| 75 | +tail =newNode; |
| 76 | + }else { |
| 77 | +// If the deque is not empty, insert the node as the new tail |
| 78 | +newNode.prev =tail; |
| 79 | +tail.next =newNode; |
| 80 | +tail =newNode; |
| 81 | + } |
| 82 | + |
| 83 | +size++; |
| 84 | + } |
| 85 | + |
| 86 | +/** |
| 87 | + * Removes and returns the first (head) value in the deque |
| 88 | + * |
| 89 | + * @return the value of the head of the deque |
| 90 | + */ |
| 91 | +publicTpollFirst() { |
| 92 | +// If the head is null, return null |
| 93 | +if (head ==null)returnnull; |
| 94 | + |
| 95 | +// First, let's get the value of the old head |
| 96 | +ToldHeadVal =head.val; |
| 97 | + |
| 98 | +// Now, let's remove the head |
| 99 | +if (head ==tail) { |
| 100 | +// If there is only one node, remove it |
| 101 | +head =null; |
| 102 | +tail =null; |
| 103 | + }else { |
| 104 | +// If there is more than one node, fix the references |
| 105 | +head.next.prev =null; |
| 106 | +DequeNode<T>oldHead =head; |
| 107 | +head =head.next; |
| 108 | + |
| 109 | +// Can be considered unnecessary... |
| 110 | +// Unlinking the old head to make sure there are no random |
| 111 | +// references possibly affecting garbage collection |
| 112 | +oldHead.next =null; |
| 113 | + } |
| 114 | + |
| 115 | +size--; |
| 116 | +returnoldHeadVal; |
| 117 | + } |
| 118 | + |
| 119 | +/** |
| 120 | + * Removes and returns the last (tail) value in the deque |
| 121 | + * |
| 122 | + * @return the value of the tail of the deque |
| 123 | + */ |
| 124 | +publicTpollLast() { |
| 125 | +// If the tail is null, return null |
| 126 | +if (tail ==null)returnnull; |
| 127 | + |
| 128 | +// Let's get the value of the old tail |
| 129 | +ToldTailVal =tail.val; |
| 130 | + |
| 131 | +// Now, remove the tail |
| 132 | +if (head ==tail) { |
| 133 | +// If there is only one node, remove it |
| 134 | +head =null; |
| 135 | +tail =null; |
| 136 | + }else { |
| 137 | +// If there is more than one node, fix the references |
| 138 | +tail.prev.next =null; |
| 139 | +DequeNode<T>oldTail =tail; |
| 140 | +tail =tail.prev; |
| 141 | + |
| 142 | +// Similarly to above, can be considered unnecessary |
| 143 | +// See `pollFirst()` for explanation |
| 144 | +oldTail.prev =null; |
| 145 | + } |
| 146 | + |
| 147 | +size--; |
| 148 | +returnoldTailVal; |
| 149 | + } |
| 150 | + |
| 151 | +/** |
| 152 | + * Returns the first (head) value of the deque WITHOUT removing |
| 153 | + * |
| 154 | + * @return the value of the head of the deque |
| 155 | + */ |
| 156 | +publicTpeekFirst() { |
| 157 | +returnhead.val; |
| 158 | + } |
| 159 | + |
| 160 | +/** |
| 161 | + * Returns the last (tail) value of the deque WITHOUT removing |
| 162 | + * |
| 163 | + * @return the value of the tail of the deque |
| 164 | + */ |
| 165 | +publicTpeekLast() { |
| 166 | +returntail.val; |
| 167 | + } |
| 168 | + |
| 169 | +/** |
| 170 | + * Returns the size of the deque |
| 171 | + * |
| 172 | + * @return the size of the deque |
| 173 | + */ |
| 174 | +publicintsize() { |
| 175 | +returnsize; |
| 176 | + } |
| 177 | + |
| 178 | +/** |
| 179 | + * Returns whether or not the deque is empty |
| 180 | + * |
| 181 | + * @return whether or not the deque is empty |
| 182 | + */ |
| 183 | +publicbooleanisEmpty() { |
| 184 | +returnhead ==null; |
| 185 | + } |
| 186 | + |
| 187 | +/** |
| 188 | + * Returns a stringified deque in a pretty form: |
| 189 | + * |
| 190 | + * <p>Head -> 1 <-> 2 <-> 3 <- Tail |
| 191 | + * |
| 192 | + * @return the stringified deque |
| 193 | + */ |
| 194 | +@Override |
| 195 | +publicStringtoString() { |
| 196 | +StringdequeString ="Head -> "; |
| 197 | +DequeNode<T>currNode =head; |
| 198 | +while (currNode !=null) { |
| 199 | +dequeString +=currNode.val; |
| 200 | + |
| 201 | +if (currNode.next !=null)dequeString +=" <-> "; |
| 202 | + |
| 203 | +currNode =currNode.next; |
| 204 | + } |
| 205 | + |
| 206 | +dequeString +=" <- Tail"; |
| 207 | + |
| 208 | +returndequeString; |
| 209 | + } |
| 210 | + |
| 211 | +publicstaticvoidmain(String[]args) { |
| 212 | +Deques<Integer>myDeque =newDeques<Integer>(); |
| 213 | +for (inti =0;i <42;i++) { |
| 214 | +if (i /42.0 <0.5) { |
| 215 | +myDeque.addFirst(i); |
| 216 | + }else { |
| 217 | +myDeque.addLast(i); |
| 218 | + } |
| 219 | + } |
| 220 | + |
| 221 | +System.out.println(myDeque); |
| 222 | +System.out.println("Size: " +myDeque.size()); |
| 223 | +System.out.println(); |
| 224 | + |
| 225 | +myDeque.pollFirst(); |
| 226 | +myDeque.pollFirst(); |
| 227 | +myDeque.pollLast(); |
| 228 | +System.out.println(myDeque); |
| 229 | +System.out.println("Size: " +myDeque.size()); |
| 230 | +System.out.println(); |
| 231 | + |
| 232 | +intdequeSize =myDeque.size(); |
| 233 | +for (inti =0;i <dequeSize;i++) { |
| 234 | +intremoving = -1; |
| 235 | +if (i /39.0 <0.5) { |
| 236 | +removing =myDeque.pollFirst(); |
| 237 | + }else { |
| 238 | +removing =myDeque.pollLast(); |
| 239 | + } |
| 240 | + |
| 241 | +System.out.println("Removing: " +removing); |
| 242 | + } |
| 243 | + |
| 244 | +System.out.println(myDeque); |
| 245 | +System.out.println(myDeque.size()); |
| 246 | + } |
| 247 | +} |