Deque.java revision be0e537d8953365ae5a008350461ccf777a719fb
151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is free software; you can redistribute it and/or modify it 551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under the terms of the GNU General Public License version 2 only, as 651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * published by the Free Software Foundation. Oracle designates this 751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * particular file as subject to the "Classpath" exception as provided 851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by Oracle in the LICENSE file that accompanied this code. 951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is distributed in the hope that it will be useful, but WITHOUT 1151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version 2 for more details (a copy is included in the LICENSE file that 1451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * accompanied this code). 1551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * You should have received a copy of the GNU General Public License version 1751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2 along with this work; if not, write to the Free Software Foundation, 1851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or visit www.oracle.com if you need additional information or have any 2251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * questions. 2351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 2451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 2651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This file is available under and governed by the GNU General Public 2751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * License version 2 only, as published by the Free Software Foundation. 2851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * However, the following notice accompanied the original version of this 2951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * file: 3051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Written by Doug Lea and Josh Bloch with assistance from members of 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * JCP JSR-166 Expert Group and released to the public domain, as explained 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * at http://creativecommons.org/publicdomain/zero/1.0/ 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipackage java.util; 3651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 37be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller// BEGIN android-note 38be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller// removed link to collections framework docs 39be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller// END android-note 40be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 4251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A linear collection that supports element insertion and removal at 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * both ends. The name <i>deque</i> is short for "double ended queue" 44be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * and is usually pronounced "deck". Most {@code Deque} 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * implementations place no fixed limits on the number of elements 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * they may contain, but this interface supports capacity-restricted 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deques as well as those with no fixed size limit. 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This interface defines methods to access the elements at both 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ends of the deque. Methods are provided to insert, remove, and 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * examine the element. Each of these methods exists in two forms: 5251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * one throws an exception if the operation fails, the other returns a 53be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * special value (either {@code null} or {@code false}, depending on 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the operation). The latter form of the insert operation is 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * designed specifically for use with capacity-restricted 56be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code Deque} implementations; in most implementations, insert 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * operations cannot fail. 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>The twelve methods described above are summarized in the 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * following table: 6151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p> 6351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <table BORDER CELLPADDING=3 CELLSPACING=1> 64be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <caption>Summary of Deque methods</caption> 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td></td> 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER COLSPAN = 2> <b>First Element (Head)</b></td> 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER COLSPAN = 2> <b>Last Element (Tail)</b></td> 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td></td> 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Throws exception</em></td> 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Special value</em></td> 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Throws exception</em></td> 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Special value</em></td> 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td><b>Insert</b></td> 79be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#addFirst addFirst(e)}</td> 80be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#offerFirst offerFirst(e)}</td> 81be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#addLast addLast(e)}</td> 82be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#offerLast offerLast(e)}</td> 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td><b>Remove</b></td> 86be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#removeFirst removeFirst()}</td> 87be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#pollFirst pollFirst()}</td> 88be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#removeLast removeLast()}</td> 89be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#pollLast pollLast()}</td> 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td><b>Examine</b></td> 93be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#getFirst getFirst()}</td> 94be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#peekFirst peekFirst()}</td> 95be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#getLast getLast()}</td> 96be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#peekLast peekLast()}</td> 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </table> 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This interface extends the {@link Queue} interface. When a deque is 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * used as a queue, FIFO (First-In-First-Out) behavior results. Elements are 10251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * added at the end of the deque and removed from the beginning. The methods 103be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * inherited from the {@code Queue} interface are precisely equivalent to 104be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code Deque} methods as indicated in the following table: 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p> 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <table BORDER CELLPADDING=3 CELLSPACING=1> 108be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <caption>Comparison of Queue and Deque methods</caption> 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 110be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td ALIGN=CENTER> <b>{@code Queue} Method</b></td> 111be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td> 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#add add(e)}</td> 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #addLast addLast(e)}</td> 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#offer offer(e)}</td> 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #offerLast offerLast(e)}</td> 12051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#remove remove()}</td> 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #removeFirst removeFirst()}</td> 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#poll poll()}</td> 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #pollFirst pollFirst()}</td> 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#element element()}</td> 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #getFirst getFirst()}</td> 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#peek peek()}</td> 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #peek peekFirst()}</td> 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </table> 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 13951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Deques can also be used as LIFO (Last-In-First-Out) stacks. This 14051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * interface should be used in preference to the legacy {@link Stack} class. 14151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * When a deque is used as a stack, elements are pushed and popped from the 14251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * beginning of the deque. Stack methods are precisely equivalent to 143be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code Deque} methods as indicated in the table below: 14451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p> 14651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <table BORDER CELLPADDING=3 CELLSPACING=1> 147be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <caption>Comparison of Stack and Deque methods</caption> 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER> <b>Stack Method</b></td> 150be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td> 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #push push(e)}</td> 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #addFirst addFirst(e)}</td> 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #pop pop()}</td> 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #removeFirst removeFirst()}</td> 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #peek peek()}</td> 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #peekFirst peekFirst()}</td> 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 16451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </table> 16551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 16651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Note that the {@link #peek peek} method works equally well when 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a deque is used as a queue or a stack; in either case, elements are 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * drawn from the beginning of the deque. 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This interface provides two methods to remove interior 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #removeLastOccurrence removeLastOccurrence}. 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Unlike the {@link List} interface, this interface does not 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * provide support for indexed access to elements. 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 177be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <p>While {@code Deque} implementations are not strictly required 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to prohibit the insertion of null elements, they are strongly 179be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * encouraged to do so. Users of any {@code Deque} implementations 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that do allow null elements are strongly encouraged <i>not</i> to 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * take advantage of the ability to insert nulls. This is so because 182be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code null} is used as a special return value by various methods 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to indicated that the deque is empty. 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 185be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <p>{@code Deque} implementations generally do not define 186be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * element-based versions of the {@code equals} and {@code hashCode} 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * methods, but instead inherit the identity-based versions from class 188be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code Object}. 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 19051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Doug Lea 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Josh Bloch 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.6 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param <E> the type of elements held in this collection 19451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 19551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic interface Deque<E> extends Queue<E> { 19651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 19751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the front of this deque if it is 198be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * possible to do so immediately without violating capacity restrictions, 199be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * throwing an {@code IllegalStateException} if no space is currently 200be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * available. When using a capacity-restricted deque, it is generally 201be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * preferable to use method {@link #offerFirst}. 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void addFirst(E e); 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the end of this deque if it is 217be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * possible to do so immediately without violating capacity restrictions, 218be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * throwing an {@code IllegalStateException} if no space is currently 219be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * available. When using a capacity-restricted deque, it is generally 220be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * preferable to use method {@link #offerLast}. 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #add}. 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void addLast(E e); 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the front of this deque unless it would 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * violate capacity restrictions. When using a capacity-restricted deque, 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this method is generally preferable to the {@link #addFirst} method, 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * which can fail to insert an element only by throwing an exception. 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 243be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if the element was added to this deque, else 244be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code false} 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean offerFirst(E e); 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the end of this deque unless it would 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * violate capacity restrictions. When using a capacity-restricted deque, 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this method is generally preferable to the {@link #addLast} method, 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * which can fail to insert an element only by throwing an exception. 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 261be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if the element was added to this deque, else 262be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code false} 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean offerLast(E e); 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the first element of this deque. This method 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * differs from {@link #pollFirst pollFirst} only in that it throws an 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 27651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 27751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of this deque 27851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 27951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 28051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E removeFirst(); 28151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 28251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 28351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the last element of this deque. This method 28451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * differs from {@link #pollLast pollLast} only in that it throws an 28551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 28651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 28751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the tail of this deque 28851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E removeLast(); 29151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 29351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the first element of this deque, 294be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 296be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the head of this deque, or {@code null} if this deque is empty 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E pollFirst(); 29951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 30151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the last element of this deque, 302be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 304be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the tail of this deque, or {@code null} if this deque is empty 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E pollLast(); 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the first element of this deque. 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #peekFirst peekFirst} only in that it 31251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * throws an exception if this deque is empty. 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of this deque 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E getFirst(); 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the last element of this deque. 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #peekLast peekLast} only in that it 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * throws an exception if this deque is empty. 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the tail of this deque 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E getLast(); 32851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the first element of this deque, 331be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 333be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the head of this deque, or {@code null} if this deque is empty 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E peekFirst(); 33651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the last element of this deque, 339be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 341be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the tail of this deque, or {@code null} if this deque is empty 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E peekLast(); 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 34551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 34651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the first occurrence of the specified element from this deque. 34751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the deque does not contain the element, it is unchanged. 348be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * More formally, removes the first element {@code e} such that 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tt>(o==null ? e==null : o.equals(e))</tt> 35051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (if such an element exists). 351be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * Returns {@code true} if this deque contained the specified element 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (or equivalently, if this deque changed as a result of the call). 35351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 35451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this deque, if present 355be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if an element was removed as a result of this call 35651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 357be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * is incompatible with this deque (optional) 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 359be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * deque does not permit null elements (optional) 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removeFirstOccurrence(Object o); 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 36451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the last occurrence of the specified element from this deque. 36551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the deque does not contain the element, it is unchanged. 366be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * More formally, removes the last element {@code e} such that 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tt>(o==null ? e==null : o.equals(e))</tt> 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (if such an element exists). 369be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * Returns {@code true} if this deque contained the specified element 37051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (or equivalently, if this deque changed as a result of the call). 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 37251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this deque, if present 373be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if an element was removed as a result of this call 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 375be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * is incompatible with this deque (optional) 37651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 377be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * deque does not permit null elements (optional) 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removeLastOccurrence(Object o); 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // *** Queue methods *** 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element into the queue represented by this deque 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, at the tail of this deque) if it is possible to do so 38651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * immediately without violating capacity restrictions, returning 387be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code true} upon success and throwing an 388be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code IllegalStateException} if no space is currently available. 38951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * When using a capacity-restricted deque, it is generally preferable to 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * use {@link #offer(Object) offer}. 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #addLast}. 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 39451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 395be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} (as specified by {@link Collection#add}) 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean add(E e); 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element into the queue represented by this deque 40951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, at the tail of this deque) if it is possible to do so 41051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * immediately without violating capacity restrictions, returning 411be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code true} upon success and {@code false} if no space is currently 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * available. When using a capacity-restricted deque, this method is 41351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * generally preferable to the {@link #add} method, which can fail to 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * insert an element only by throwing an exception. 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #offerLast}. 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 41851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 419be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if the element was added to this deque, else 420be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code false} 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean offer(E e); 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 43151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the head of the queue represented by this deque 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, the first element of this deque). 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #poll poll} only in that it throws an 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 43651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #removeFirst()}. 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of the queue represented by this deque 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E remove(); 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the head of the queue represented by this deque 44551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, the first element of this deque), or returns 446be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code null} if this deque is empty. 44751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #pollFirst()}. 44951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 450be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the first element of this deque, or {@code null} if 45151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this deque is empty 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 45351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E poll(); 45451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the head of the queue represented by 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this deque (in other words, the first element of this deque). 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #peek peek} only in that it throws an 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #getFirst()}. 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of the queue represented by this deque 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 46551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E element(); 46751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 46851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the head of the queue represented by 47051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this deque (in other words, the first element of this deque), or 471be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * returns {@code null} if this deque is empty. 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #peekFirst()}. 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of the queue represented by this deque, or 476be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code null} if this deque is empty 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E peek(); 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // *** Stack methods *** 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Pushes an element onto the stack represented by this deque (in other 48551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * words, at the head of this deque) if it is possible to do so 486be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * immediately without violating capacity restrictions, throwing an 487be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code IllegalStateException} if no space is currently available. 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #addFirst}. 49051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to push 49251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void push(E e); 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Pops an element from the stack represented by this deque. In other 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * words, removes and returns the first element of this deque. 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #removeFirst()}. 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the element at the front of this deque (which is the top 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the stack represented by this deque) 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 51251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E pop(); 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // *** Collection methods *** 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 51951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the first occurrence of the specified element from this deque. 52051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the deque does not contain the element, it is unchanged. 521be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * More formally, removes the first element {@code e} such that 52251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tt>(o==null ? e==null : o.equals(e))</tt> 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (if such an element exists). 524be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * Returns {@code true} if this deque contained the specified element 52551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (or equivalently, if this deque changed as a result of the call). 52651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 527be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}. 52851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 52951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this deque, if present 530be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if an element was removed as a result of this call 53151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 532be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * is incompatible with this deque (optional) 53351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 534be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * deque does not permit null elements (optional) 53551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 53651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean remove(Object o); 53751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 53851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 539be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * Returns {@code true} if this deque contains the specified element. 540be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * More formally, returns {@code true} if and only if this deque contains 541be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * at least one element {@code e} such that 54251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tt>(o==null ? e==null : o.equals(e))</tt>. 54351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 54451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element whose presence in this deque is to be tested 545be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if this deque contains the specified element 54651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the type of the specified element 547be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * is incompatible with this deque (optional) 54851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 549be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * deque does not permit null elements (optional) 55051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 55151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean contains(Object o); 55251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 55351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 55451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the number of elements in this deque. 55551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 55651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the number of elements in this deque 55751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 55851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int size(); 55951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 56151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an iterator over the elements in this deque in proper sequence. 56251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The elements will be returned in order from first (head) to last (tail). 56351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 56451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an iterator over the elements in this deque in proper sequence 56551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 56651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Iterator<E> iterator(); 56751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 56951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an iterator over the elements in this deque in reverse 57051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sequential order. The elements will be returned in order from 57151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * last (tail) to first (head). 57251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 57351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an iterator over the elements in this deque in reverse 57451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sequence 57551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 57651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Iterator<E> descendingIterator(); 57751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 579