GNU Classpath (0.97.2) | |
Frames | No Frames |
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: * <p>The twelve methods described above are summarized in the 28: * following table: 29: * 30: * <p> 31: * <table BORDER CELLPADDING=3 CELLSPACING=1> 32: * <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>Special value</em></td> 41: * <td ALIGN=CENTER><em>Throws exception</em></td> 42: * <td ALIGN=CENTER><em>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: * added at the end of the deque and removed from the beginning. The methods 70: * inherited from the <tt>Queue</tt> interface are precisely equivalent to 71: * <tt>Deque</tt> methods as indicated in the following table: 72: * 73: * <p> 74: * <table BORDER CELLPADDING=3 CELLSPACING=1> 75: * <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#add add(e)}</td> 81: * <td>{@link #addLast addLast(e)}</td> 82: * </tr> 83: * <tr> 84: * <td>{@link java.util.Queue#offer offer(e)}</td> 85: * <td>{@link #offerLast offerLast(e)}</td> 86: * </tr> 87: * <tr> 88: * <td>{@link java.util.Queue#remove remove()}</td> 89: * <td>{@link #removeFirst removeFirst()}</td> 90: * </tr> 91: * <tr> 92: * <td>{@link java.util.Queue#poll poll()}</td> 93: * <td>{@link #pollFirst pollFirst()}</td> 94: * </tr> 95: * <tr> 96: * <td>{@link java.util.Queue#element element()}</td> 97: * <td>{@link #getFirst getFirst()}</td> 98: * </tr> 99: * <tr> 100: * <td>{@link java.util.Queue#peek peek()}</td> 101: * <td>{@link #peek peekFirst()}</td> 102: * </tr> 103: * </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: * When a deque is used as a stack, elements are pushed and popped from the 108: * beginning of the deque. Stack methods are precisely equivalent to 109: * <tt>Deque</tt> methods as indicated in the table below: 110: * 111: * <p> 112: * <table BORDER CELLPADDING=3 CELLSPACING=1> 113: * <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: * </tr> 121: * <tr> 122: * <td>{@link #pop pop()}</td> 123: * <td>{@link #removeFirst removeFirst()}</td> 124: * </tr> 125: * <tr> 126: * <td>{@link #peek peek()}</td> 127: * <td>{@link #peekFirst peekFirst()}</td> 128: * </tr> 129: * </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: * <p>This interface provides two methods to remove interior 136: * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and 137: * {@link #removeLastOccurrence removeLastOccurrence}. 138: * 139: * <p>Unlike the {@link List} interface, this interface does not 140: * provide support for indexed access to elements. 141: * 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: * 150: * <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}/../technotes/guides/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: * 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: * @throws ClassCastException if the class of the specified element 176: * prevents it from being added to this deque 177: * @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: * <p>This method is equivalent to {@link #add}. 191: * 192: * @param e the element to add 193: * @throws IllegalStateException if the element cannot be added at this 194: * time due to capacity restrictions 195: * @throws ClassCastException if the class of the specified element 196: * prevents it from being added to this deque 197: * @throws NullPointerException if the specified element is null and this 198: * deque does not permit null elements 199: * @throws IllegalArgumentException if some property of the specified 200: * element prevents it from being added to this deque 201: */ 202: void addLast(E e); 203: 204: /** 205: * Inserts the specified element at the front of this deque unless it would 206: * violate capacity restrictions. When using a capacity-restricted deque, 207: * this method is generally preferable to the {@link #addFirst} method, 208: * which can fail to insert an element only by throwing an exception. 209: * 210: * @param e the element to add 211: * @return <tt>true</tt> if the element was added to this deque, else 212: * <tt>false</tt> 213: * @throws ClassCastException if the class of the specified element 214: * prevents it from being added to this deque 215: * @throws NullPointerException if the specified element is null and this 216: * deque does not permit null elements 217: * @throws IllegalArgumentException if some property of the specified 218: * element prevents it from being added to this deque 219: */ 220: boolean offerFirst(E e); 221: 222: /** 223: * Inserts the specified element at the end of this deque unless it would 224: * violate capacity restrictions. When using a capacity-restricted deque, 225: * this method is generally preferable to the {@link #addLast} method, 226: * which can fail to insert an element only by throwing an exception. 227: * 228: * @param e the element to add 229: * @return <tt>true</tt> if the element was added to this deque, else 230: * <tt>false</tt> 231: * @throws ClassCastException if the class of the specified element 232: * prevents it from being added to this deque 233: * @throws NullPointerException if the specified element is null and this 234: * deque does not permit null elements 235: * @throws IllegalArgumentException if some property of the specified 236: * element prevents it from being added to this deque 237: */ 238: boolean offerLast(E e); 239: 240: /** 241: * Retrieves and removes the first element of this deque. This method 242: * differs from {@link #pollFirst pollFirst} only in that it throws an 243: * exception if this deque is empty. 244: * 245: * @return the head of this deque 246: * @throws NoSuchElementException if this deque is empty 247: */ 248: E removeFirst(); 249: 250: /** 251: * Retrieves and removes the last element of this deque. This method 252: * differs from {@link #pollLast pollLast} only in that it throws an 253: * exception if this deque is empty. 254: * 255: * @return the tail of this deque 256: * @throws NoSuchElementException if this deque is empty 257: */ 258: E removeLast(); 259: 260: /** 261: * Retrieves and removes the first element of this deque, 262: * or returns <tt>null</tt> if this deque is empty. 263: * 264: * @return the head of this deque, or <tt>null</tt> if this deque is empty 265: */ 266: E pollFirst(); 267: 268: /** 269: * Retrieves and removes the last element of this deque, 270: * or returns <tt>null</tt> if this deque is empty. 271: * 272: * @return the tail of this deque, or <tt>null</tt> if this deque is empty 273: */ 274: E pollLast(); 275: 276: /** 277: * Retrieves, but does not remove, the first element of this deque. 278: * 279: * This method differs from {@link #peekFirst peekFirst} only in that it 280: * throws an exception if this deque is empty. 281: * 282: * @return the head of this deque 283: * @throws NoSuchElementException if this deque is empty 284: */ 285: E getFirst(); 286: 287: /** 288: * Retrieves, but does not remove, the last element of this deque. 289: * This method differs from {@link #peekLast peekLast} only in that it 290: * throws an exception if this deque is empty. 291: * 292: * @return the tail of this deque 293: * @throws NoSuchElementException if this deque is empty 294: */ 295: E getLast(); 296: 297: /** 298: * Retrieves, but does not remove, the first element of this deque, 299: * or returns <tt>null</tt> if this deque is empty. 300: * 301: * @return the head of this deque, or <tt>null</tt> if this deque is empty 302: */ 303: E peekFirst(); 304: 305: /** 306: * Retrieves, but does not remove, the last element of this deque, 307: * or returns <tt>null</tt> if this deque is empty. 308: * 309: * @return the tail of this deque, or <tt>null</tt> if this deque is empty 310: */ 311: E peekLast(); 312: 313: /** 314: * Removes the first occurrence of the specified element from this deque. 315: * If the deque does not contain the element, it is unchanged. 316: * More formally, removes the first element <tt>e</tt> such that 317: * <tt>(o==null ? e==null : o.equals(e))</tt> 318: * (if such an element exists). 319: * Returns <tt>true</tt> if this deque contained the specified element 320: * (or equivalently, if this deque changed as a result of the call). 321: * 322: * @param o element to be removed from this deque, if present 323: * @return <tt>true</tt> if an element was removed as a result of this call 324: * @throws ClassCastException if the class of the specified element 325: * is incompatible with this deque (optional) 326: * @throws NullPointerException if the specified element is null and this 327: * deque does not permit null elements (optional) 328: */ 329: boolean removeFirstOccurrence(Object o); 330: 331: /** 332: * Removes the last occurrence of the specified element from this deque. 333: * If the deque does not contain the element, it is unchanged. 334: * More formally, removes the last element <tt>e</tt> such that 335: * <tt>(o==null ? e==null : o.equals(e))</tt> 336: * (if such an element exists). 337: * Returns <tt>true</tt> if this deque contained the specified element 338: * (or equivalently, if this deque changed as a result of the call). 339: * 340: * @param o element to be removed from this deque, if present 341: * @return <tt>true</tt> if an element was removed as a result of this call 342: * @throws ClassCastException if the class of the specified element 343: * is incompatible with this deque (optional) 344: * @throws NullPointerException if the specified element is null and this 345: * deque does not permit null elements (optional) 346: */ 347: boolean removeLastOccurrence(Object o); 348: 349: // *** Queue methods *** 350: 351: /** 352: * Inserts the specified element into the queue represented by this deque 353: * (in other words, at the tail of this deque) if it is possible to do so 354: * immediately without violating capacity restrictions, returning 355: * <tt>true</tt> upon success and throwing an 356: * <tt>IllegalStateException</tt> if no space is currently available. 357: * When using a capacity-restricted deque, it is generally preferable to 358: * use {@link #offer(Object) offer}. 359: * 360: * <p>This method is equivalent to {@link #addLast}. 361: * 362: * @param e the element to add 363: * @return <tt>true</tt> (as specified by {@link Collection#add}) 364: * @throws IllegalStateException if the element cannot be added at this 365: * time due to capacity restrictions 366: * @throws ClassCastException if the class of the specified element 367: * prevents it from being added to this deque 368: * @throws NullPointerException if the specified element is null and this 369: * deque does not permit null elements 370: * @throws IllegalArgumentException if some property of the specified 371: * element prevents it from being added to this deque 372: */ 373: boolean add(E e); 374: 375: /** 376: * Inserts the specified element into the queue represented by this deque 377: * (in other words, at the tail of this deque) if it is possible to do so 378: * immediately without violating capacity restrictions, returning 379: * <tt>true</tt> upon success and <tt>false</tt> if no space is currently 380: * available. When using a capacity-restricted deque, this method is 381: * generally preferable to the {@link #add} method, which can fail to 382: * insert an element only by throwing an exception. 383: * 384: * <p>This method is equivalent to {@link #offerLast}. 385: * 386: * @param e the element to add 387: * @return <tt>true</tt> if the element was added to this deque, else 388: * <tt>false</tt> 389: * @throws ClassCastException if the class of the specified element 390: * prevents it from being added to this deque 391: * @throws NullPointerException if the specified element is null and this 392: * deque does not permit null elements 393: * @throws IllegalArgumentException if some property of the specified 394: * element prevents it from being added to this deque 395: */ 396: boolean offer(E e); 397: 398: /** 399: * Retrieves and removes the head of the queue represented by this deque 400: * (in other words, the first element of this deque). 401: * This method differs from {@link #poll poll} only in that it throws an 402: * exception if this deque is empty. 403: * 404: * <p>This method is equivalent to {@link #removeFirst()}. 405: * 406: * @return the head of the queue represented by this deque 407: * @throws NoSuchElementException if this deque is empty 408: */ 409: E remove(); 410: 411: /** 412: * Retrieves and removes the head of the queue represented by this deque 413: * (in other words, the first element of this deque), or returns 414: * <tt>null</tt> if this deque is empty. 415: * 416: * <p>This method is equivalent to {@link #pollFirst()}. 417: * 418: * @return the first element of this deque, or <tt>null</tt> if 419: * this deque is empty 420: */ 421: E poll(); 422: 423: /** 424: * Retrieves, but does not remove, the head of the queue represented by 425: * this deque (in other words, the first element of this deque). 426: * This method differs from {@link #peek peek} only in that it throws an 427: * exception if this deque is empty. 428: * 429: * <p>This method is equivalent to {@link #getFirst()}. 430: * 431: * @return the head of the queue represented by this deque 432: * @throws NoSuchElementException if this deque is empty 433: */ 434: E element(); 435: 436: /** 437: * Retrieves, but does not remove, the head of the queue represented by 438: * this deque (in other words, the first element of this deque), or 439: * returns <tt>null</tt> if this deque is empty. 440: * 441: * <p>This method is equivalent to {@link #peekFirst()}. 442: * 443: * @return the head of the queue represented by this deque, or 444: * <tt>null</tt> if this deque is empty 445: */ 446: E peek(); 447: 448: 449: // *** Stack methods *** 450: 451: /** 452: * Pushes an element onto the stack represented by this deque (in other 453: * words, at the head of this deque) if it is possible to do so 454: * immediately without violating capacity restrictions, returning 455: * <tt>true</tt> upon success and throwing an 456: * <tt>IllegalStateException</tt> if no space is currently available. 457: * 458: * <p>This method is equivalent to {@link #addFirst}. 459: * 460: * @param e the element to push 461: * @throws IllegalStateException if the element cannot be added at this 462: * time due to capacity restrictions 463: * @throws ClassCastException if the class of the specified element 464: * prevents it from being added to this deque 465: * @throws NullPointerException if the specified element is null and this 466: * deque does not permit null elements 467: * @throws IllegalArgumentException if some property of the specified 468: * element prevents it from being added to this deque 469: */ 470: void push(E e); 471: 472: /** 473: * Pops an element from the stack represented by this deque. In other 474: * words, removes and returns the first element of this deque. 475: * 476: * <p>This method is equivalent to {@link #removeFirst()}. 477: * 478: * @return the element at the front of this deque (which is the top 479: * of the stack represented by this deque) 480: * @throws NoSuchElementException if this deque is empty 481: */ 482: E pop(); 483: 484: 485: // *** Collection methods *** 486: 487: /** 488: * Removes the first occurrence of the specified element from this deque. 489: * If the deque does not contain the element, it is unchanged. 490: * More formally, removes the first element <tt>e</tt> such that 491: * <tt>(o==null ? e==null : o.equals(e))</tt> 492: * (if such an element exists). 493: * Returns <tt>true</tt> if this deque contained the specified element 494: * (or equivalently, if this deque changed as a result of the call). 495: * 496: * <p>This method is equivalent to {@link #removeFirstOccurrence}. 497: * 498: * @param o element to be removed from this deque, if present 499: * @return <tt>true</tt> if an element was removed as a result of this call 500: * @throws ClassCastException if the class of the specified element 501: * is incompatible with this deque (optional) 502: * @throws NullPointerException if the specified element is null and this 503: * deque does not permit null elements (optional) 504: */ 505: boolean remove(Object o); 506: 507: /** 508: * Returns <tt>true</tt> if this deque contains the specified element. 509: * More formally, returns <tt>true</tt> if and only if this deque contains 510: * at least one element <tt>e</tt> such that 511: * <tt>(o==null ? e==null : o.equals(e))</tt>. 512: * 513: * @param o element whose presence in this deque is to be tested 514: * @return <tt>true</tt> if this deque contains the specified element 515: * @throws ClassCastException if the type of the specified element 516: * is incompatible with this deque (optional) 517: * @throws NullPointerException if the specified element is null and this 518: * deque does not permit null elements (optional) 519: */ 520: boolean contains(Object o); 521: 522: /** 523: * Returns the number of elements in this deque. 524: * 525: * @return the number of elements in this deque 526: */ 527: public int size(); 528: 529: /** 530: * Returns an iterator over the elements in this deque in proper sequence. 531: * The elements will be returned in order from first (head) to last (tail). 532: * 533: * @return an iterator over the elements in this deque in proper sequence 534: */ 535: Iterator<E> iterator(); 536: 537: /** 538: * Returns an iterator over the elements in this deque in reverse 539: * sequential order. The elements will be returned in order from 540: * last (tail) to first (head). 541: * 542: * @return an iterator over the elements in this deque in reverse 543: * sequence 544: */ 545: Iterator<E> descendingIterator(); 546: 547: }
GNU Classpath (0.97.2) |