1/* 2 * Written by Doug Lea and Josh Bloch with assistance from members of 3 * JCP JSR-166 Expert Group and released to the public domain, as explained 4 * at http://creativecommons.org/publicdomain/zero/1.0/ 5 */ 6 7package java.util; 8 9// BEGIN android-note 10// removed link to collections framework docs 11// END android-note 12 13/** 14 * A linear collection that supports element insertion and removal at 15 * both ends. The name <i>deque</i> is short for "double ended queue" 16 * and is usually pronounced "deck". Most <tt>Deque</tt> 17 * implementations place no fixed limits on the number of elements 18 * they may contain, but this interface supports capacity-restricted 19 * deques as well as those with no fixed size limit. 20 * 21 * <p>This interface defines methods to access the elements at both 22 * ends of the deque. Methods are provided to insert, remove, and 23 * examine the element. Each of these methods exists in two forms: 24 * one throws an exception if the operation fails, the other returns a 25 * special value (either <tt>null</tt> or <tt>false</tt>, depending on 26 * the operation). The latter form of the insert operation is 27 * designed specifically for use with capacity-restricted 28 * <tt>Deque</tt> implementations; in most implementations, insert 29 * operations cannot fail. 30 * 31 * <p>The twelve methods described above are summarized in the 32 * following table: 33 * 34 * <p> 35 * <table BORDER CELLPADDING=3 CELLSPACING=1> 36 * <tr> 37 * <td></td> 38 * <td ALIGN=CENTER COLSPAN = 2> <b>First Element (Head)</b></td> 39 * <td ALIGN=CENTER COLSPAN = 2> <b>Last Element (Tail)</b></td> 40 * </tr> 41 * <tr> 42 * <td></td> 43 * <td ALIGN=CENTER><em>Throws exception</em></td> 44 * <td ALIGN=CENTER><em>Special value</em></td> 45 * <td ALIGN=CENTER><em>Throws exception</em></td> 46 * <td ALIGN=CENTER><em>Special value</em></td> 47 * </tr> 48 * <tr> 49 * <td><b>Insert</b></td> 50 * <td>{@link #addFirst addFirst(e)}</td> 51 * <td>{@link #offerFirst offerFirst(e)}</td> 52 * <td>{@link #addLast addLast(e)}</td> 53 * <td>{@link #offerLast offerLast(e)}</td> 54 * </tr> 55 * <tr> 56 * <td><b>Remove</b></td> 57 * <td>{@link #removeFirst removeFirst()}</td> 58 * <td>{@link #pollFirst pollFirst()}</td> 59 * <td>{@link #removeLast removeLast()}</td> 60 * <td>{@link #pollLast pollLast()}</td> 61 * </tr> 62 * <tr> 63 * <td><b>Examine</b></td> 64 * <td>{@link #getFirst getFirst()}</td> 65 * <td>{@link #peekFirst peekFirst()}</td> 66 * <td>{@link #getLast getLast()}</td> 67 * <td>{@link #peekLast peekLast()}</td> 68 * </tr> 69 * </table> 70 * 71 * <p>This interface extends the {@link Queue} interface. When a deque is 72 * used as a queue, FIFO (First-In-First-Out) behavior results. Elements are 73 * added at the end of the deque and removed from the beginning. The methods 74 * inherited from the <tt>Queue</tt> interface are precisely equivalent to 75 * <tt>Deque</tt> methods as indicated in the following table: 76 * 77 * <p> 78 * <table BORDER CELLPADDING=3 CELLSPACING=1> 79 * <tr> 80 * <td ALIGN=CENTER> <b><tt>Queue</tt> Method</b></td> 81 * <td ALIGN=CENTER> <b>Equivalent <tt>Deque</tt> Method</b></td> 82 * </tr> 83 * <tr> 84 * <td>{@link java.util.Queue#add add(e)}</td> 85 * <td>{@link #addLast addLast(e)}</td> 86 * </tr> 87 * <tr> 88 * <td>{@link java.util.Queue#offer offer(e)}</td> 89 * <td>{@link #offerLast offerLast(e)}</td> 90 * </tr> 91 * <tr> 92 * <td>{@link java.util.Queue#remove remove()}</td> 93 * <td>{@link #removeFirst removeFirst()}</td> 94 * </tr> 95 * <tr> 96 * <td>{@link java.util.Queue#poll poll()}</td> 97 * <td>{@link #pollFirst pollFirst()}</td> 98 * </tr> 99 * <tr> 100 * <td>{@link java.util.Queue#element element()}</td> 101 * <td>{@link #getFirst getFirst()}</td> 102 * </tr> 103 * <tr> 104 * <td>{@link java.util.Queue#peek peek()}</td> 105 * <td>{@link #peek peekFirst()}</td> 106 * </tr> 107 * </table> 108 * 109 * <p>Deques can also be used as LIFO (Last-In-First-Out) stacks. This 110 * interface should be used in preference to the legacy {@link Stack} class. 111 * When a deque is used as a stack, elements are pushed and popped from the 112 * beginning of the deque. Stack methods are precisely equivalent to 113 * <tt>Deque</tt> methods as indicated in the table below: 114 * 115 * <p> 116 * <table BORDER CELLPADDING=3 CELLSPACING=1> 117 * <tr> 118 * <td ALIGN=CENTER> <b>Stack Method</b></td> 119 * <td ALIGN=CENTER> <b>Equivalent <tt>Deque</tt> Method</b></td> 120 * </tr> 121 * <tr> 122 * <td>{@link #push push(e)}</td> 123 * <td>{@link #addFirst addFirst(e)}</td> 124 * </tr> 125 * <tr> 126 * <td>{@link #pop pop()}</td> 127 * <td>{@link #removeFirst removeFirst()}</td> 128 * </tr> 129 * <tr> 130 * <td>{@link #peek peek()}</td> 131 * <td>{@link #peekFirst peekFirst()}</td> 132 * </tr> 133 * </table> 134 * 135 * <p>Note that the {@link #peek peek} method works equally well when 136 * a deque is used as a queue or a stack; in either case, elements are 137 * drawn from the beginning of the deque. 138 * 139 * <p>This interface provides two methods to remove interior 140 * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and 141 * {@link #removeLastOccurrence removeLastOccurrence}. 142 * 143 * <p>Unlike the {@link List} interface, this interface does not 144 * provide support for indexed access to elements. 145 * 146 * <p>While <tt>Deque</tt> implementations are not strictly required 147 * to prohibit the insertion of null elements, they are strongly 148 * encouraged to do so. Users of any <tt>Deque</tt> implementations 149 * that do allow null elements are strongly encouraged <i>not</i> to 150 * take advantage of the ability to insert nulls. This is so because 151 * <tt>null</tt> is used as a special return value by various methods 152 * to indicated that the deque is empty. 153 * 154 * <p><tt>Deque</tt> implementations generally do not define 155 * element-based versions of the <tt>equals</tt> and <tt>hashCode</tt> 156 * methods, but instead inherit the identity-based versions from class 157 * <tt>Object</tt>. 158 * 159 * @author Doug Lea 160 * @author Josh Bloch 161 * @since 1.6 162 * @param <E> the type of elements held in this collection 163 */ 164 165public interface Deque<E> extends Queue<E> { 166 /** 167 * Inserts the specified element at the front of this deque if it is 168 * possible to do so immediately without violating capacity restrictions. 169 * When using a capacity-restricted deque, it is generally preferable to 170 * use method {@link #offerFirst}. 171 * 172 * @param e the element to add 173 * @throws IllegalStateException if the element cannot be added at this 174 * time due to capacity restrictions 175 * @throws ClassCastException if the class of the specified element 176 * prevents it from being added to this deque 177 * @throws NullPointerException if the specified element is null and this 178 * deque does not permit null elements 179 * @throws IllegalArgumentException if some property of the specified 180 * element prevents it from being added to this deque 181 */ 182 void addFirst(E e); 183 184 /** 185 * Inserts the specified element at the end of this deque if it is 186 * possible to do so immediately without violating capacity restrictions. 187 * When using a capacity-restricted deque, it is generally preferable to 188 * use method {@link #offerLast}. 189 * 190 * <p>This method is equivalent to {@link #add}. 191 * 192 * @param e the element to add 193 * @throws IllegalStateException if the element cannot be added at this 194 * time due to capacity restrictions 195 * @throws ClassCastException if the class of the specified element 196 * prevents it from being added to this deque 197 * @throws NullPointerException if the specified element is null and this 198 * deque does not permit null elements 199 * @throws IllegalArgumentException if some property of the specified 200 * element prevents it from being added to this deque 201 */ 202 void addLast(E e); 203 204 /** 205 * Inserts the specified element at the front of this deque unless it would 206 * violate capacity restrictions. When using a capacity-restricted deque, 207 * this method is generally preferable to the {@link #addFirst} method, 208 * which can fail to insert an element only by throwing an exception. 209 * 210 * @param e the element to add 211 * @return <tt>true</tt> if the element was added to this deque, else 212 * <tt>false</tt> 213 * @throws ClassCastException if the class of the specified element 214 * prevents it from being added to this deque 215 * @throws NullPointerException if the specified element is null and this 216 * deque does not permit null elements 217 * @throws IllegalArgumentException if some property of the specified 218 * element prevents it from being added to this deque 219 */ 220 boolean offerFirst(E e); 221 222 /** 223 * Inserts the specified element at the end of this deque unless it would 224 * violate capacity restrictions. When using a capacity-restricted deque, 225 * this method is generally preferable to the {@link #addLast} method, 226 * which can fail to insert an element only by throwing an exception. 227 * 228 * @param e the element to add 229 * @return <tt>true</tt> if the element was added to this deque, else 230 * <tt>false</tt> 231 * @throws ClassCastException if the class of the specified element 232 * prevents it from being added to this deque 233 * @throws NullPointerException if the specified element is null and this 234 * deque does not permit null elements 235 * @throws IllegalArgumentException if some property of the specified 236 * element prevents it from being added to this deque 237 */ 238 boolean offerLast(E e); 239 240 /** 241 * Retrieves and removes the first element of this deque. This method 242 * differs from {@link #pollFirst pollFirst} only in that it throws an 243 * exception if this deque is empty. 244 * 245 * @return the head of this deque 246 * @throws NoSuchElementException if this deque is empty 247 */ 248 E removeFirst(); 249 250 /** 251 * Retrieves and removes the last element of this deque. This method 252 * differs from {@link #pollLast pollLast} only in that it throws an 253 * exception if this deque is empty. 254 * 255 * @return the tail of this deque 256 * @throws NoSuchElementException if this deque is empty 257 */ 258 E removeLast(); 259 260 /** 261 * Retrieves and removes the first element of this deque, 262 * or returns <tt>null</tt> if this deque is empty. 263 * 264 * @return the head of this deque, or <tt>null</tt> if this deque is empty 265 */ 266 E pollFirst(); 267 268 /** 269 * Retrieves and removes the last element of this deque, 270 * or returns <tt>null</tt> if this deque is empty. 271 * 272 * @return the tail of this deque, or <tt>null</tt> if this deque is empty 273 */ 274 E pollLast(); 275 276 /** 277 * Retrieves, but does not remove, the first element of this deque. 278 * 279 * This method differs from {@link #peekFirst peekFirst} only in that it 280 * throws an exception if this deque is empty. 281 * 282 * @return the head of this deque 283 * @throws NoSuchElementException if this deque is empty 284 */ 285 E getFirst(); 286 287 /** 288 * Retrieves, but does not remove, the last element of this deque. 289 * This method differs from {@link #peekLast peekLast} only in that it 290 * throws an exception if this deque is empty. 291 * 292 * @return the tail of this deque 293 * @throws NoSuchElementException if this deque is empty 294 */ 295 E getLast(); 296 297 /** 298 * Retrieves, but does not remove, the first element of this deque, 299 * or returns <tt>null</tt> if this deque is empty. 300 * 301 * @return the head of this deque, or <tt>null</tt> if this deque is empty 302 */ 303 E peekFirst(); 304 305 /** 306 * Retrieves, but does not remove, the last element of this deque, 307 * or returns <tt>null</tt> if this deque is empty. 308 * 309 * @return the tail of this deque, or <tt>null</tt> if this deque is empty 310 */ 311 E peekLast(); 312 313 /** 314 * Removes the first occurrence of the specified element from this deque. 315 * If the deque does not contain the element, it is unchanged. 316 * More formally, removes the first element <tt>e</tt> such that 317 * <tt>(o==null ? e==null : o.equals(e))</tt> 318 * (if such an element exists). 319 * Returns <tt>true</tt> if this deque contained the specified element 320 * (or equivalently, if this deque changed as a result of the call). 321 * 322 * @param o element to be removed from this deque, if present 323 * @return <tt>true</tt> if an element was removed as a result of this call 324 * @throws ClassCastException if the class of the specified element 325 * is incompatible with this deque (optional) 326 * @throws NullPointerException if the specified element is null and this 327 * deque does not permit null elements (optional) 328 */ 329 boolean removeFirstOccurrence(Object o); 330 331 /** 332 * Removes the last occurrence of the specified element from this deque. 333 * If the deque does not contain the element, it is unchanged. 334 * More formally, removes the last element <tt>e</tt> such that 335 * <tt>(o==null ? e==null : o.equals(e))</tt> 336 * (if such an element exists). 337 * Returns <tt>true</tt> if this deque contained the specified element 338 * (or equivalently, if this deque changed as a result of the call). 339 * 340 * @param o element to be removed from this deque, if present 341 * @return <tt>true</tt> if an element was removed as a result of this call 342 * @throws ClassCastException if the class of the specified element 343 * is incompatible with this deque (optional) 344 * @throws NullPointerException if the specified element is null and this 345 * deque does not permit null elements (optional) 346 */ 347 boolean removeLastOccurrence(Object o); 348 349 // *** Queue methods *** 350 351 /** 352 * Inserts the specified element into the queue represented by this deque 353 * (in other words, at the tail of this deque) if it is possible to do so 354 * immediately without violating capacity restrictions, returning 355 * <tt>true</tt> upon success and throwing an 356 * <tt>IllegalStateException</tt> if no space is currently available. 357 * When using a capacity-restricted deque, it is generally preferable to 358 * use {@link #offer(Object) offer}. 359 * 360 * <p>This method is equivalent to {@link #addLast}. 361 * 362 * @param e the element to add 363 * @return <tt>true</tt> (as specified by {@link Collection#add}) 364 * @throws IllegalStateException if the element cannot be added at this 365 * time due to capacity restrictions 366 * @throws ClassCastException if the class of the specified element 367 * prevents it from being added to this deque 368 * @throws NullPointerException if the specified element is null and this 369 * deque does not permit null elements 370 * @throws IllegalArgumentException if some property of the specified 371 * element prevents it from being added to this deque 372 */ 373 boolean add(E e); 374 375 /** 376 * Inserts the specified element into the queue represented by this deque 377 * (in other words, at the tail of this deque) if it is possible to do so 378 * immediately without violating capacity restrictions, returning 379 * <tt>true</tt> upon success and <tt>false</tt> if no space is currently 380 * available. When using a capacity-restricted deque, this method is 381 * generally preferable to the {@link #add} method, which can fail to 382 * insert an element only by throwing an exception. 383 * 384 * <p>This method is equivalent to {@link #offerLast}. 385 * 386 * @param e the element to add 387 * @return <tt>true</tt> if the element was added to this deque, else 388 * <tt>false</tt> 389 * @throws ClassCastException if the class of the specified element 390 * prevents it from being added to this deque 391 * @throws NullPointerException if the specified element is null and this 392 * deque does not permit null elements 393 * @throws IllegalArgumentException if some property of the specified 394 * element prevents it from being added to this deque 395 */ 396 boolean offer(E e); 397 398 /** 399 * Retrieves and removes the head of the queue represented by this deque 400 * (in other words, the first element of this deque). 401 * This method differs from {@link #poll poll} only in that it throws an 402 * exception if this deque is empty. 403 * 404 * <p>This method is equivalent to {@link #removeFirst()}. 405 * 406 * @return the head of the queue represented by this deque 407 * @throws NoSuchElementException if this deque is empty 408 */ 409 E remove(); 410 411 /** 412 * Retrieves and removes the head of the queue represented by this deque 413 * (in other words, the first element of this deque), or returns 414 * <tt>null</tt> if this deque is empty. 415 * 416 * <p>This method is equivalent to {@link #pollFirst()}. 417 * 418 * @return the first element of this deque, or <tt>null</tt> if 419 * this deque is empty 420 */ 421 E poll(); 422 423 /** 424 * Retrieves, but does not remove, the head of the queue represented by 425 * this deque (in other words, the first element of this deque). 426 * This method differs from {@link #peek peek} only in that it throws an 427 * exception if this deque is empty. 428 * 429 * <p>This method is equivalent to {@link #getFirst()}. 430 * 431 * @return the head of the queue represented by this deque 432 * @throws NoSuchElementException if this deque is empty 433 */ 434 E element(); 435 436 /** 437 * Retrieves, but does not remove, the head of the queue represented by 438 * this deque (in other words, the first element of this deque), or 439 * returns <tt>null</tt> if this deque is empty. 440 * 441 * <p>This method is equivalent to {@link #peekFirst()}. 442 * 443 * @return the head of the queue represented by this deque, or 444 * <tt>null</tt> if this deque is empty 445 */ 446 E peek(); 447 448 449 // *** Stack methods *** 450 451 /** 452 * Pushes an element onto the stack represented by this deque (in other 453 * words, at the head of this deque) if it is possible to do so 454 * immediately without violating capacity restrictions, returning 455 * <tt>true</tt> upon success and throwing an 456 * <tt>IllegalStateException</tt> if no space is currently available. 457 * 458 * <p>This method is equivalent to {@link #addFirst}. 459 * 460 * @param e the element to push 461 * @throws IllegalStateException if the element cannot be added at this 462 * time due to capacity restrictions 463 * @throws ClassCastException if the class of the specified element 464 * prevents it from being added to this deque 465 * @throws NullPointerException if the specified element is null and this 466 * deque does not permit null elements 467 * @throws IllegalArgumentException if some property of the specified 468 * element prevents it from being added to this deque 469 */ 470 void push(E e); 471 472 /** 473 * Pops an element from the stack represented by this deque. In other 474 * words, removes and returns the first element of this deque. 475 * 476 * <p>This method is equivalent to {@link #removeFirst()}. 477 * 478 * @return the element at the front of this deque (which is the top 479 * of the stack represented by this deque) 480 * @throws NoSuchElementException if this deque is empty 481 */ 482 E pop(); 483 484 485 // *** Collection methods *** 486 487 /** 488 * Removes the first occurrence of the specified element from this deque. 489 * If the deque does not contain the element, it is unchanged. 490 * More formally, removes the first element <tt>e</tt> such that 491 * <tt>(o==null ? e==null : o.equals(e))</tt> 492 * (if such an element exists). 493 * Returns <tt>true</tt> if this deque contained the specified element 494 * (or equivalently, if this deque changed as a result of the call). 495 * 496 * <p>This method is equivalent to {@link #removeFirstOccurrence}. 497 * 498 * @param o element to be removed from this deque, if present 499 * @return <tt>true</tt> if an element was removed as a result of this call 500 * @throws ClassCastException if the class of the specified element 501 * is incompatible with this deque (optional) 502 * @throws NullPointerException if the specified element is null and this 503 * deque does not permit null elements (optional) 504 */ 505 boolean remove(Object o); 506 507 /** 508 * Returns <tt>true</tt> if this deque contains the specified element. 509 * More formally, returns <tt>true</tt> if and only if this deque contains 510 * at least one element <tt>e</tt> such that 511 * <tt>(o==null ? e==null : o.equals(e))</tt>. 512 * 513 * @param o element whose presence in this deque is to be tested 514 * @return <tt>true</tt> if this deque contains the specified element 515 * @throws ClassCastException if the type of the specified element 516 * is incompatible with this deque (optional) 517 * @throws NullPointerException if the specified element is null and this 518 * deque does not permit null elements (optional) 519 */ 520 boolean contains(Object o); 521 522 /** 523 * Returns the number of elements in this deque. 524 * 525 * @return the number of elements in this deque 526 */ 527 public int size(); 528 529 /** 530 * Returns an iterator over the elements in this deque in proper sequence. 531 * The elements will be returned in order from first (head) to last (tail). 532 * 533 * @return an iterator over the elements in this deque in proper sequence 534 */ 535 Iterator<E> iterator(); 536 537 /** 538 * Returns an iterator over the elements in this deque in reverse 539 * sequential order. The elements will be returned in order from 540 * last (tail) to first (head). 541 * 542 * @return an iterator over the elements in this deque in reverse 543 * sequence 544 */ 545 Iterator<E> descendingIterator(); 546 547} 548