ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/Deque.java

Comparing jsr166/src/main/java/util/Deque.java (file contents):
Revision 1.15 by jsr166, Mon Jul 18 19:14:17 2005 UTC vs.
Revision 1.25 by jsr166, Thu May 2 06:38:33 2013 UTC

#	Line 1 | Line 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
4	>	* at http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package java.util;
8	–	import java.util.*; // for javadoc (till 6280605 is fixed)
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>
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.
#	Line 19 | Line 18 | import java.util.*; // for javadoc (till
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
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	<	* <tt>Deque</tt> implementations; in most implementations, insert
24	>	* {@code Deque} implementations; in most implementations, insert
25		* operations cannot fail.
26		*
27		* <p>The twelve methods described above are summarized in the
#	Line 30 | Line 29 | import java.util.*; // for javadoc (till
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>
#	Line 68 | Line 68 | import java.util.*; // for javadoc (till
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:
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><tt>Queue</tt> Method</b></td>
79	<	*    <td ALIGN=CENTER> <b>Equivalent <tt>Deque</tt> Method</b></td>
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>
#	Line 107 | Line 108 | import java.util.*; // for javadoc (till
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	<	* <tt>Deque</tt> methods as indicated in the table below:
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 <tt>Deque</tt> 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>
#	Line 140 | Line 142 | import java.util.*; // for javadoc (till
142		* <p>Unlike the {@link List} interface, this interface does not
143		* provide support for indexed access to elements.
144		*
145	<	* <p>While <tt>Deque</tt> implementations are not strictly required
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 <tt>Deque</tt> implementations
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	<	* <tt>null</tt> is used as a special return value by various methods
150	>	* {@code null} is used as a special return value by various methods
151		* to indicated that the deque is empty.
152		*
153	<	* <p><tt>Deque</tt> implementations generally do not define
154	<	* element-based versions of the <tt>equals</tt> and <tt>hashCode</tt>
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	<	* <tt>Object</tt>.
156	>	* {@code Object}.
157		*
158		* <p>This interface is a member of the <a
159	<	* href="{@docRoot}/../guide/collections/index.html"> Java Collections
159	>	* href="{@docRoot}/../technotes/guides/collections/index.html"> Java Collections
160		* Framework</a>.
161		*
162		* @author Doug Lea
#	Line 162 | Line 164 | import java.util.*; // for javadoc (till
164		* @since  1.6
165		* @param <E> the type of elements held in this collection
166		*/
165	–
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	<	* When using a capacity-restricted deque, it is generally preferable to
172	<	* use method {@link #offerFirst}.
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
#	Line 184 | Line 186 | public interface Deque<E> extends Queue<
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	<	* When using a capacity-restricted deque, it is generally preferable to
191	<	* use method {@link #offerLast}.
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		*
#	Line 209 | Line 212 | public interface Deque<E> extends Queue<
212		* which can fail to insert an element only by throwing an exception.
213		*
214		* @param e the element to add
215	<	* @return <tt>true</tt> if the element was added to this deque, else
216	<	*         <tt>false</tt>
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
#	Line 227 | Line 230 | public interface Deque<E> extends Queue<
230		* which can fail to insert an element only by throwing an exception.
231		*
232		* @param e the element to add
233	<	* @return <tt>true</tt> if the element was added to this deque, else
234	<	*         <tt>false</tt>
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
#	Line 260 | Line 263 | public interface Deque<E> extends Queue<
263
264		/**
265		* Retrieves and removes the first element of this deque,
266	<	* or returns <tt>null</tt> if this deque is empty.
266	>	* or returns {@code null} if this deque is empty.
267		*
268	<	* @return the head of this deque, or <tt>null</tt> if this deque is empty
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 <tt>null</tt> if this deque is empty.
274	>	* or returns {@code null} if this deque is empty.
275		*
276	<	* @return the tail of this deque, or <tt>null</tt> if this deque is empty
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	<	*
282	>	*
283		* This method differs from {@link #peekFirst peekFirst} only in that it
284		* throws an exception if this deque is empty.
285		*
#	Line 297 | Line 300 | public interface Deque<E> extends Queue<
300
301		/**
302		* Retrieves, but does not remove, the first element of this deque,
303	<	* or returns <tt>null</tt> if this deque is empty.
303	>	* or returns {@code null} if this deque is empty.
304		*
305	<	* @return the head of this deque, or <tt>null</tt> if this deque is empty
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 <tt>null</tt> if this deque is empty.
311	>	* or returns {@code null} if this deque is empty.
312		*
313	<	* @return the tail of this deque, or <tt>null</tt> if this deque is empty
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 <tt>e</tt> such that
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 <tt>true</tt> if this deque contained the specified element
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 <tt>true</tt> if an element was removed as a result of this call
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
#	Line 332 | Line 335 | public interface Deque<E> extends Queue<
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 <tt>e</tt> such that
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 <tt>true</tt> if this deque contained the specified element
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 <tt>true</tt> if an element was removed as a result of this call
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
#	Line 353 | Line 356 | public interface Deque<E> extends Queue<
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	<	* <tt>true</tt> upon success and throwing an
360	<	* <tt>IllegalStateException</tt> if no space is currently available.
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 <tt>true</tt> (as specified by {@link Collection#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
#	Line 377 | Line 380 | public interface Deque<E> extends Queue<
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	<	* <tt>true</tt> upon success and <tt>false</tt> if no space is currently
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.
#	Line 385 | Line 388 | public interface Deque<E> extends Queue<
388		* <p>This method is equivalent to {@link #offerLast}.
389		*
390		* @param e the element to add
391	<	* @return <tt>true</tt> if the element was added to this deque, else
392	<	*         <tt>false</tt>
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
#	Line 412 | Line 415 | public interface Deque<E> extends Queue<
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	<	* <tt>null</tt> if this deque is empty.
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 <tt>null</tt> if
422	>	* @return the first element of this deque, or {@code null} if
423		*         this deque is empty
424		*/
425		E poll();
#	Line 437 | Line 440 | public interface Deque<E> extends Queue<
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 <tt>null</tt> if this deque is empty.
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	<	*         <tt>null</tt> if this deque is empty
448	>	*         {@code null} if this deque is empty
449		*/
450		E peek();
451
#	Line 452 | Line 455 | public interface Deque<E> extends Queue<
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, returning
459	<	* <tt>true</tt> upon success and throwing an
457	<	* <tt>IllegalStateException</tt> if no space is currently available.
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		*
#	Line 488 | Line 490 | public interface Deque<E> extends Queue<
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 <tt>e</tt> such that
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 <tt>true</tt> if this deque contained the specified element
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}.
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 <tt>true</tt> if an element was removed as a result of this call
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
#	Line 506 | Line 508 | public interface Deque<E> extends Queue<
508		boolean remove(Object o);
509
510		/**
511	<	* Returns <tt>true</tt> if this deque contains the specified element.
512	<	* More formally, returns <tt>true</tt> if and only if this deque contains
513	<	* at least one element <tt>e</tt> such that
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 <tt>true</tt> if this deque contains the specified element
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
#	Line 534 | Line 536 | public interface Deque<E> extends Queue<
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		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines