Stacks

The Basics

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

stack.gif

Operations

Examples

Representations

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:

First, an interface

Stack.java
package edu.lmu.cs.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.

SimpleStack.java
package edu.lmu.cs.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:

A Bounded Array Implementation

Things to note here:

BoundedStack.java
package edu.lmu.cs.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

LinkedStack.java
package edu.lmu.cs.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

stackuml.png

Unit Testing

Here is what we need to test:

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.

StackTest.java
package edu.lmu.cs.collections;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.util.NoSuchElementException;

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();
    }
}

The concrete test classes instantiate the specific kind of stack. Because they are subclasses of the base test class, they inherit all of the the common test cases for free!

SimpleStackTest.java
package edu.lmu.cs.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() {}
}
LinkedStackTest.java
package edu.lmu.cs.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() {}
}
BoundedStackTest.java
package edu.lmu.cs.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");
    }
}