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 * <table BORDER CELLPADDING=3 CELLSPACING=1> 63be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <caption>Summary of Deque methods</caption> 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td></td> 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER COLSPAN = 2> <b>First Element (Head)</b></td> 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER COLSPAN = 2> <b>Last Element (Tail)</b></td> 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td></td> 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Throws exception</em></td> 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Special value</em></td> 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Throws exception</em></td> 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER><em>Special value</em></td> 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td><b>Insert</b></td> 78be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#addFirst addFirst(e)}</td> 79be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#offerFirst offerFirst(e)}</td> 80be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#addLast addLast(e)}</td> 81be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#offerLast offerLast(e)}</td> 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td><b>Remove</b></td> 85be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#removeFirst removeFirst()}</td> 86be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#pollFirst pollFirst()}</td> 87be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#removeLast removeLast()}</td> 88be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#pollLast pollLast()}</td> 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td><b>Examine</b></td> 92be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#getFirst getFirst()}</td> 93be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#peekFirst peekFirst()}</td> 94be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#getLast getLast()}</td> 95be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td>{@link Deque#peekLast peekLast()}</td> 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </table> 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This interface extends the {@link Queue} interface. When a deque is 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * used as a queue, FIFO (First-In-First-Out) behavior results. Elements are 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * added at the end of the deque and removed from the beginning. The methods 102be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * inherited from the {@code Queue} interface are precisely equivalent to 103be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code Deque} methods as indicated in the following table: 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <table BORDER CELLPADDING=3 CELLSPACING=1> 106be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <caption>Comparison of Queue and Deque methods</caption> 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 108be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td ALIGN=CENTER> <b>{@code Queue} Method</b></td> 109be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td> 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#add add(e)}</td> 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #addLast addLast(e)}</td> 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#offer offer(e)}</td> 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #offerLast offerLast(e)}</td> 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 12051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#remove remove()}</td> 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #removeFirst removeFirst()}</td> 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#poll poll()}</td> 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #pollFirst pollFirst()}</td> 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#element element()}</td> 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #getFirst getFirst()}</td> 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link java.util.Queue#peek peek()}</td> 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #peek peekFirst()}</td> 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </table> 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Deques can also be used as LIFO (Last-In-First-Out) stacks. This 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * interface should be used in preference to the legacy {@link Stack} class. 13951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * When a deque is used as a stack, elements are pushed and popped from the 14051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * beginning of the deque. Stack methods are precisely equivalent to 141be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code Deque} methods as indicated in the table below: 14251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 14351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <table BORDER CELLPADDING=3 CELLSPACING=1> 144be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <caption>Comparison of Stack and Deque methods</caption> 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 14651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td ALIGN=CENTER> <b>Stack Method</b></td> 147be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td> 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 15051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #push push(e)}</td> 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #addFirst addFirst(e)}</td> 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #pop pop()}</td> 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #removeFirst removeFirst()}</td> 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <tr> 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #peek peek()}</td> 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <td>{@link #peekFirst peekFirst()}</td> 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </tr> 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * </table> 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Note that the {@link #peek peek} method works equally well when 16451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a deque is used as a queue or a stack; in either case, elements are 16551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * drawn from the beginning of the deque. 16651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This interface provides two methods to remove interior 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #removeLastOccurrence removeLastOccurrence}. 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Unlike the {@link List} interface, this interface does not 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * provide support for indexed access to elements. 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 174be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <p>While {@code Deque} implementations are not strictly required 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to prohibit the insertion of null elements, they are strongly 176be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * encouraged to do so. Users of any {@code Deque} implementations 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that do allow null elements are strongly encouraged <i>not</i> to 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * take advantage of the ability to insert nulls. This is so because 179be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code null} is used as a special return value by various methods 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to indicated that the deque is empty. 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 182be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <p>{@code Deque} implementations generally do not define 183be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * element-based versions of the {@code equals} and {@code hashCode} 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * methods, but instead inherit the identity-based versions from class 185be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code Object}. 18651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Doug Lea 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Josh Bloch 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.6 190e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param <E> the type of elements held in this deque 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic interface Deque<E> extends Queue<E> { 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 19451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the front of this deque if it is 195be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * possible to do so immediately without violating capacity restrictions, 196be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * throwing an {@code IllegalStateException} if no space is currently 197be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * available. When using a capacity-restricted deque, it is generally 198be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * preferable to use method {@link #offerFirst}. 19951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 20051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 20151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void addFirst(E e); 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the end of this deque if it is 214be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * possible to do so immediately without violating capacity restrictions, 215be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * throwing an {@code IllegalStateException} if no space is currently 216be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * available. When using a capacity-restricted deque, it is generally 217be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * preferable to use method {@link #offerLast}. 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #add}. 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void addLast(E e); 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the front of this deque unless it would 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * violate capacity restrictions. When using a capacity-restricted deque, 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this method is generally preferable to the {@link #addFirst} method, 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * which can fail to insert an element only by throwing an exception. 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 240be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if the element was added to this deque, else 241be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code false} 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean offerFirst(E e); 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element at the end of this deque unless it would 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * violate capacity restrictions. When using a capacity-restricted deque, 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this method is generally preferable to the {@link #addLast} method, 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * which can fail to insert an element only by throwing an exception. 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 258be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if the element was added to this deque, else 259be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code false} 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 26151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 26251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean offerLast(E e); 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the first element of this deque. This method 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * differs from {@link #pollFirst pollFirst} only in that it throws an 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of this deque 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 27651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 27751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E removeFirst(); 27851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 27951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 28051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the last element of this deque. This method 28151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * differs from {@link #pollLast pollLast} only in that it throws an 28251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 28351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 28451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the tail of this deque 28551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 28651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 28751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E removeLast(); 28851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the first element of this deque, 291be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 293be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the head of this deque, or {@code null} if this deque is empty 29451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E pollFirst(); 29651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the last element of this deque, 299be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 301be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the tail of this deque, or {@code null} if this deque is empty 30251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E pollLast(); 30451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the first element of this deque. 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 30851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #peekFirst peekFirst} only in that it 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * throws an exception if this deque is empty. 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of this deque 31251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E getFirst(); 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the last element of this deque. 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #peekLast peekLast} only in that it 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * throws an exception if this deque is empty. 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the tail of this deque 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E getLast(); 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the first element of this deque, 328be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 330be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the head of this deque, or {@code null} if this deque is empty 33151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E peekFirst(); 33351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the last element of this deque, 336be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * or returns {@code null} if this deque is empty. 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 338be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the tail of this deque, or {@code null} if this deque is empty 33951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E peekLast(); 34151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the first occurrence of the specified element from this deque. 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the deque does not contain the element, it is unchanged. 345be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * More formally, removes the first element {@code e} such that 346e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@code Objects.equals(o, e)} (if such an element exists). 347be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * Returns {@code true} if this deque contained the specified element 34851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (or equivalently, if this deque changed as a result of the call). 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 35051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this deque, if present 351be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if an element was removed as a result of this call 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 353e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * is incompatible with this deque 354e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 35551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 356e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * deque does not permit null elements 357e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 35951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removeFirstOccurrence(Object o); 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the last occurrence of the specified element from this deque. 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the deque does not contain the element, it is unchanged. 364be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * More formally, removes the last element {@code e} such that 365e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@code Objects.equals(o, e)} (if such an element exists). 366be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * Returns {@code true} if this deque contained the specified element 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (or equivalently, if this deque changed as a result of the call). 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 36951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this deque, if present 370be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if an element was removed as a result of this call 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 372e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * is incompatible with this deque 373e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 375e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * deque does not permit null elements 376e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 37751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removeLastOccurrence(Object o); 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // *** Queue methods *** 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element into the queue represented by this deque 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, at the tail of this deque) if it is possible to do so 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * immediately without violating capacity restrictions, returning 386be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code true} upon success and throwing an 387be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code IllegalStateException} if no space is currently available. 38851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * When using a capacity-restricted deque, it is generally preferable to 38951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * use {@link #offer(Object) offer}. 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #addLast}. 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 394be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} (as specified by {@link Collection#add}) 39551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean add(E e); 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element into the queue represented by this deque 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, at the tail of this deque) if it is possible to do so 40951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * immediately without violating capacity restrictions, returning 410be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code true} upon success and {@code false} if no space is currently 41151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * available. When using a capacity-restricted deque, this method is 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * generally preferable to the {@link #add} method, which can fail to 41351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * insert an element only by throwing an exception. 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #offerLast}. 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to add 418be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if the element was added to this deque, else 419be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code false} 42051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean offer(E e); 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the head of the queue represented by this deque 43151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, the first element of this deque). 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #poll poll} only in that it throws an 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #removeFirst()}. 43651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of the queue represented by this deque 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E remove(); 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves and removes the head of the queue represented by this deque 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (in other words, the first element of this deque), or returns 445be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code null} if this deque is empty. 44651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 44751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #pollFirst()}. 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 449be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return the first element of this deque, or {@code null} if 45051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this deque is empty 45151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E poll(); 45351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 45451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the head of the queue represented by 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this deque (in other words, the first element of this deque). 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This method differs from {@link #peek peek} only in that it throws an 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * exception if this deque is empty. 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #getFirst()}. 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of the queue represented by this deque 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 46551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E element(); 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 46751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 46851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Retrieves, but does not remove, the head of the queue represented by 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this deque (in other words, the first element of this deque), or 470be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * returns {@code null} if this deque is empty. 47151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #peekFirst()}. 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the head of the queue represented by this deque, or 475be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code null} if this deque is empty 47651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E peek(); 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // *** Stack methods *** 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Pushes an element onto the stack represented by this deque (in other 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * words, at the head of this deque) if it is possible to do so 485be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * immediately without violating capacity restrictions, throwing an 486be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * {@code IllegalStateException} if no space is currently available. 48751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #addFirst}. 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 49051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e the element to push 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalStateException if the element cannot be added at this 49251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time due to capacity restrictions 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this deque 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * deque does not permit null elements 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of the specified 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element prevents it from being added to this deque 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski void push(E e); 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Pops an element from the stack represented by this deque. In other 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * words, removes and returns the first element of this deque. 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is equivalent to {@link #removeFirst()}. 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the element at the front of this deque (which is the top 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the stack represented by this deque) 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NoSuchElementException if this deque is empty 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 51251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E pop(); 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // *** Collection methods *** 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 51851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the first occurrence of the specified element from this deque. 51951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the deque does not contain the element, it is unchanged. 520be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * More formally, removes the first element {@code e} such that 521e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@code Objects.equals(o, e)} (if such an element exists). 522be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * Returns {@code true} if this deque contained the specified element 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (or equivalently, if this deque changed as a result of the call). 52451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 525be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}. 52651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 52751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this deque, if present 528be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if an element was removed as a result of this call 52951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 530e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * is incompatible with this deque 531e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 53251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 533e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * deque does not permit null elements 534e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 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 541e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * at least one element {@code e} such that {@code Objects.equals(o, e)}. 54251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 54351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element whose presence in this deque is to be tested 544be0e537d8953365ae5a008350461ccf777a719fbNeil Fuller * @return {@code true} if this deque contains the specified element 545e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws ClassCastException if the class of the specified element 546e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * is incompatible with this deque 547e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 54851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 549e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * deque does not permit null elements 550e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (<a href="Collection.html#optional-restrictions">optional</a>) 55151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 55251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean contains(Object o); 55351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 55451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 55551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the number of elements in this deque. 55651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 55751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the number of elements in this deque 55851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 559e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int size(); 56051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 56251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an iterator over the elements in this deque in proper sequence. 56351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The elements will be returned in order from first (head) to last (tail). 56451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 56551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an iterator over the elements in this deque in proper sequence 56651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 56751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Iterator<E> iterator(); 56851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 56951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 57051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an iterator over the elements in this deque in reverse 57151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sequential order. The elements will be returned in order from 57251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * last (tail) to first (head). 57351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 57451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an iterator over the elements in this deque in reverse 57551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sequence 57651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 57751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Iterator<E> descendingIterator(); 57851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 580