Stacks

The Basics

A stack is a LIFO sequence. Addition and removal takes place only at one end, called the top.

Operations

• push(x): add an item on the top
• pop: remove the item at the top
• peek: return the item at the top (without removing it)
• size: return the number of items in the stack
• isEmpty: return whether the stack has no items

Examples

• Stacks of plates
• Trains
• Vending Machines
• Expression Evaluation
• Matching delimiters
• Navigating a maze
• Map coloring
• Many more examples

Representations

• Wrapper around a built-in list object
• Array-based, bounded or expandable (All operations in Θ(1))

  

• Linked (All operations in Θ(1))

  

Stacks in Java

The Java Core API has a stack class in the package java.util but you should avoid it since it subclasses Vector and thus has a bunch of non-stack operations (this is a major design flaw in the library), and it is (perhaps unnecessarily) synchronized making it slow (though always thread-safe).

Regardless, you should learn how to build a stack ADT from scratch, because:

• This is the only way for you to really learn how stacks work
• You need coding practice, especially with linked structures
• You need to know how to code things up when you find yourself in a very restrictive environment that doesn't have a collections library.

First, an interface

package edu.lmu.cs.rtoal.collections;

/**
 * A small stack interface.  You can query the size of the stack and
 * ask whether it is empty, push items, pop items, and peek at the top
 * item.
 */
public interface Stack {

    /**
     * Adds the given item to the top of the stack.
     */
    void push(Object item);

    /**
     * Removes the top item from the stack and returns it.
     * @exception java.util.NoSuchElementException if the stack is empty.
     */
    Object pop();

    /**
     * Returns the top item from the stack without popping it.
     * @exception java.util.NoSuchElementException if the stack is empty.
     */
    Object peek();

    /**
     * Returns the number of items currently in the stack.
     */
    int size();

    /**
     * Returns whether the stack is empty or not.
     */
    boolean isEmpty();
}

The Trivial Wrapper Implementation

One way to make our own stack is to make a wrapper around the existing LinkedList class.

package edu.lmu.cs.rtoal.collections;

import java.util.LinkedList;

/**
 * A stack class implemented as a wrapper around a java.util.LinkedList.
 * All stack methods simply delegate to LinkedList methods.
 */
public class SimpleStack implements Stack {
    private LinkedList<Object> list = new LinkedList<Object>();

    public void push(Object item) {list.addFirst(item);}
    public Object pop() {return list.removeFirst();}
    public Object peek() {return list.getFirst();}
    public int size() {return list.size();}
    public boolean isEmpty() {return list.isEmpty();}
}

This is a common design pattern and all developers are expected to know how to do this. Terminology associated with this technique:

• "The stack wraps the list"
• "The list is being adapted to use in a stack context"
• "The stack delegates to the list"
• "The list interface is being narrowed to that of a stack"

A Bounded Array Implementation

Things to note here:

• The capacity is set at creation time
• Pushes have a precondition that the stack isn't already full
• Pushing on a full stack is a state exception, not an argument exception
• The field for the current size doubles as the index of the next item to be pushed, and
• When popping, we take care to nullify the newly unused slot in the array to prevent a possible memory leak

package edu.lmu.cs.rtoal.collections;

import java.util.NoSuchElementException;

/**
 * An implementation of a stack using a fixed, non-expandable array whose
 * capacity is set in its constructor.
 */
public class BoundedStack implements Stack {
    private Object[] array;
    private int size = 0;

    public BoundedStack(int capacity) {
        array = new Object[capacity];
    }

    public void push(Object item) {
        if (size == array.length) {
            throw new IllegalStateException("Cannot add to full stack");
        }
        array[size++] = item;
    }

    public Object pop() {
        if (size == 0) {
            throw new NoSuchElementException("Cannot pop from empty stack");
        }
        Object result = array[size-1];
        array[--size] = null;
        return result;
    }

