[cvs] / jsr166 / src / main / java / util / Deque.java Repository:
ViewVC logotype

Annotation of /jsr166/src/main/java/util/Deque.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.7 - (view) (download)

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 :     * <td ALIGN=CENTER><em>Returns special value</em></td>
41 :     * <td ALIGN=CENTER><em>Throws exception</em></td>
42 :     * <td ALIGN=CENTER><em>Returns special value</em></td>
43 :     * </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 :     * <td>{@link java.util.Queue#offer offer(e)}</td>
81 :     * <td>{@link #offerLast offerLast(e)}</td>
82 : jsr166 1.5 * </tr>
83 :     * <tr>
84 : dl 1.1 * <td>{@link java.util.Queue#add add(e)}</td>
85 :     * <td>{@link #addLast addLast(e)}</td>
86 : jsr166 1.5 * </tr>
87 :     * <tr>
88 : dl 1.1 * <td>{@link java.util.Queue#poll poll()}</td>
89 :     * <td>{@link #pollFirst pollFirst()}</td>
90 : jsr166 1.5 * </tr>
91 :     * <tr>
92 : dl 1.1 * <td>{@link java.util.Queue#remove remove()}</td>
93 :     * <td>{@link #removeFirst removeFirst()}</td>
94 : jsr166 1.5 * </tr>
95 :     * <tr>
96 : dl 1.1 * <td>{@link java.util.Queue#peek peek()}</td>
97 :     * <td>{@link #peek peekFirst()}</td>
98 : jsr166 1.5 * </tr>
99 :     * <tr>
100 : dl 1.1 * <td>{@link java.util.Queue#element element()}</td>
101 :     * <td>{@link #getFirst getFirst()}</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 :     * {@link #removeLastOccurrence removeLastOccurrence}. Unlike the
138 :     * {@link List} interface, this interface does not provide support for
139 :     * indexed access to elements.
140 :     *
141 :     * <p>While <tt>Deque</tt> implementations are not strictly required
142 :     * to prohibit the insertion of null elements, they are strongly
143 :     * encouraged to do so. Users of any <tt>Deque</tt> implementations
144 :     * that do allow null elements are strongly encouraged <i>not</i> to
145 :     * take advantage of the ability to insert nulls. This is so because
146 :     * <tt>null</tt> is used as a special return value by various methods
147 :     * to indicated that the deque is empty.
148 : dl 1.3 *
149 : dl 1.1 * <p><tt>Deque</tt> implementations generally do not define
150 :     * element-based versions of the <tt>equals</tt> and <tt>hashCode</tt>
151 :     * methods, but instead inherit the identity-based versions from class
152 :     * <tt>Object</tt>.
153 :     *
154 :     * <p>This interface is a member of the <a
155 :     * href="{@docRoot}/../guide/collections/index.html"> Java Collections
156 :     * Framework</a>.
157 :     *
158 :     * @author Doug Lea
159 :     * @author Josh Bloch
160 :     * @since 1.6
161 :     * @param <E> the type of elements held in this collection
162 :     */
163 :    
164 :     public interface Deque<E> extends Queue<E> {
165 :     /**
166 : dl 1.3 * Inserts the specified element at the front of this deque unless it would
167 : dl 1.1 * violate capacity restrictions. When using a capacity-restricted deque,
168 :     * this method is generally preferable to method <tt>addFirst</tt>, which
169 :     * can fail to insert an element only by throwing an exception.
170 :     *
171 :     * @param e the element to insert
172 :     * @return <tt>true</tt> if it was possible to insert the element,
173 :     * else <tt>false</tt>
174 : dl 1.3 * @throws NullPointerException if the specified element is null and this
175 : dl 1.1 * deque does not permit null elements
176 :     */
177 :     boolean offerFirst(E e);
178 :    
179 :     /**
180 : dl 1.4 * Inserts the specified element at the end of this deque unless it would
181 : dl 1.1 * violate capacity restrictions. When using a capacity-restricted deque,
182 :     * this method is generally preferable to method <tt>addLast</tt> which
183 :     * can fail to insert an element only by throwing an exception.
184 :     *
185 :     * @param e the element to insert
186 :     * @return <tt>true</tt> if it was possible to insert the element,
187 :     * else <tt>false</tt>
188 : dl 1.3 * @throws NullPointerException if the specified element is null and this
189 : dl 1.1 * deque does not permit null elements
190 :     */
191 :     boolean offerLast(E e);
192 :    
193 :     /**
194 : dl 1.3 * Inserts the specified element at the front of this deque unless it
195 : dl 1.1 * would violate capacity restrictions.
196 :     *
197 :     * @param e the element to insert
198 :     * @throws IllegalStateException if it was not possible to insert
199 :     * the element due to capacity restrictions
200 : dl 1.3 * @throws NullPointerException if the specified element is null and this
201 : dl 1.1 * deque does not permit null elements
202 :     */
203 :     void addFirst(E e);
204 :    
205 :     /**
206 : dl 1.4 * Inserts the specified element at the end of this deque unless it would
207 : dl 1.1 * violate capacity restrictions.
208 :     *
209 :     * @param e the element to insert
210 :     * @throws IllegalStateException if it was not possible to insert
211 :     * the element due to capacity restrictions
212 : dl 1.3 * @throws NullPointerException if the specified element is null and this
213 : dl 1.1 * deque does not permit null elements
214 :     */
215 :     void addLast(E e);
216 :    
217 :     /**
218 :     * Retrieves and removes the first element of this deque, or
219 :     * <tt>null</tt> if this deque is empty.
220 :     *
221 :     * @return the first element of this deque, or <tt>null</tt> if
222 :     * this deque is empty
223 :     */
224 :     E pollFirst();
225 :    
226 :     /**
227 :     * Retrieves and removes the last element of this deque, or
228 :     * <tt>null</tt> if this deque is empty.
229 :     *
230 :     * @return the last element of this deque, or <tt>null</tt> if
231 :     * this deque is empty
232 :     */
233 :     E pollLast();
234 :    
235 :     /**
236 : jsr166 1.5 * Retrieves and removes the first element of this deque. This method
237 : jsr166 1.6 * differs from the {@link #pollFirst} method only in that it throws an
238 : dl 1.1 * exception if this deque is empty.
239 :     *
240 :     * @return the first element of this deque
241 :     * @throws NoSuchElementException if this deque is empty
242 :     */
243 :     E removeFirst();
244 :    
245 :     /**
246 :     * Retrieves and removes the last element of this deque. This method
247 : jsr166 1.6 * differs from the {@link #pollLast} method only in that it throws an
248 : dl 1.1 * exception if this deque is empty.
249 :     *
250 :     * @return the last element of this deque
251 :     * @throws NoSuchElementException if this deque is empty
252 :     */
253 :     E removeLast();
254 :    
255 :     /**
256 :     * Retrieves, but does not remove, the first element of this deque,
257 :     * returning <tt>null</tt> if this deque is empty.
258 :     *
259 :     * @return the first element of this deque, or <tt>null</tt> if
260 :     * this deque is empty
261 :     */
262 :     E peekFirst();
263 :    
264 :     /**
265 :     * Retrieves, but does not remove, the last element of this deque,
266 :     * returning <tt>null</tt> if this deque is empty.
267 :     *
268 :     * @return the last element of this deque, or <tt>null</tt> if this deque
269 :     * is empty
270 :     */
271 :     E peekLast();
272 :    
273 :     /**
274 :     * Retrieves, but does not remove, the first element of this
275 : jsr166 1.6 * deque. This method differs from the {@link #peekFirst} method only
276 : dl 1.1 * in that it throws an exception if this deque is empty.
277 :     *
278 :     * @return the first element of this deque
279 :     * @throws NoSuchElementException if this deque is empty
280 :     */
281 :     E getFirst();
282 :    
283 :     /**
284 :     * Retrieves, but does not remove, the last element of this
285 : jsr166 1.6 * deque. This method differs from the {@link #peekLast} method only
286 : dl 1.1 * in that it throws an exception if this deque is empty.
287 :     *
288 :     * @return the last element of this deque
289 :     * @throws NoSuchElementException if this deque is empty
290 :     */
291 :     E getLast();
292 :    
293 :     /**
294 :     * Removes the first occurrence of the specified element in this
295 :     * deque. If the deque does not contain the element, it is
296 :     * unchanged. More formally, removes the first element <tt>e</tt>
297 :     * such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
298 :     * such an element exists).
299 :     *
300 : dl 1.3 * @param o element to be removed from this deque, if present
301 : dl 1.1 * @return <tt>true</tt> if the deque contained the specified element
302 : dl 1.4 * @throws NullPointerException if the specified element is null and this
303 :     * deque does not permit null elements
304 : dl 1.1 */
305 : dl 1.3 boolean removeFirstOccurrence(Object o);
306 : dl 1.1
307 :     /**
308 :     * Removes the last occurrence of the specified element in this
309 :     * deque. If the deque does not contain the element, it is
310 :     * unchanged. More formally, removes the last element <tt>e</tt>
311 :     * such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
312 :     * such an element exists).
313 :     *
314 : dl 1.3 * @param o element to be removed from this deque, if present
315 : dl 1.1 * @return <tt>true</tt> if the deque contained the specified element
316 : dl 1.4 * @throws NullPointerException if the specified element is null and this
317 :     * deque does not permit null elements
318 : dl 1.1 */
319 : dl 1.3 boolean removeLastOccurrence(Object o);
320 : dl 1.1
321 :    
322 :     // *** Queue methods ***
323 :    
324 :     /**
325 :     * Inserts the specified element into the queue represented by this deque
326 :     * unless it would violate capacity restrictions. In other words, inserts
327 : dl 1.4 * the specified element at the end of this deque. When using a
328 : dl 1.1 * capacity-restricted deque, this method is generally preferable to the
329 :     * {@link #add} method, which can fail to insert an element only by
330 :     * throwing an exception.
331 :     *
332 :     * <p>This method is equivalent to {@link #offerLast}.
333 :     *
334 :     * @param e the element to insert
335 :     * @return <tt>true</tt> if it was possible to insert the element,
336 :     * else <tt>false</tt>
337 : dl 1.3 * @throws NullPointerException if the specified element is null and this
338 : dl 1.1 * deque does not permit null elements
339 :     */
340 :     boolean offer(E e);
341 :    
342 :     /**
343 :     * Inserts the specified element into the queue represented by this
344 :     * deque unless it would violate capacity restrictions. In other words,
345 : dl 1.3 * inserts the specified element as the last element of this deque.
346 : dl 1.1 *
347 :     * <p>This method is equivalent to {@link #addLast}.
348 :     *
349 :     * @param e the element to insert
350 :     * @return <tt>true</tt> (as per the spec for {@link Collection#add})
351 :     * @throws IllegalStateException if it was not possible to insert
352 :     * the element due to capacity restrictions
353 : dl 1.3 * @throws NullPointerException if the specified element is null and this
354 : dl 1.1 * deque does not permit null elements
355 :     */
356 :     boolean add(E e);
357 :    
358 :     /**
359 :     * Retrieves and removes the head of the queue represented by
360 :     * this deque, or <tt>null</tt> if this deque is empty. In other words,
361 :     * retrieves and removes the first element of this deque, or <tt>null</tt>
362 :     * if this deque is empty.
363 :     *
364 :     * <p>This method is equivalent to {@link #pollFirst()}.
365 :     *
366 :     * @return the first element of this deque, or <tt>null</tt> if
367 :     * this deque is empty
368 :     */
369 :     E poll();
370 :    
371 :     /**
372 :     * Retrieves and removes the head of the queue represented by this deque.
373 : jsr166 1.6 * This method differs from the {@link #poll} method only in that it
374 : dl 1.1 * throws an exception if this deque is empty.
375 :     *
376 :     * <p>This method is equivalent to {@link #removeFirst()}.
377 :     *
378 :     * @return the head of the queue represented by this deque
379 :     * @throws NoSuchElementException if this deque is empty
380 :     */
381 :     E remove();
382 :    
383 :     /**
384 :     * Retrieves, but does not remove, the head of the queue represented by
385 :     * this deque, returning <tt>null</tt> if this deque is empty.
386 :     *
387 : dl 1.3 * <p>This method is equivalent to {@link #peekFirst()}.
388 : dl 1.1 *
389 :     * @return the head of the queue represented by this deque, or
390 :     * <tt>null</tt> if this deque is empty
391 :     */
392 :     E peek();
393 :    
394 :     /**
395 :     * Retrieves, but does not remove, the head of the queue represented by
396 : jsr166 1.6 * this deque. This method differs from the {@link #peek} method only in
397 : dl 1.1 * that it throws an exception if this deque is empty.
398 :     *
399 : dl 1.3 * <p>This method is equivalent to {@link #getFirst()}.
400 : dl 1.1 *
401 :     * @return the head of the queue represented by this deque
402 :     * @throws NoSuchElementException if this deque is empty
403 :     */
404 :     E element();
405 :    
406 :    
407 :     // *** Stack methods ***
408 :    
409 :     /**
410 :     * Pushes an element onto the stack represented by this deque. In other
411 : dl 1.3 * words, inserts the element at the front of this deque unless it would
412 : dl 1.1 * violate capacity restrictions.
413 :     *
414 :     * <p>This method is equivalent to {@link #addFirst}.
415 :     *
416 : dl 1.3 * @param e the element to push
417 : dl 1.1 * @throws IllegalStateException if it was not possible to insert
418 :     * the element due to capacity restrictions
419 : dl 1.3 * @throws NullPointerException if the specified element is null and this
420 : dl 1.1 * deque does not permit null elements
421 :     */
422 :     void push(E e);
423 :    
424 :     /**
425 :     * Pops an element from the stack represented by this deque. In other
426 : dl 1.2 * words, removes and returns the first element of this deque.
427 : dl 1.1 *
428 :     * <p>This method is equivalent to {@link #removeFirst()}.
429 :     *
430 :     * @return the element at the front of this deque (which is the top
431 :     * of the stack represented by this deque)
432 :     * @throws NoSuchElementException if this deque is empty
433 :     */
434 :     E pop();
435 :    
436 :    
437 :     // *** Collection Method ***
438 :    
439 :     /**
440 :     * Returns an iterator over the elements in this deque. The elements
441 :     * will be ordered from first (head) to last (tail).
442 : dl 1.3 *
443 : dl 1.1 * @return an <tt>Iterator</tt> over the elements in this deque
444 :     */
445 :     Iterator<E> iterator();
446 :     }

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8