KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > Deque


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