    public Object peek() {
        if (size == 0) {
            throw new NoSuchElementException("Cannot peek into empty stack");
        }
        return array[size - 1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}

A Linked Implementation

package edu.lmu.cs.rtoal.collections;

import java.util.NoSuchElementException;

/**
 * An implementation of the stack interface using singly-linked
 * nodes.
 */
public class LinkedStack implements Stack {
    private class Node {
        public Object data;
        public Node next;
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node top = null;

    public void push(Object item) {
        top = new Node(item, top);
    }

    public Object pop() {
        Object item = peek();
        top = top.next;
        return item;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public Object peek() {
        if (top == null) {
            throw new NoSuchElementException();
        }
        return top.data;
    }

    public int size() {
        int count = 0;
        for (Node node = top; node != null; node = node.next) {
            count++;
        }
        return count;
    }
}

Class Diagram

Unit Testing

Here is what we need to test:

• A stack is empty on construction
• A stack has size 0 on construction
• After n pushes to an empty stack, n > 0, the stack is not empty and its size is n
• If one pushes x then pops, the value popped is x.
• If one pushes x then peeks, the value returned is x, but the size stays the same
• If the size is n, then after n pops, the stack is empty and has a size 0
• Popping from an empty stack does throw a NoSuchElementException
• Peeking into an empty stack does throw a NoSuchElementException
• For bounded stacks only, pushing onto a full stack does throw an IllegalStateException

We really have three classes to test, but the test cases share a bunch of things in common; the common tests can go in a base class.

package edu.lmu.cs.rtoal.collections;

import java.util.NoSuchElementException;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertEquals;
import org.junit.Test;

/**
 * Base test for any class that implements the Stack interface.
 */
public abstract class StackTest {

    /**
     * The stack to use in all the tests: set this in subclasses.
     */
    protected Stack s;

    @Test
    public void testNewStackIsEmpty() {
        assertTrue(s.isEmpty());
        assertEquals(s.size(), 0);
    }

    @Test
    public void testPushesToEmptyStack() {
        int numberOfPushes = 6;
        for (int i = 0; i < numberOfPushes; i++) {
            s.push("zzz");
        }
        assertFalse(s.isEmpty());
        assertEquals(s.size(), numberOfPushes);
    }

    @Test
    public void testPushThenPop() {
        String message = "hello";
        s.push(message);
        assertEquals(s.pop(), message);
    }

    @Test
    public void testPushThenPeek() {
        String message = "hello";
        s.push(message);
        int size = s.size();
        assertEquals(s.peek(), message);
        assertEquals(s.size(), size);
    }

    @Test
    public void testPoppingDownToEmpty() {
        int numberOfPushes = (int)(Math.random() * 20 + 1);
        for (int i = 0; i < numberOfPushes; i++) {
            s.push("zzz");
        }
        for (int i = 0; i < numberOfPushes; i++) {
            s.pop();
        }
        assertTrue(s.isEmpty());
        assertEquals(s.size(), 0);
    }

    @Test(expected=NoSuchElementException.class)
    public void testPopOnEmptyStack() {
        assertTrue(s.isEmpty());
        s.pop();
    }

    @Test(expected=NoSuchElementException.class)
    public void testPeekIntoEmptyStack() {
        assertTrue(s.isEmpty());
        s.peek();
    }
}

package edu.lmu.cs.rtoal.collections;

import org.junit.Before;
import org.junit.Test;

/**
 * Unit test for SimpleStack.
 */
public class SimpleStackTest extends StackTest {

    @Before
    public void makeSimpleStack() {
        s = new SimpleStack();
    }

    @Test public void stupidPieceOfCrapMethodForEclipse() {}
}

package edu.lmu.cs.rtoal.collections;

import org.junit.Before;
import org.junit.Test;

/**
 * Unit test for LinkedStack.
 */
public class LinkedStackTest extends StackTest {

    @Before
    public void makeLinkedStack() {
        s = new LinkedStack();
    }

    @Test public void stupidPieceOfCrapMethodForEclipse() {}
}

package edu.lmu.cs.rtoal.collections;

import org.junit.Before;
import org.junit.Test;

/**
 * Unit test for BoundedStack.
 */
public class BoundedStackTest extends StackTest {
    private static int CAPACITY = 40;

    @Before
    public void makeBoundedStack() {
        s = new BoundedStack(CAPACITY);
    }

    @Test(expected=IllegalStateException.class)
    public void testPushToFullStack() {
        for (int i = 0; i < CAPACITY; i++) {
            s.push("abc");
        }
        s.push("abc");
    }
}