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