ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/Deque.java
Revision: 1.8
Committed: Sat May 14 02:22:28 2005 UTC (18 years, 11 months ago) by jsr166
Branch: MAIN
Changes since 1.7: +232 -148 lines
Log Message: 
doc fixes

File Contents

# User Rev Content
1 dl 1.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 dl 1.3 * <p>The twelve methods described above are summarized in the
28 jsr166 1.5 * following table:
29 dl 1.3 *
30 jsr166 1.7 * <p>
31     * <table BORDER CELLPADDING=3 CELLSPACING=1>
32 dl 1.1 * <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 jsr166 1.8 * <td ALIGN=CENTER><em>Special value</em></td>
41 dl 1.1 * <td ALIGN=CENTER><em>Throws exception</em></td>
42 jsr166 1.8 * <td ALIGN=CENTER><em>Special value</em></td>
43 dl 1.1 * </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 dl 1.4 * added at the end of the deque and removed from the beginning. The methods
70 dl 1.1 * inherited from the <tt>Queue</tt> interface are precisely equivalent to
71 jsr166 1.5 * <tt>Deque</tt> methods as indicated in the following table:
72 dl 1.1 *
73 jsr166 1.7 * <p>
74     * <table BORDER CELLPADDING=3 CELLSPACING=1>
75 dl 1.1 * <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 jsr166 1.8 * <td>{@link java.util.Queue#add add(e)}</td>
81     * <td>{@link #addLast addLast(e)}</td>
82     * </tr>
83     * <tr>
84 dl 1.1 * <td>{@link java.util.Queue#offer offer(e)}</td>
85     * <td>{@link #offerLast offerLast(e)}</td>
86 jsr166 1.5 * </tr>
87     * <tr>
88 jsr166 1.8 * <td>{@link java.util.Queue#remove remove()}</td>
89     * <td>{@link #removeFirst removeFirst()}</td>
90 jsr166 1.5 * </tr>
91     * <tr>
92 dl 1.1 * <td>{@link java.util.Queue#poll poll()}</td>
93     * <td>{@link #pollFirst pollFirst()}</td>
94 jsr166 1.5 * </tr>
95     * <tr>
96 jsr166 1.8 * <td>{@link java.util.Queue#element element()}</td>
97     * <td>{@link #getFirst getFirst()}</td>
98 jsr166 1.5 * </tr>
99     * <tr>
100 dl 1.1 * <td>{@link java.util.Queue#peek peek()}</td>
101     * <td>{@link #peek peekFirst()}</td>
102 jsr166 1.5 * </tr>
103 dl 1.1 * </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 dl 1.3 * When a deque is used as a stack, elements are pushed and popped from the
108 dl 1.1 * beginning of the deque. Stack methods are precisely equivalent to
109 jsr166 1.5 * <tt>Deque</tt> methods as indicated in the table below:
110 dl 1.1 *
111 jsr166 1.7 * <p>
112     * <table BORDER CELLPADDING=3 CELLSPACING=1>
113 dl 1.1 * <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 jsr166 1.5 * </tr>
121     * <tr>
122 dl 1.1 * <td>{@link #pop pop()}</td>
123     * <td>{@link #removeFirst removeFirst()}</td>
124 jsr166 1.5 * </tr>
125     * <tr>
126 dl 1.1 * <td>{@link #peek peek()}</td>
127     * <td>{@link #peekFirst peekFirst()}</td>
128 jsr166 1.5 * </tr>
129 dl 1.1 * </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 dl 1.2 * <p>This interface provides two methods to remove interior
136 dl 1.1 * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and
137 jsr166 1.8 * {@link #removeLastOccurrence removeLastOccurrence}.
138     *
139     * <p>Unlike the {@link List} interface, this interface does not
140     * provide support for indexed access to elements.
141 dl 1.1 *
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 dl 1.3 *
150 dl 1.1 * <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}/../guide/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 jsr166 1.8 * 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 NullPointerException if the specified element is null and this
176     * deque does not permit null elements
177     * @throws ClassCastException if the class of the specified element
178     * prevents it from being added to this deque
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     * @param e the element to add
191     * @throws IllegalStateException if the element cannot be added at this
192     * time due to capacity restrictions
193     * @throws NullPointerException if the specified element is null and this
194     * deque does not permit null elements
195     * @throws ClassCastException if the class of the specified element
196     * prevents it from being added to this deque
197     * @throws IllegalArgumentException if some property of the specified
198     * element prevents it from being added to this deque
199     */
200     void addLast(E e);
201    
202     /**
203 dl 1.3 * Inserts the specified element at the front of this deque unless it would
204 dl 1.1 * violate capacity restrictions. When using a capacity-restricted deque,
205 jsr166 1.8 * this method is generally preferable to the {@link #addFirst} method,
206     * which can fail to insert an element only by throwing an exception.
207 dl 1.1 *
208 jsr166 1.8 * @param e the element to add
209 dl 1.1 * @return <tt>true</tt> if it was possible to insert the element,
210 jsr166 1.8 * else <tt>false</tt>
211 dl 1.3 * @throws NullPointerException if the specified element is null and this
212 jsr166 1.8 * deque does not permit null elements
213     * @throws ClassCastException if the class of the specified element
214     * prevents it from being added to this deque
215     * @throws IllegalArgumentException if some property of the specified
216     * element prevents it from being added to this deque
217 dl 1.1 */
218     boolean offerFirst(E e);
219    
220     /**
221 dl 1.4 * Inserts the specified element at the end of this deque unless it would
222 dl 1.1 * violate capacity restrictions. When using a capacity-restricted deque,
223 jsr166 1.8 * this method is generally preferable to the {@link #addLast} method,
224     * which can fail to insert an element only by throwing an exception.
225 dl 1.1 *
226 jsr166 1.8 * @param e the element to add
227 dl 1.1 * @return <tt>true</tt> if it was possible to insert the element,
228 jsr166 1.8 * else <tt>false</tt>
229 dl 1.3 * @throws NullPointerException if the specified element is null and this
230 jsr166 1.8 * deque does not permit null elements
231     * @throws ClassCastException if the class of the specified element
232     * prevents it from being added to this deque
233     * @throws IllegalArgumentException if some property of the specified
234     * element prevents it from being added to this deque
235 dl 1.1 */
236     boolean offerLast(E e);
237    
238     /**
239 jsr166 1.8 * Retrieves and removes the first element of this deque. This method
240     * differs from {@link #pollFirst} only in that it throws an exception
241     * if this deque is empty.
242 dl 1.1 *
243 jsr166 1.8 * @return the head of this deque
244     * @throws NoSuchElementException if this deque is empty
245 dl 1.1 */
246 jsr166 1.8 E removeFirst();
247 dl 1.1
248     /**
249 jsr166 1.8 * Retrieves and removes the last element of this deque. This method
250     * differs from {@link #pollLast} only in that it throws an exception if
251     * this deque is empty.
252 dl 1.1 *
253 jsr166 1.8 * @return the tail of this deque
254     * @throws NoSuchElementException if this deque is empty
255 dl 1.1 */
256 jsr166 1.8 E removeLast();
257 dl 1.1
258     /**
259 jsr166 1.8 * Retrieves and removes the first element of this deque,
260     * or returns <tt>null</tt> if this deque is empty.
261 dl 1.1 *
262 jsr166 1.8 * @return the head of this deque, or <tt>null</tt> if this deque is empty
263 dl 1.1 */
264     E pollFirst();
265    
266     /**
267 jsr166 1.8 * Retrieves and removes the last element of this deque,
268     * or returns <tt>null</tt> if this deque is empty.
269 dl 1.1 *
270 jsr166 1.8 * @return the tail of this deque, or <tt>null</tt> if this deque is empty
271 dl 1.1 */
272     E pollLast();
273    
274     /**
275 jsr166 1.8 * Retrieves, but does not remove, the first element of this deque.
276     * This method differs from {@link #peekFirst} only in that it throws an
277 dl 1.1 * exception if this deque is empty.
278     *
279 jsr166 1.8 * @return the head of this deque
280 dl 1.1 * @throws NoSuchElementException if this deque is empty
281     */
282 jsr166 1.8 E getFirst();
283 dl 1.1
284     /**
285 jsr166 1.8 * Retrieves, but does not remove, the last element of this deque.
286     * This method differs from {@link #peekLast} only in that it throws an
287 dl 1.1 * exception if this deque is empty.
288     *
289 jsr166 1.8 * @return the tail of this deque
290 dl 1.1 * @throws NoSuchElementException if this deque is empty
291     */
292 jsr166 1.8 E getLast();
293 dl 1.1
294     /**
295     * Retrieves, but does not remove, the first element of this deque,
296 jsr166 1.8 * or returns <tt>null</tt> if this deque is empty.
297 dl 1.1 *
298 jsr166 1.8 * @return the head of this deque, or <tt>null</tt> if this deque is empty
299 dl 1.1 */
300     E peekFirst();
301    
302     /**
303     * Retrieves, but does not remove, the last element of this deque,
304 jsr166 1.8 * or returns <tt>null</tt> if this deque is empty.
305 dl 1.1 *
306 jsr166 1.8 * @return the tail of this deque, or <tt>null</tt> if this deque is empty
307 dl 1.1 */
308     E peekLast();
309    
310     /**
311 jsr166 1.8 * Removes the first occurrence of the specified element from this deque.
312     * If the deque does not contain the element, it is unchanged.
313     * More formally, removes the first element <tt>e</tt> such that
314     * <tt>(o==null ? e==null : o.equals(e))</tt> (if such an element exists).
315     * Returns true if this deque contained the specified element (or
316     * equivalently, if this deque changed as a result of the call).
317 dl 1.1 *
318 dl 1.3 * @param o element to be removed from this deque, if present
319 jsr166 1.8 * @return <tt>true</tt> if an element was removed as a result of this call
320 dl 1.4 * @throws NullPointerException if the specified element is null and this
321 jsr166 1.8 * deque does not permit null elements (optional)
322     * @throws ClassCastException if the class of the specified element
323     * is incompatible with this collection (optional)
324 dl 1.1 */
325 dl 1.3 boolean removeFirstOccurrence(Object o);
326 dl 1.1
327     /**
328 jsr166 1.8 * Removes the last occurrence of the specified element from this deque.
329     * If the deque does not contain the element, it is unchanged.
330     * More formally, removes the last element <tt>e</tt> such that
331     * <tt>(o==null ? e==null : o.equals(e))</tt> (if such an element exists).
332     * Returns true if this deque contained the specified element (or
333     * equivalently, if this deque changed as a result of the call).
334 dl 1.1 *
335 dl 1.3 * @param o element to be removed from this deque, if present
336 jsr166 1.8 * @return <tt>true</tt> if an element was removed as a result of this call
337 dl 1.4 * @throws NullPointerException if the specified element is null and this
338 jsr166 1.8 * deque does not permit null elements (optional)
339     * @throws ClassCastException if the class of the specified element
340     * is incompatible with this collection (optional)
341 dl 1.1 */
342 dl 1.3 boolean removeLastOccurrence(Object o);
343 dl 1.1
344 jsr166 1.8 // *** Queue methods ***
345 dl 1.1
346 jsr166 1.8 /**
347     * Inserts the specified element into the queue represented by this deque
348     * (in other words, at the tail of this deque) if it is possible to do so
349     * immediately without violating capacity restrictions, returning
350     * <tt>true</tt> upon success and throwing an
351     * <tt>IllegalStateException</tt> if no space is currently available.
352     * When using a capacity-restricted deque, it is generally preferable to
353     * use {@link #offer(Object) offer}.
354     *
355     * <p>This method is equivalent to {@link #addLast(Object) addLast}.
356     *
357     * @param e the element to add
358     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
359     * @throws IllegalStateException if the element cannot be added at this
360     * time due to capacity restrictions
361     * @throws NullPointerException if the specified element is null and this
362     * deque does not permit null elements
363     * @throws ClassCastException if the class of the specified element
364     * prevents it from being added to this deque
365     * @throws IllegalArgumentException if some property of the specified
366     * element prevents it from being added to this deque
367     */
368     boolean add(E e);
369 dl 1.1
370     /**
371     * Inserts the specified element into the queue represented by this deque
372 jsr166 1.8 * (in other words, at the tail of this deque) if it is possible to do so
373     * immediately without violating capacity restrictions, returning
374     * <tt>true</tt> upon success and <tt>false</tt> if no space is currently
375     * available. When using a capacity-restricted deque, this method is
376     * generally preferable to the {@link #add} method, which can fail to
377     * insert an element only by throwing an exception.
378 dl 1.1 *
379     * <p>This method is equivalent to {@link #offerLast}.
380     *
381 jsr166 1.8 * @param e the element to add
382     * @return <tt>true</tt> if the element was added to this deque, else
383     * <tt>false</tt>
384 dl 1.3 * @throws NullPointerException if the specified element is null and this
385 jsr166 1.8 * deque does not permit null elements
386     * @throws ClassCastException if the class of the specified element
387     * prevents it from being added to this deque
388     * @throws IllegalArgumentException if some property of the specified
389     * element prevents it from being added to this deque
390 dl 1.1 */
391     boolean offer(E e);
392    
393     /**
394 jsr166 1.8 * Retrieves and removes the head of the queue represented by this deque
395     * (in other words, the first element of this deque).
396     * This method differs from {@link #poll} only in that it throws an
397     * exception if this deque is empty.
398 dl 1.1 *
399 jsr166 1.8 * <p>This method is equivalent to {@link #removeFirst()}.
400 dl 1.1 *
401 jsr166 1.8 * @return the head of the queue represented by this deque
402     * @throws NoSuchElementException if this deque is empty
403 dl 1.1 */
404 jsr166 1.8 E remove();
405 dl 1.1
406     /**
407 jsr166 1.8 * Retrieves and removes the head of the queue represented by this deque
408     * (in other words, the first element of this deque), or returns
409     * <tt>null</tt> if this deque is empty.
410 dl 1.1 *
411     * <p>This method is equivalent to {@link #pollFirst()}.
412     *
413     * @return the first element of this deque, or <tt>null</tt> if
414 jsr166 1.8 * this deque is empty
415 dl 1.1 */
416     E poll();
417    
418     /**
419 jsr166 1.8 * Retrieves, but does not remove, the head of the queue represented by
420     * this deque (in other words, the first element of this deque).
421     * This method differs from {@link #peek} only in that it throws an
422     * exception if this deque is empty.
423 dl 1.1 *
424 jsr166 1.8 * <p>This method is equivalent to {@link #getFirst()}.
425 dl 1.1 *
426     * @return the head of the queue represented by this deque
427     * @throws NoSuchElementException if this deque is empty
428     */
429 jsr166 1.8 E element();
430 dl 1.1
431     /**
432     * Retrieves, but does not remove, the head of the queue represented by
433 jsr166 1.8 * this deque (in other words, the first element of this deque), or
434     * returns <tt>null</tt> if this deque is empty.
435 dl 1.1 *
436 dl 1.3 * <p>This method is equivalent to {@link #peekFirst()}.
437 dl 1.1 *
438     * @return the head of the queue represented by this deque, or
439 jsr166 1.8 * <tt>null</tt> if this deque is empty
440 dl 1.1 */
441     E peek();
442    
443    
444     // *** Stack methods ***
445    
446     /**
447 jsr166 1.8 * Pushes an element onto the stack represented by this deque (in other
448     * words, at the head of this deque) if it is possible to do so
449     * immediately without violating capacity restrictions, returning
450     * <tt>true</tt> upon success and throwing an
451     * <tt>IllegalStateException</tt> if no space is currently available.
452 dl 1.1 *
453     * <p>This method is equivalent to {@link #addFirst}.
454     *
455 dl 1.3 * @param e the element to push
456 jsr166 1.8 * @throws IllegalStateException if the element cannot be added at this
457     * time due to capacity restrictions
458 dl 1.3 * @throws NullPointerException if the specified element is null and this
459 jsr166 1.8 * deque does not permit null elements
460     * @throws ClassCastException if the class of the specified element
461     * prevents it from being added to this deque
462     * @throws IllegalArgumentException if some property of the specified
463     * element prevents it from being added to this deque
464 dl 1.1 */
465     void push(E e);
466    
467     /**
468     * Pops an element from the stack represented by this deque. In other
469 dl 1.2 * words, removes and returns the first element of this deque.
470 dl 1.1 *
471     * <p>This method is equivalent to {@link #removeFirst()}.
472     *
473     * @return the element at the front of this deque (which is the top
474 jsr166 1.8 * of the stack represented by this deque)
475 dl 1.1 * @throws NoSuchElementException if this deque is empty
476     */
477     E pop();
478    
479    
480 jsr166 1.8 // *** Collection methods ***
481    
482     /**
483     * Removes the first occurrence of the specified element from this deque.
484     * If the deque does not contain the element, it is unchanged.
485     * More formally, removes the first element <tt>e</tt> such that
486     * <tt>(o==null ? e==null : o.equals(e))</tt> (if such an element exists).
487     * Returns true if this deque contained the specified element (or
488     * equivalently, if this deque changed as a result of the call).
489     *
490     * <p>This method is equivalent to {@link #removeFirstOccurrence}.
491     *
492     * @param o element to be removed from this deque, if present
493     * @return <tt>true</tt> if an element was removed as a result of this call
494     * @throws NullPointerException if the specified element is null and this
495     * deque does not permit null elements (optional)
496     * @throws ClassCastException if the class of the specified element
497     * is incompatible with this collection (optional)
498     */
499     boolean remove(Object o);
500    
501     /**
502     * Returns <tt>true</tt> if this deque contains the specified element.
503     * More formally, returns <tt>true</tt> if and only if this deque
504     * contains at least one element <tt>e</tt> such that <tt>(o==null ?
505     * e==null : o.equals(e))</tt>.
506     *
507     * @param o element whose presence in this deque is to be tested
508     * @return <tt>true</tt> if this deque contains the specified element
509     * @throws ClassCastException if the type of the specified element
510     * is incompatible with this deque (optional)
511     * @throws NullPointerException if the specified element is null and this
512     * deque does not permit null elements (optional)
513     */
514     boolean contains(Object o);
515    
516     /**
517     * Returns the number of elements in this deque.
518     *
519     * @return the number of elements in this deque
520     */
521     public int size();
522 dl 1.1
523     /**
524     * Returns an iterator over the elements in this deque. The elements
525     * will be ordered from first (head) to last (tail).
526 dl 1.3 *
527 dl 1.1 * @return an <tt>Iterator</tt> over the elements in this deque
528     */
529     Iterator<E> iterator();
530     }