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