Source for java.util.Deque

   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/licenses/publicdomain
   5:  */
   6: 
   7: package java.util;
   8: 
   9: /**
  10:  * A linear collection that supports element insertion and removal at
  11:  * both ends.  The name <i>deque</i> is short for "double ended queue"
  12:  * and is usually pronounced "deck".  Most <tt>Deque</tt>
  13:  * implementations place no fixed limits on the number of elements
  14:  * they may contain, but this interface supports capacity-restricted
  15:  * deques as well as those with no fixed size limit.
  16:  *
  17:  * <p>This interface defines methods to access the elements at both
  18:  * ends of the deque.  Methods are provided to insert, remove, and
  19:  * examine the element.  Each of these methods exists in two forms:
  20:  * one throws an exception if the operation fails, the other returns a
  21:  * special value (either <tt>null</tt> or <tt>false</tt>, depending on
  22:  * the operation).  The latter form of the insert operation is
  23:  * designed specifically for use with capacity-restricted
  24:  * <tt>Deque</tt> implementations; in most implementations, insert
  25:  * operations cannot fail.
  26:  *
  27:  * <p>The twelve methods described above are summarized in the
  28:  * following table:
  29:  *
  30:  * <p>
  31:  * <table BORDER CELLPADDING=3 CELLSPACING=1>
  32:  *  <tr>
  33:  *    <td></td>
  34:  *    <td ALIGN=CENTER COLSPAN = 2> <b>First Element (Head)</b></td>
  35:  *    <td ALIGN=CENTER COLSPAN = 2> <b>Last Element (Tail)</b></td>
  36:  *  </tr>
  37:  *  <tr>
  38:  *    <td></td>
  39:  *    <td ALIGN=CENTER><em>Throws exception</em></td>
  40:  *    <td ALIGN=CENTER><em>Special value</em></td>
  41:  *    <td ALIGN=CENTER><em>Throws exception</em></td>
  42:  *    <td ALIGN=CENTER><em>Special value</em></td>
  43:  *  </tr>
  44:  *  <tr>
  45:  *    <td><b>Insert</b></td>
  46:  *    <td>{@link #addFirst addFirst(e)}</td>
  47:  *    <td>{@link #offerFirst offerFirst(e)}</td>
  48:  *    <td>{@link #addLast addLast(e)}</td>
  49:  *    <td>{@link #offerLast offerLast(e)}</td>
  50:  *  </tr>
  51:  *  <tr>
  52:  *    <td><b>Remove</b></td>
  53:  *    <td>{@link #removeFirst removeFirst()}</td>
  54:  *    <td>{@link #pollFirst pollFirst()}</td>
  55:  *    <td>{@link #removeLast removeLast()}</td>
  56:  *    <td>{@link #pollLast pollLast()}</td>
  57:  *  </tr>
  58:  *  <tr>
  59:  *    <td><b>Examine</b></td>
  60:  *    <td>{@link #getFirst getFirst()}</td>
  61:  *    <td>{@link #peekFirst peekFirst()}</td>
  62:  *    <td>{@link #getLast getLast()}</td>
  63:  *    <td>{@link #peekLast peekLast()}</td>
  64:  *  </tr>
  65:  * </table>
  66:  *
  67:  * <p>This interface extends the {@link Queue} interface.  When a deque is
  68:  * used as a queue, FIFO (First-In-First-Out) behavior results.  Elements are
  69:  * added at the end of the deque and removed from the beginning.  The methods
  70:  * inherited from the <tt>Queue</tt> interface are precisely equivalent to
  71:  * <tt>Deque</tt> methods as indicated in the following table:
  72:  *
  73:  * <p>
  74:  * <table BORDER CELLPADDING=3 CELLSPACING=1>
  75:  *  <tr>
  76:  *    <td ALIGN=CENTER> <b><tt>Queue</tt> Method</b></td>
  77:  *    <td ALIGN=CENTER> <b>Equivalent <tt>Deque</tt> Method</b></td>
  78:  *  </tr>
  79:  *  <tr>
  80:  *    <td>{@link java.util.Queue#add add(e)}</td>
  81:  *    <td>{@link #addLast addLast(e)}</td>
  82:  *  </tr>
  83:  *  <tr>
  84:  *    <td>{@link java.util.Queue#offer offer(e)}</td>
  85:  *    <td>{@link #offerLast offerLast(e)}</td>
  86:  *  </tr>
  87:  *  <tr>
  88:  *    <td>{@link java.util.Queue#remove remove()}</td>
  89:  *    <td>{@link #removeFirst removeFirst()}</td>
  90:  *  </tr>
  91:  *  <tr>
  92:  *    <td>{@link java.util.Queue#poll poll()}</td>
  93:  *    <td>{@link #pollFirst pollFirst()}</td>
  94:  *  </tr>
  95:  *  <tr>
  96:  *    <td>{@link java.util.Queue#element element()}</td>
  97:  *    <td>{@link #getFirst getFirst()}</td>
  98:  *  </tr>
  99:  *  <tr>
 100:  *    <td>{@link java.util.Queue#peek peek()}</td>
 101:  *    <td>{@link #peek peekFirst()}</td>
 102:  *  </tr>
 103:  * </table>
 104:  *
 105:  * <p>Deques can also be used as LIFO (Last-In-First-Out) stacks.  This
 106:  * interface should be used in preference to the legacy {@link Stack} class.
 107:  * When a deque is used as a stack, elements are pushed and popped from the
 108:  * beginning of the deque.  Stack methods are precisely equivalent to
 109:  * <tt>Deque</tt> methods as indicated in the table below:
 110:  *
 111:  * <p>
 112:  * <table BORDER CELLPADDING=3 CELLSPACING=1>
 113:  *  <tr>
 114:  *    <td ALIGN=CENTER> <b>Stack Method</b></td>
 115:  *    <td ALIGN=CENTER> <b>Equivalent <tt>Deque</tt> Method</b></td>
 116:  *  </tr>
 117:  *  <tr>
 118:  *    <td>{@link #push push(e)}</td>
 119:  *    <td>{@link #addFirst addFirst(e)}</td>
 120:  *  </tr>
 121:  *  <tr>
 122:  *    <td>{@link #pop pop()}</td>
 123:  *    <td>{@link #removeFirst removeFirst()}</td>
 124:  *  </tr>
 125:  *  <tr>
 126:  *    <td>{@link #peek peek()}</td>
 127:  *    <td>{@link #peekFirst peekFirst()}</td>
 128:  *  </tr>
 129:  * </table>
 130:  *
 131:  * <p>Note that the {@link #peek peek} method works equally well when
 132:  * a deque is used as a queue or a stack; in either case, elements are
 133:  * drawn from the beginning of the deque.
 134:  *
 135:  * <p>This interface provides two methods to remove interior
 136:  * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and
 137:  * {@link #removeLastOccurrence removeLastOccurrence}.
 138:  *
 139:  * <p>Unlike the {@link List} interface, this interface does not
 140:  * provide support for indexed access to elements.
 141:  *
 142:  * <p>While <tt>Deque</tt> implementations are not strictly required
 143:  * to prohibit the insertion of null elements, they are strongly
 144:  * encouraged to do so.  Users of any <tt>Deque</tt> implementations
 145:  * that do allow null elements are strongly encouraged <i>not</i> to
 146:  * take advantage of the ability to insert nulls.  This is so because
 147:  * <tt>null</tt> is used as a special return value by various methods
 148:  * to indicated that the deque is empty.
 149:  *
 150:  * <p><tt>Deque</tt> implementations generally do not define
 151:  * element-based versions of the <tt>equals</tt> and <tt>hashCode</tt>
 152:  * methods, but instead inherit the identity-based versions from class
 153:  * <tt>Object</tt>.
 154:  *
 155:  * <p>This interface is a member of the <a
 156:  * href="{@docRoot}/../technotes/guides/collections/index.html"> Java Collections
 157:  * Framework</a>.
 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: 
 165: public 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&nbsp;?&nbsp;e==null&nbsp;:&nbsp;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&nbsp;?&nbsp;e==null&nbsp;:&nbsp;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&nbsp;?&nbsp;e==null&nbsp;:&nbsp;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&nbsp;?&nbsp;e==null&nbsp;:&nbsp;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: }