ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/Deque.java
Revision: 1.11
Committed: Tue May 17 16:00:48 2005 UTC (18 years, 11 months ago) by jsr166
Branch: MAIN
Changes since 1.10: +4 -4 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 jsr166 1.9 * @throws ClassCastException if the class of the specified element
176     * prevents it from being added to this deque
177 jsr166 1.8 * @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     * @param e the element to add
191     * @throws IllegalStateException if the element cannot be added at this
192     * time due to capacity restrictions
193 jsr166 1.9 * @throws ClassCastException if the class of the specified element
194     * prevents it from being added to this deque
195 jsr166 1.8 * @throws NullPointerException if the specified element is null and this
196     * deque does not permit null elements
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 jsr166 1.11 * @return <tt>true</tt> if the element was added to this deque, else
210     * <tt>false</tt>
211 jsr166 1.9 * @throws ClassCastException if the class of the specified element
212     * prevents it from being added to this deque
213 dl 1.3 * @throws NullPointerException if the specified element is null and this
214 jsr166 1.8 * deque does not permit null elements
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 jsr166 1.11 * @return <tt>true</tt> if the element was added to this deque, else
228     * <tt>false</tt>
229 jsr166 1.9 * @throws ClassCastException if the class of the specified element
230     * prevents it from being added to this deque
231 dl 1.3 * @throws NullPointerException if the specified element is null and this
232 jsr166 1.8 * deque does not permit null elements
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 jsr166 1.9 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
315     * (if such an element exists).
316 jsr166 1.8 * Returns true if this deque contained the specified element (or
317     * equivalently, if this deque changed as a result of the call).
318 dl 1.1 *
319 dl 1.3 * @param o element to be removed from this deque, if present
320 jsr166 1.8 * @return <tt>true</tt> if an element was removed as a result of this call
321 jsr166 1.9 * @throws ClassCastException if the class of the specified element
322     * is incompatible with this deque (optional)
323 dl 1.4 * @throws NullPointerException if the specified element is null and this
324 jsr166 1.8 * deque does not permit null elements (optional)
325 dl 1.1 */
326 dl 1.3 boolean removeFirstOccurrence(Object o);
327 dl 1.1
328     /**
329 jsr166 1.8 * Removes the last occurrence of the specified element from this deque.
330     * If the deque does not contain the element, it is unchanged.
331     * More formally, removes the last element <tt>e</tt> such that
332 jsr166 1.9 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
333     * (if such an element exists).
334 jsr166 1.8 * Returns true if this deque contained the specified element (or
335     * equivalently, if this deque changed as a result of the call).
336 dl 1.1 *
337 dl 1.3 * @param o element to be removed from this deque, if present
338 jsr166 1.8 * @return <tt>true</tt> if an element was removed as a result of this call
339 jsr166 1.9 * @throws ClassCastException if the class of the specified element
340     * is incompatible with this deque (optional)
341 dl 1.4 * @throws NullPointerException if the specified element is null and this
342 jsr166 1.8 * deque does not permit null elements (optional)
343 dl 1.1 */
344 dl 1.3 boolean removeLastOccurrence(Object o);
345 dl 1.1
346 jsr166 1.8 // *** Queue methods ***
347 dl 1.1
348 jsr166 1.8 /**
349     * Inserts the specified element into the queue represented by this deque
350     * (in other words, at the tail of this deque) if it is possible to do so
351     * immediately without violating capacity restrictions, returning
352     * <tt>true</tt> upon success and throwing an
353     * <tt>IllegalStateException</tt> if no space is currently available.
354     * When using a capacity-restricted deque, it is generally preferable to
355     * use {@link #offer(Object) offer}.
356     *
357     * <p>This method is equivalent to {@link #addLast(Object) addLast}.
358     *
359     * @param e the element to add
360     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
361     * @throws IllegalStateException if the element cannot be added at this
362     * time due to capacity restrictions
363 jsr166 1.9 * @throws ClassCastException if the class of the specified element
364     * prevents it from being added to this deque
365 jsr166 1.8 * @throws NullPointerException if the specified element is null and this
366     * deque does not permit null elements
367     * @throws IllegalArgumentException if some property of the specified
368     * element prevents it from being added to this deque
369     */
370     boolean add(E e);
371 dl 1.1
372     /**
373     * Inserts the specified element into the queue represented by this deque
374 jsr166 1.8 * (in other words, at the tail of this deque) if it is possible to do so
375     * immediately without violating capacity restrictions, returning
376     * <tt>true</tt> upon success and <tt>false</tt> if no space is currently
377     * available. When using a capacity-restricted deque, this method is
378     * generally preferable to the {@link #add} method, which can fail to
379     * insert an element only by throwing an exception.
380 dl 1.1 *
381     * <p>This method is equivalent to {@link #offerLast}.
382     *
383 jsr166 1.8 * @param e the element to add
384     * @return <tt>true</tt> if the element was added to this deque, else
385     * <tt>false</tt>
386 jsr166 1.9 * @throws ClassCastException if the class of the specified element
387     * prevents it from being added to this deque
388 dl 1.3 * @throws NullPointerException if the specified element is null and this
389 jsr166 1.8 * deque does not permit null elements
390     * @throws IllegalArgumentException if some property of the specified
391     * element prevents it from being added to this deque
392 dl 1.1 */
393     boolean offer(E e);
394    
395     /**
396 jsr166 1.8 * Retrieves and removes the head of the queue represented by this deque
397     * (in other words, the first element of this deque).
398     * This method differs from {@link #poll} only in that it throws an
399     * exception if this deque is empty.
400 dl 1.1 *
401 jsr166 1.8 * <p>This method is equivalent to {@link #removeFirst()}.
402 dl 1.1 *
403 jsr166 1.8 * @return the head of the queue represented by this deque
404     * @throws NoSuchElementException if this deque is empty
405 dl 1.1 */
406 jsr166 1.8 E remove();
407 dl 1.1
408     /**
409 jsr166 1.8 * Retrieves and removes the head of the queue represented by this deque
410     * (in other words, the first element of this deque), or returns
411     * <tt>null</tt> if this deque is empty.
412 dl 1.1 *
413     * <p>This method is equivalent to {@link #pollFirst()}.
414     *
415     * @return the first element of this deque, or <tt>null</tt> if
416 jsr166 1.8 * this deque is empty
417 dl 1.1 */
418     E poll();
419    
420     /**
421 jsr166 1.8 * Retrieves, but does not remove, the head of the queue represented by
422     * this deque (in other words, the first element of this deque).
423     * This method differs from {@link #peek} only in that it throws an
424     * exception if this deque is empty.
425 dl 1.1 *
426 jsr166 1.8 * <p>This method is equivalent to {@link #getFirst()}.
427 dl 1.1 *
428     * @return the head of the queue represented by this deque
429     * @throws NoSuchElementException if this deque is empty
430     */
431 jsr166 1.8 E element();
432 dl 1.1
433     /**
434     * Retrieves, but does not remove, the head of the queue represented by
435 jsr166 1.8 * this deque (in other words, the first element of this deque), or
436     * returns <tt>null</tt> if this deque is empty.
437 dl 1.1 *
438 dl 1.3 * <p>This method is equivalent to {@link #peekFirst()}.
439 dl 1.1 *
440     * @return the head of the queue represented by this deque, or
441 jsr166 1.8 * <tt>null</tt> if this deque is empty
442 dl 1.1 */
443     E peek();
444    
445    
446     // *** Stack methods ***
447    
448     /**
449 jsr166 1.8 * Pushes an element onto the stack represented by this deque (in other
450     * words, at the head of this deque) if it is possible to do so
451     * immediately without violating capacity restrictions, returning
452     * <tt>true</tt> upon success and throwing an
453     * <tt>IllegalStateException</tt> if no space is currently available.
454 dl 1.1 *
455     * <p>This method is equivalent to {@link #addFirst}.
456     *
457 dl 1.3 * @param e the element to push
458 jsr166 1.8 * @throws IllegalStateException if the element cannot be added at this
459     * time due to capacity restrictions
460 jsr166 1.9 * @throws ClassCastException if the class of the specified element
461     * prevents it from being added to this deque
462 dl 1.3 * @throws NullPointerException if the specified element is null and this
463 jsr166 1.8 * deque does not permit null elements
464     * @throws IllegalArgumentException if some property of the specified
465     * element prevents it from being added to this deque
466 dl 1.1 */
467     void push(E e);
468    
469     /**
470     * Pops an element from the stack represented by this deque. In other
471 dl 1.2 * words, removes and returns the first element of this deque.
472 dl 1.1 *
473     * <p>This method is equivalent to {@link #removeFirst()}.
474     *
475     * @return the element at the front of this deque (which is the top
476 jsr166 1.8 * of the stack represented by this deque)
477 dl 1.1 * @throws NoSuchElementException if this deque is empty
478     */
479     E pop();
480    
481    
482 jsr166 1.8 // *** Collection methods ***
483    
484     /**
485     * Removes the first occurrence of the specified element from this deque.
486     * If the deque does not contain the element, it is unchanged.
487     * More formally, removes the first element <tt>e</tt> such that
488 jsr166 1.9 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
489     * (if such an element exists).
490 jsr166 1.8 * Returns true if this deque contained the specified element (or
491     * equivalently, if this deque changed as a result of the call).
492     *
493     * <p>This method is equivalent to {@link #removeFirstOccurrence}.
494     *
495     * @param o element to be removed from this deque, if present
496     * @return <tt>true</tt> if an element was removed as a result of this call
497 jsr166 1.9 * @throws ClassCastException if the class of the specified element
498     * is incompatible with this deque (optional)
499 jsr166 1.8 * @throws NullPointerException if the specified element is null and this
500     * deque does not permit null elements (optional)
501     */
502     boolean remove(Object o);
503    
504     /**
505     * Returns <tt>true</tt> if this deque contains the specified element.
506 jsr166 1.9 * More formally, returns <tt>true</tt> if and only if this deque contains
507     * at least one element <tt>e</tt> such that
508     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
509 jsr166 1.8 *
510     * @param o element whose presence in this deque is to be tested
511     * @return <tt>true</tt> if this deque contains the specified element
512     * @throws ClassCastException if the type of the specified element
513     * is incompatible with this deque (optional)
514     * @throws NullPointerException if the specified element is null and this
515     * deque does not permit null elements (optional)
516     */
517     boolean contains(Object o);
518    
519     /**
520     * Returns the number of elements in this deque.
521     *
522     * @return the number of elements in this deque
523     */
524     public int size();
525 dl 1.1
526     /**
527 jsr166 1.10 * Returns an iterator over the elements in this deque in proper sequence.
528     * The elements will be returned in order from first (head) to last (tail).
529 dl 1.3 *
530 jsr166 1.10 * @return an iterator over the elements in this deque in proper sequence
531 dl 1.1 */
532     Iterator<E> iterator();
533     }