12.1.1. Stack Terminology and Interface¶

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 easier 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” of the stack. 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. Finally, if we want to know what is at the top of the stack without removing it, we can peek at it.

Below is a stack interface:

public interface MHCStack<E> {
    // Add item to end
    public void push (E item);

    // Get last item added
    public E peek();

    // Remove last item added
    public E pop();

    // Is it empty?
    public boolean isEmpty();

    // How many items are in it?
    public int size();    
}

Like we did with the List interface, we will implement the Stack interface in two different ways.

12.1.2. ArrayList-Based Stack¶

Here is a complete implementation of the MHCStack interface using an ArrayList:

import java.util.ArrayList;
import java.util.EmptyStackException;

public class ArrayListStack<E> implements MHCStack<E> {
    private ArrayList<E> values;

    public ArrayListStack() {
        values = new ArrayList<E>();
    }

    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return values.get(values.size() - 1);
    } 
    
    public boolean isEmpty () {
        return values.size() == 0;
    }
    
    public int size() {
        return values.size();
    }

    public void push(E item) {
        values.add(item);
    }

    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return values.remove(size() - 1);
    }
}

The arraylist-based stack implementation is essentially a List that has a restricted set of operations. In particular, we can only add or remove elements from one end of the list. Notice that we initialize the values instance variable in the constructor that will hold the stack’s values:

public class ArrayListStack<E> implements MHCStack<E> {
    private ArrayList<E> values;

    public ArrayListStack() {
        values = new ArrayList<E>();
    }

Since we use an ArrayList to store the stack’s values, we can re-use all of the ArrayList’s methods, which will result in shorter code.

The main important design decision to be made is which end of the array should represent the top of the stack.

Settings

Saving...
Server Error
Resubmit

12.1.2.1. ArrayList Push Operation¶

Settings

Saving...
Server Error
Resubmit

12.1.2.2. ArrayList Pop Operation¶

Settings

Saving...
Server Error
Resubmit

12.1.3. LinkedList-Based Stack¶

Next, we look at implementing a stack using a LinkedList. Like the ArrayList-based stack, we will treat the end of the LinkedList as the top of the stack and use the LinkedList’s methods to implement the Stack interface:

import java.util.EmptyStackException;
import java.util.LinkedList;

public class LinkedListStack<E> implements MHCStack<E> {
    private LinkedList<E> values = new LinkedList<>();

    public void push(E item) {
        values.add(item);
    }

    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }

        return values.removeLast();
    } 

    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return values.getLast();
    } 
    
    public boolean isEmpty () {
        return values.isEmpty();
    }
    
    public int size() {
        return values.size();
    }
}

Note that we use the getLast() method to implement peek(), which gets the top element of the stack:

    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return values.getLast();
    } 

// NOTE: this would be part of the LinkedList class,
// where we have access to the tail instance variable
public E getLast() {
    return tail.getValue();
}

12.1.3.1. LinkedList Push Operation¶

Settings

Saving...
Server Error
Resubmit

12.1.3.2. LinkedList Pop Operation¶

Settings

Saving...
Server Error
Resubmit

12.1.4. Comparison of ArrayList-Based and LinkedList-Based Stacks¶

All operations for the ArrayList-based and LinkedList-based 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 ArrayList-based stack must declare a fixed-size array initially, and so some of that space is wasted whenever the stack is not full. The LinkedList-based stack can shrink and grow but requires the overhead of a Node field for every element.