4.9. Dynamic Array-Based Stacks¶
4.9.1. Stack Terminology and Implementation¶
The stack is a list-like structure in which elements may be inserted or removed from only one end. While this restriction makes stacks less flexible than lists, it also makes stacks both efficient (for those operations they can do) and easy to implement. Many applications require only the limited form of insert and remove operations that stacks provide. In such cases, it is more efficient to use the simpler stack data structure rather than the generic list.
Despite their restrictions, stacks have many uses. Thus, a special vocabulary for stacks has developed. Accountants used stacks long before the invention of the computer. They called the stack a “LIFO” list, which stands for “Last-In, First-Out.” Note that one implication of the LIFO policy is that stacks remove elements in reverse order of their arrival.
The accessible element of the stack is called the top element.
Elements are not said to be inserted, they are pushed
onto the stack.
When removed, an element is said to be popped from the
stack.
Here is our ADT for stacks:
// Note: This is an interface, while java.util.Stack is a class!
interface Stack<E> extends Collection<E> {
void push(E x); // Pushes x on top of the stack.
E pop(); // Pops the top of the stack and returns it. Raises an exception if the stack is empty.
E peek(); // Returns the top element, without removing it. Raises an exception if the stack is empty.
// Note: iterator() should yield the elements starting from the top of the stack.
}
class Stack(Collection):
def push(self, x): """Pushes x on top of the stack."""
def pop(self): """Pops the top of the stack and returns it. Raises an exception if the stack is empty."""
def peek(self): """Returns the top element, without removing it. Raises an exception if the stack is empty."""
# Note: __iter__() should yield the elements starting from the top of the stack.
As with lists, there are many variations on stack implementation. The two main approaches are the array-based stack and the linked stack, which are analogous to array-based and linked lists, respectively.
4.9.2. Dynamic Array-Based Stacks¶
The dynamic array-based stack contains an internal array (which will grow and shrink dynamically), and the index of the top of the stack. Or actually, the index is for the next free slot in the array, which at the same time is the size of the stack.
class DynamicArrayStack<E> implements Stack<E> {
private E[] internalArray; // Internal array containing the stack elements
private int stackSize; // Size of stack, and index of the next free slot
static int MinCapacity = 8; // Minimum capacity of internalArray
static double MinLoadFactor = 0.5; // Must be smaller than 1/CapacityMultiplier
static double CapacityMultiplier = 1.5; // Factor to grow/shrink the capacity
@SuppressWarnings("unchecked")
public DynamicArrayStack() {
internalArray = (E[]) new Object[MinCapacity];
stackSize = 0;
}
class DynamicArrayStack(Stack):
_minCapacity = 8 # Minimum capacity of internalArray
_minLoadFactor = 0.5 # Must be smaller than 1/CapacityMultiplier
_capacityMultiplier = 1.5 # Factor to grow/shrink the capacity
def __init__(self):
self._internalArray = [None] * self._minCapacity # Internal array containing the stack elements
self._stackSize = 0 # Size of stack, and index of the next free slot
The array-based stack implementation is essentially a simplified version of the array-based list. The only important design decision to be made is which end of the array should represent the top of the stack.
4.9.3. Pushing to the Stack¶
public void push(E x) {
if (stackSize >= internalArray.length)
resizeArray((int) (internalArray.length * CapacityMultiplier));
internalArray[stackSize] = x;
stackSize++;
}
def push(self, x):
if self._stackSize >= len(self._internalArray):
self._resizeArray(len(self._internalArray) * self._capacityMultiplier)
self._internalArray[self._stackSize] = x
self._stackSize += 1
4.9.4. Popping from the Stack¶
public E pop() {
if (!(stackSize > 0)) throw new NoSuchElementException("pop from empty stack");
stackSize--;
E x = internalArray[stackSize];
internalArray[stackSize] = null; // For garbage collection
if (stackSize <= internalArray.length * MinLoadFactor)
resizeArray((int) (internalArray.length / CapacityMultiplier));
return x;
}
def pop(self):
if not (self._stackSize > 0): raise IndexError("pop from empty stack")
self._stackSize -= 1
x = self._internalArray[self._stackSize]
self._internalArray[self._stackSize] = None # For garbage collection
if self._stackSize <= len(self._internalArray) * self._minLoadFactor:
self._resizeArray(len(self._internalArray) / self._capacityMultiplier)
return x
4.9.5. Array-based stacks: Full implementation¶
As you hopefully have noticed, the code for stacks is very similar to the code for lists. E.g., the internal variables are exactly the same, and the resizing method doesn’t change at all. The main difference is that stacks are even simpler to implement than their list counterparts.
Here is a complete implementation for the (dynamic) array-based stack class.
class DynamicArrayStack<E> implements Stack<E> {
private E[] internalArray; // Internal array containing the stack elements
private int stackSize; // Size of stack, and index of the next free slot
static int MinCapacity = 8; // Minimum capacity of internalArray
static double MinLoadFactor = 0.5; // Must be smaller than 1/CapacityMultiplier
static double CapacityMultiplier = 1.5; // Factor to grow/shrink the capacity
@SuppressWarnings("unchecked")
public DynamicArrayStack() {
internalArray = (E[]) new Object[MinCapacity];
stackSize = 0;
}
public void push(E x) {
if (stackSize >= internalArray.length)
resizeArray((int) (internalArray.length * CapacityMultiplier));
internalArray[stackSize] = x;
stackSize++;
}
public E peek() {
if (!(stackSize > 0)) throw new NoSuchElementException("peek from empty stack");
return internalArray[stackSize-1];
}
public E pop() {
if (!(stackSize > 0)) throw new NoSuchElementException("pop from empty stack");
stackSize--;
E x = internalArray[stackSize];
internalArray[stackSize] = null; // For garbage collection
if (stackSize <= internalArray.length * MinLoadFactor)
resizeArray((int) (internalArray.length / CapacityMultiplier));
return x;
}
private void resizeArray(int newCapacity) {
if (newCapacity < MinCapacity) return;
@SuppressWarnings("unchecked")
E[] newArray = (E[]) new Object[newCapacity];
for (int i = 0; i < stackSize; i++)
newArray[i] = internalArray[i];
internalArray = newArray;
}
public boolean isEmpty() {
return stackSize == 0;
}
public int size() {
return stackSize;
}
public Iterator<E> iterator() {
return Arrays.stream(internalArray, 0, stackSize).iterator();
}
}
class DynamicArrayStack(Stack):
_minCapacity = 8 # Minimum capacity of internalArray
_minLoadFactor = 0.5 # Must be smaller than 1/CapacityMultiplier
_capacityMultiplier = 1.5 # Factor to grow/shrink the capacity
def __init__(self):
self._internalArray = [None] * self._minCapacity # Internal array containing the stack elements
self._stackSize = 0 # Size of stack, and index of the next free slot
def push(self, x):
if self._stackSize >= len(self._internalArray):
self._resizeArray(len(self._internalArray) * self._capacityMultiplier)
self._internalArray[self._stackSize] = x
self._stackSize += 1
def peek(self):
if not (self._stackSize > 0): raise IndexError("peek from empty stack")
return self._internalArray[self._stackSize-1]
def pop(self):
if not (self._stackSize > 0): raise IndexError("pop from empty stack")
self._stackSize -= 1
x = self._internalArray[self._stackSize]
self._internalArray[self._stackSize] = None # For garbage collection
if self._stackSize <= len(self._internalArray) * self._minLoadFactor:
self._resizeArray(len(self._internalArray) / self._capacityMultiplier)
return x
def _resizeArray(self, newCapacity):
if newCapacity < self._minCapacity: return
newArray = [None] * int(newCapacity)
for i in range(self._stackSize):
newArray[i] = self._internalArray[i]
self._internalArray = newArray
def isEmpty(self):
return self._stackSize == 0
def size(self):
return self._stackSize
def __iter__(self):
for i in reversed(range(self._stackSize)):
yield self._internalArray[i]
