4.8 Stacks

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:

interface Stack extends Collection:
    push(x)    // Pushes x on top of the stack.
    pop()      // Pops the top of the stack and returns it.
    peek()     // Returns the top element, without removing it.

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.8.1 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 implements Stack:
    DynamicArrayStack():
        this.internalArray = new Array(8)  // Internal array containing the stack elements
        this.stackSize = 0                 // Size of stack, and index of the next free slot

Note that here we use an initial array size of 8, but we could use any positive value. (It doesn’t work with an initial empty array, can you figure out why?)

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.8.2 Pushing to the Stack

class DynamicArrayStack implements Stack:
    ...
    push(x):
        if this.stackSize >= this.internalArray.size():
            this.resizeArray(this.internalArray.size() * 2)
        this.internalArray[this.stackSize] = x
        this.stackSize = this.stackSize + 1

Note that any resizing factor >1 works, and in fact it is probably better to use something like 1.5 or even 1.1 (because this will save memory without losing too much efficiency).

4.8.3 Popping from the Stack

class DynamicArrayStack implements Stack:
    ...
    pop():
        precondition: this.stackSize > 0
        this.stackSize = this.stackSize - 1
        x = this.internalArray[this.stackSize]
        this.internalArray[this.stackSize] = null  // For garbage collection
        if this.stackSize <= this.internalArray.size() * 1/3:
            this.resizeArray(this.internalArray.size() * 1/2)
        return x

Note that the factors 1/3 and 1/2 are not set in stone. The only requirement is that the minimum load factor 1/3 must be smaller than the shrinking factor 1/2, which in turn must be <1.

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.

4.8.4 Linked List Stacks

The linked stack implementation is quite simple. Elements are inserted and removed only from the head of the list. Here is a visual representation for the linked stack.

class LinkedStack implements Stack:
    LinkedStack():
        this.top = null     // Pointer to top of stack
        this.stackSize = 0  // Size of stack

Stack nodes are exactly the same as the linked list nodes we saw earlier.

class Node:
    Node(elem, next):
        this.elem = elem   // Value for this node
        this.next = next   // Pointer to next node in stack

4.8.4.1 Linked Stack Push

class LinkedStack implements Stack:
    ...
    push(x):
        this.top = new Node(x, this.top)
        this.stackSize = this.stackSize + 1

4.8.4.2 Linked Stack Pop

class LinkedStack implements Stack:
    ...
    pop():
        precondition: this.stackSize > 0
        removed = this.top
        this.top = removed.next
        removed.next = null  // For garbage collection
        this.stackSize = this.stackSize - 1
        return removed.elem

4.8.5 Comparison of Array-Based and Linked Stacks

All operations for the array-based and linked stack implementations take constant time, so from a time efficiency perspective, neither has a significant advantage. Another basis for comparison is the total space required. The analysis is similar to that done for list implementations. The array-based stack must allocate an array with more elements than actually needed, and some of that space is wasted whenever the stack is not full. The linked stack can shrink and grow but requires the overhead of a next field for every element.

4.8.5.1 Implementing two stacks using one array

If you need to use two stacks at the same time, you can take advantage of the one-way growth of the array-based stack by using a single array to store two stacks. One stack grows inward from each end as illustrated by the figure below, hopefully leading to less wasted space. However, this only works well when the space requirements of the two stacks are inversely correlated. In other words, ideally when one stack grows, the other will shrink. This is particularly effective when elements are taken from one stack and given to the other. If instead both stacks grow at the same time, then the free space in the middle of the array will be exhausted quickly, and the array has to be resized.