1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections;
18
19 import java.util.ArrayList;
20 import java.util.EmptyStackException;
21
22 /**
23 * An implementation of the {@link java.util.Stack} API that is based on an
24 * <code>ArrayList</code> instead of a <code>Vector</code>, so it is not
25 * synchronized to protect against multi-threaded access. The implementation
26 * is therefore operates faster in environments where you do not need to
27 * worry about multiple thread contention.
28 * <p>
29 * The removal order of an <code>ArrayStack</code> is based on insertion
30 * order: The most recently added element is removed first. The iteration
31 * order is <i>not</i> the same as the removal order. The iterator returns
32 * elements from the bottom up, whereas the {@link #remove()} method removes
33 * them from the top down.
34 * <p>
35 * Unlike <code>Stack</code>, <code>ArrayStack</code> accepts null entries.
36 *
37 * @see java.util.Stack
38 * @since 1.0
39 * @version $Id: ArrayStack.java 1429905 2013-01-07 17:15:14Z ggregory $
40 */
41 public class ArrayStack<E> extends ArrayList<E> implements Buffer<E> {
42
43 /** Ensure serialization compatibility */
44 private static final long serialVersionUID = 2130079159931574599L;
45
46 /**
47 * Constructs a new empty <code>ArrayStack</code>. The initial size
48 * is controlled by <code>ArrayList</code> and is currently 10.
49 */
50 public ArrayStack() {
51 super();
52 }
53
54 /**
55 * Constructs a new empty <code>ArrayStack</code> with an initial size.
56 *
57 * @param initialSize the initial size to use
58 * @throws IllegalArgumentException if the specified initial size
59 * is negative
60 */
61 public ArrayStack(final int initialSize) {
62 super(initialSize);
63 }
64
65 /**
66 * Return <code>true</code> if this stack is currently empty.
67 * <p>
68 * This method exists for compatibility with <code>java.util.Stack</code>.
69 * New users of this class should use <code>isEmpty</code> instead.
70 *
71 * @return true if the stack is currently empty
72 */
73 public boolean empty() {
74 return isEmpty();
75 }
76
77 /**
78 * Returns the top item off of this stack without removing it.
79 *
80 * @return the top item on the stack
81 * @throws EmptyStackException if the stack is empty
82 */
83 public E peek() throws EmptyStackException {
84 final int n = size();
85 if (n <= 0) {
86 throw new EmptyStackException();
87 } else {
88 return get(n - 1);
89 }
90 }
91
92 /**
93 * Returns the n'th item down (zero-relative) from the top of this
94 * stack without removing it.
95 *
96 * @param n the number of items down to go
97 * @return the n'th item on the stack, zero relative
98 * @throws EmptyStackException if there are not enough items on the
99 * stack to satisfy this request
100 */
101 public E peek(final int n) throws EmptyStackException {
102 final int m = (size() - n) - 1;
103 if (m < 0) {
104 throw new EmptyStackException();
105 } else {
106 return get(m);
107 }
108 }
109
110 /**
111 * Pops the top item off of this stack and return it.
112 *
113 * @return the top item on the stack
114 * @throws EmptyStackException if the stack is empty
115 */
116 public E pop() throws EmptyStackException {
117 final int n = size();
118 if (n <= 0) {
119 throw new EmptyStackException();
120 } else {
121 return remove(n - 1);
122 }
123 }
124
125 /**
126 * Pushes a new item onto the top of this stack. The pushed item is also
127 * returned. This is equivalent to calling <code>add</code>.
128 *
129 * @param item the item to be added
130 * @return the item just pushed
131 */
132 public E push(final E item) {
133 add(item);
134 return item;
135 }
136
137 /**
138 * Returns the one-based position of the distance from the top that the
139 * specified object exists on this stack, where the top-most element is
140 * considered to be at distance <code>1</code>. If the object is not
141 * present on the stack, return <code>-1</code> instead. The
142 * <code>equals()</code> method is used to compare to the items
143 * in this stack.
144 *
145 * @param object the object to be searched for
146 * @return the 1-based depth into the stack of the object, or -1 if not found
147 */
148 public int search(final Object object) {
149 int i = size() - 1; // Current index
150 int n = 1; // Current distance
151 while (i >= 0) {
152 final Object current = get(i);
153 if ((object == null && current == null) ||
154 (object != null && object.equals(current))) {
155 return n;
156 }
157 i--;
158 n++;
159 }
160 return -1;
161 }
162
163 /**
164 * Returns the element on the top of the stack.
165 *
166 * @return the element on the top of the stack
167 * @throws BufferUnderflowException if the stack is empty
168 */
169 public E get() {
170 final int size = size();
171 if (size == 0) {
172 throw new BufferUnderflowException();
173 }
174 return get(size - 1);
175 }
176
177 /**
178 * Removes the element on the top of the stack.
179 *
180 * @return the removed element
181 * @throws BufferUnderflowException if the stack is empty
182 */
183 public E remove() {
184 final int size = size();
185 if (size == 0) {
186 throw new BufferUnderflowException();
187 }
188 return remove(size - 1);
189 }
190
191 }