View Javadoc
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 {@code Deque}
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 {@code null} or {@code false}, depending on
51   * the operation).  The latter form of the insert operation is
52   * designed specifically for use with capacity-restricted
53   * {@code Deque} 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   * <table BORDER CELLPADDING=3 CELLSPACING=1>
60   * <caption>Summary of Deque methods</caption>
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 Deque#addFirst addFirst(e)}</td>
76   *    <td>{@link Deque#offerFirst offerFirst(e)}</td>
77   *    <td>{@link Deque#addLast addLast(e)}</td>
78   *    <td>{@link Deque#offerLast offerLast(e)}</td>
79   *  </tr>
80   *  <tr>
81   *    <td><b>Remove</b></td>
82   *    <td>{@link Deque#removeFirst removeFirst()}</td>
83   *    <td>{@link Deque#pollFirst pollFirst()}</td>
84   *    <td>{@link Deque#removeLast removeLast()}</td>
85   *    <td>{@link Deque#pollLast pollLast()}</td>
86   *  </tr>
87   *  <tr>
88   *    <td><b>Examine</b></td>
89   *    <td>{@link Deque#getFirst getFirst()}</td>
90   *    <td>{@link Deque#peekFirst peekFirst()}</td>
91   *    <td>{@link Deque#getLast getLast()}</td>
92   *    <td>{@link Deque#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 {@code Queue} interface are precisely equivalent to
100  * {@code Deque} methods as indicated in the following table:
101  *
102  * <table BORDER CELLPADDING=3 CELLSPACING=1>
103  * <caption>Comparison of Queue and Deque methods</caption>
104  *  <tr>
105  *    <td ALIGN=CENTER> <b>{@code Queue} Method</b></td>
106  *    <td ALIGN=CENTER> <b>Equivalent {@code Deque} 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  * {@code Deque} methods as indicated in the table below:
139  *
140  * <table BORDER CELLPADDING=3 CELLSPACING=1>
141  * <caption>Comparison of Stack and Deque methods</caption>
142  *  <tr>
143  *    <td ALIGN=CENTER> <b>Stack Method</b></td>
144  *    <td ALIGN=CENTER> <b>Equivalent {@code Deque} 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 {@code Deque} implementations are not strictly required
172  * to prohibit the insertion of null elements, they are strongly
173  * encouraged to do so.  Users of any {@code Deque} 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  * {@code null} is used as a special return value by various methods
177  * to indicated that the deque is empty.
178  *
179  * <p>{@code Deque} implementations generally do not define
180  * element-based versions of the {@code equals} and {@code hashCode}
181  * methods, but instead inherit the identity-based versions from class
182  * {@code Object}.
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 public interface Deque<E> extends Queue<E> {
194     /**
195      * Inserts the specified element at the front of this deque if it is
196      * possible to do so immediately without violating capacity restrictions,
197      * throwing an {@code IllegalStateException} if no space is currently
198      * available.  When using a capacity-restricted deque, it is generally
199      * preferable to 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      * throwing an {@code IllegalStateException} if no space is currently
217      * available.  When using a capacity-restricted deque, it is generally
218      * preferable to use method {@link #offerLast}.
219      *
220      * <p>This method is equivalent to {@link #add}.
221      *
222      * @param e the element to add
223      * @throws IllegalStateException if the element cannot be added at this
224      *         time due to capacity restrictions
225      * @throws ClassCastException if the class of the specified element
226      *         prevents it from being added to this deque
227      * @throws NullPointerException if the specified element is null and this
228      *         deque does not permit null elements
229      * @throws IllegalArgumentException if some property of the specified
230      *         element prevents it from being added to this deque
231      */
232     void addLast(E e);
233 
234     /**
235      * Inserts the specified element at the front of this deque unless it would
236      * violate capacity restrictions.  When using a capacity-restricted deque,
237      * this method is generally preferable to the {@link #addFirst} method,
238      * which can fail to insert an element only by throwing an exception.
239      *
240      * @param e the element to add
241      * @return {@code true} if the element was added to this deque, else
242      *         {@code false}
243      * @throws ClassCastException if the class of the specified element
244      *         prevents it from being added to this deque
245      * @throws NullPointerException if the specified element is null and this
246      *         deque does not permit null elements
247      * @throws IllegalArgumentException if some property of the specified
248      *         element prevents it from being added to this deque
249      */
250     boolean offerFirst(E e);
251 
252     /**
253      * Inserts the specified element at the end of this deque unless it would
254      * violate capacity restrictions.  When using a capacity-restricted deque,
255      * this method is generally preferable to the {@link #addLast} method,
256      * which can fail to insert an element only by throwing an exception.
257      *
258      * @param e the element to add
259      * @return {@code true} if the element was added to this deque, else
260      *         {@code false}
261      * @throws ClassCastException if the class of the specified element
262      *         prevents it from being added to this deque
263      * @throws NullPointerException if the specified element is null and this
264      *         deque does not permit null elements
265      * @throws IllegalArgumentException if some property of the specified
266      *         element prevents it from being added to this deque
267      */
268     boolean offerLast(E e);
269 
270     /**
271      * Retrieves and removes the first element of this deque.  This method
272      * differs from {@link #pollFirst pollFirst} only in that it throws an
273      * exception if this deque is empty.
274      *
275      * @return the head of this deque
276      * @throws NoSuchElementException if this deque is empty
277      */
278     E removeFirst();
279 
280     /**
281      * Retrieves and removes the last element of this deque.  This method
282      * differs from {@link #pollLast pollLast} only in that it throws an
283      * exception if this deque is empty.
284      *
285      * @return the tail of this deque
286      * @throws NoSuchElementException if this deque is empty
287      */
288     E removeLast();
289 
290     /**
291      * Retrieves and removes the first element of this deque,
292      * or returns {@code null} if this deque is empty.
293      *
294      * @return the head of this deque, or {@code null} if this deque is empty
295      */
296     E pollFirst();
297 
298     /**
299      * Retrieves and removes the last element of this deque,
300      * or returns {@code null} if this deque is empty.
301      *
302      * @return the tail of this deque, or {@code null} if this deque is empty
303      */
304     E pollLast();
305 
306     /**
307      * Retrieves, but does not remove, the first element of this deque.
308      *
309      * This method differs from {@link #peekFirst peekFirst} only in that it
310      * throws an exception if this deque is empty.
311      *
312      * @return the head of this deque
313      * @throws NoSuchElementException if this deque is empty
314      */
315     E getFirst();
316 
317     /**
318      * Retrieves, but does not remove, the last element of this deque.
319      * This method differs from {@link #peekLast peekLast} only in that it
320      * throws an exception if this deque is empty.
321      *
322      * @return the tail of this deque
323      * @throws NoSuchElementException if this deque is empty
324      */
325     E getLast();
326 
327     /**
328      * Retrieves, but does not remove, the first element of this deque,
329      * or returns {@code null} if this deque is empty.
330      *
331      * @return the head of this deque, or {@code null} if this deque is empty
332      */
333     E peekFirst();
334 
335     /**
336      * Retrieves, but does not remove, the last element of this deque,
337      * or returns {@code null} if this deque is empty.
338      *
339      * @return the tail of this deque, or {@code null} if this deque is empty
340      */
341     E peekLast();
342 
343     /**
344      * Removes the first occurrence of the specified element from this deque.
345      * If the deque does not contain the element, it is unchanged.
346      * More formally, removes the first element {@code e} such that
347      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
348      * (if such an element exists).
349      * Returns {@code true} if this deque contained the specified element
350      * (or equivalently, if this deque changed as a result of the call).
351      *
352      * @param o element to be removed from this deque, if present
353      * @return {@code true} if an element was removed as a result of this call
354      * @throws ClassCastException if the class of the specified element
355      *         is incompatible with this deque
356      * (<a href="Collection.html#optional-restrictions">optional</a>)
357      * @throws NullPointerException if the specified element is null and this
358      *         deque does not permit null elements
359      * (<a href="Collection.html#optional-restrictions">optional</a>)
360      */
361     boolean removeFirstOccurrence(Object o);
362 
363     /**
364      * Removes the last occurrence of the specified element from this deque.
365      * If the deque does not contain the element, it is unchanged.
366      * More formally, removes the last element {@code e} such that
367      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
368      * (if such an element exists).
369      * Returns {@code true} if this deque contained the specified element
370      * (or equivalently, if this deque changed as a result of the call).
371      *
372      * @param o element to be removed from this deque, if present
373      * @return {@code true} if an element was removed as a result of this call
374      * @throws ClassCastException if the class of the specified element
375      *         is incompatible with this deque
376      * (<a href="Collection.html#optional-restrictions">optional</a>)
377      * @throws NullPointerException if the specified element is null and this
378      *         deque does not permit null elements
379      * (<a href="Collection.html#optional-restrictions">optional</a>)
380      */
381     boolean removeLastOccurrence(Object o);
382 
383     // *** Queue methods ***
384 
385     /**
386      * Inserts the specified element into the queue represented by this deque
387      * (in other words, at the tail of this deque) if it is possible to do so
388      * immediately without violating capacity restrictions, returning
389      * {@code true} upon success and throwing an
390      * {@code IllegalStateException} if no space is currently available.
391      * When using a capacity-restricted deque, it is generally preferable to
392      * use {@link #offer(Object) offer}.
393      *
394      * <p>This method is equivalent to {@link #addLast}.
395      *
396      * @param e the element to add
397      * @return {@code true} (as specified by {@link Collection#add})
398      * @throws IllegalStateException if the element cannot be added at this
399      *         time due to capacity restrictions
400      * @throws ClassCastException if the class of the specified element
401      *         prevents it from being added to this deque
402      * @throws NullPointerException if the specified element is null and this
403      *         deque does not permit null elements
404      * @throws IllegalArgumentException if some property of the specified
405      *         element prevents it from being added to this deque
406      */
407     boolean add(E e);
408 
409     /**
410      * Inserts the specified element into the queue represented by this deque
411      * (in other words, at the tail of this deque) if it is possible to do so
412      * immediately without violating capacity restrictions, returning
413      * {@code true} upon success and {@code false} if no space is currently
414      * available.  When using a capacity-restricted deque, this method is
415      * generally preferable to the {@link #add} method, which can fail to
416      * insert an element only by throwing an exception.
417      *
418      * <p>This method is equivalent to {@link #offerLast}.
419      *
420      * @param e the element to add
421      * @return {@code true} if the element was added to this deque, else
422      *         {@code false}
423      * @throws ClassCastException if the class of the specified element
424      *         prevents it from being added to this deque
425      * @throws NullPointerException if the specified element is null and this
426      *         deque does not permit null elements
427      * @throws IllegalArgumentException if some property of the specified
428      *         element prevents it from being added to this deque
429      */
430     boolean offer(E e);
431 
432     /**
433      * Retrieves and removes the head of the queue represented by this deque
434      * (in other words, the first element of this deque).
435      * This method differs from {@link #poll poll} only in that it throws an
436      * exception if this deque is empty.
437      *
438      * <p>This method is equivalent to {@link #removeFirst()}.
439      *
440      * @return the head of the queue represented by this deque
441      * @throws NoSuchElementException if this deque is empty
442      */
443     E remove();
444 
445     /**
446      * Retrieves and removes the head of the queue represented by this deque
447      * (in other words, the first element of this deque), or returns
448      * {@code null} if this deque is empty.
449      *
450      * <p>This method is equivalent to {@link #pollFirst()}.
451      *
452      * @return the first element of this deque, or {@code null} if
453      *         this deque is empty
454      */
455     E poll();
456 
457     /**
458      * Retrieves, but does not remove, the head of the queue represented by
459      * this deque (in other words, the first element of this deque).
460      * This method differs from {@link #peek peek} only in that it throws an
461      * exception if this deque is empty.
462      *
463      * <p>This method is equivalent to {@link #getFirst()}.
464      *
465      * @return the head of the queue represented by this deque
466      * @throws NoSuchElementException if this deque is empty
467      */
468     E element();
469 
470     /**
471      * Retrieves, but does not remove, the head of the queue represented by
472      * this deque (in other words, the first element of this deque), or
473      * returns {@code null} if this deque is empty.
474      *
475      * <p>This method is equivalent to {@link #peekFirst()}.
476      *
477      * @return the head of the queue represented by this deque, or
478      *         {@code null} if this deque is empty
479      */
480     E peek();
481 
482 
483     // *** Stack methods ***
484 
485     /**
486      * Pushes an element onto the stack represented by this deque (in other
487      * words, at the head of this deque) if it is possible to do so
488      * immediately without violating capacity restrictions, throwing an
489      * {@code IllegalStateException} if no space is currently available.
490      *
491      * <p>This method is equivalent to {@link #addFirst}.
492      *
493      * @param e the element to push
494      * @throws IllegalStateException if the element cannot be added at this
495      *         time due to capacity restrictions
496      * @throws ClassCastException if the class of the specified element
497      *         prevents it from being added to this deque
498      * @throws NullPointerException if the specified element is null and this
499      *         deque does not permit null elements
500      * @throws IllegalArgumentException if some property of the specified
501      *         element prevents it from being added to this deque
502      */
503     void push(E e);
504 
505     /**
506      * Pops an element from the stack represented by this deque.  In other
507      * words, removes and returns the first element of this deque.
508      *
509      * <p>This method is equivalent to {@link #removeFirst()}.
510      *
511      * @return the element at the front of this deque (which is the top
512      *         of the stack represented by this deque)
513      * @throws NoSuchElementException if this deque is empty
514      */
515     E pop();
516 
517 
518     // *** Collection methods ***
519 
520     /**
521      * Removes the first occurrence of the specified element from this deque.
522      * If the deque does not contain the element, it is unchanged.
523      * More formally, removes the first element {@code e} such that
524      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
525      * (if such an element exists).
526      * Returns {@code true} if this deque contained the specified element
527      * (or equivalently, if this deque changed as a result of the call).
528      *
529      * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
530      *
531      * @param o element to be removed from this deque, if present
532      * @return {@code true} if an element was removed as a result of this call
533      * @throws ClassCastException if the class of the specified element
534      *         is incompatible with this deque
535      * (<a href="Collection.html#optional-restrictions">optional</a>)
536      * @throws NullPointerException if the specified element is null and this
537      *         deque does not permit null elements
538      * (<a href="Collection.html#optional-restrictions">optional</a>)
539      */
540     boolean remove(Object o);
541 
542     /**
543      * Returns {@code true} if this deque contains the specified element.
544      * More formally, returns {@code true} if and only if this deque contains
545      * at least one element {@code e} such that
546      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
547      *
548      * @param o element whose presence in this deque is to be tested
549      * @return {@code true} if this deque contains the specified element
550      * @throws ClassCastException if the type of the specified element
551      *         is incompatible with this deque
552      * (<a href="Collection.html#optional-restrictions">optional</a>)
553      * @throws NullPointerException if the specified element is null and this
554      *         deque does not permit null elements
555      * (<a href="Collection.html#optional-restrictions">optional</a>)
556      */
557     boolean contains(Object o);
558 
559     /**
560      * Returns the number of elements in this deque.
561      *
562      * @return the number of elements in this deque
563      */
564     public int size();
565 
566     /**
567      * Returns an iterator over the elements in this deque in proper sequence.
568      * The elements will be returned in order from first (head) to last (tail).
569      *
570      * @return an iterator over the elements in this deque in proper sequence
571      */
572     Iterator<E> iterator();
573 
574     /**
575      * Returns an iterator over the elements in this deque in reverse
576      * sequential order.  The elements will be returned in order from
577      * last (tail) to first (head).
578      *
579      * @return an iterator over the elements in this deque in reverse
580      * sequence
581      */
582     Iterator<E> descendingIterator();
583 
584 }