ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jdk7/java/util/Deque.java
Revision: 1.3
Committed: Sat Jul 20 19:33:38 2013 UTC (10 years, 8 months ago) by jsr166
Branch: MAIN
CVS Tags: HEAD
Changes since 1.2: +25 -21 lines
Log Message:
sync javadoc fixes from src/main

File Contents

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