From LiteratePrograms

Other implementations: C | Java | Python

Overview

A simple Stack in Java, implemented as an object-oriented, recursive data structure, a singly linked list. Note that Java already provides a Stack class.

Implementation

The Stack consists of two classes: the stack, which has a head element and the element, which has a next element, visualized by the following UML class diagram.

The stack has a head element and three methods: push, for adding to the stack, pop, for retrieving and removing items and empty to test if the stack is empty.

• Push: add an element at the beginning (prepend), by setting the head to the new element and the next element to the old head:

<<push>>=
public void push(E element) {
    head = new Element<E>(element, head);
}

• Pop: return the reference to the first element in the stack, removing it from the stack by setting the head to the next element; throwing an exception when the stack is empty:

<<pop>>=
public E pop() throws EmptyStackException {
    if (empty()) throw new EmptyStackException();
    E result = head.value;
    head = head.next;
    return result;
}

• Empty: return true if the stack is empty, indicated by an empty head:

<<empty>>=
public boolean empty() {
    return head == null;
}

Usage

• Sample usage: push some elements onto the stack. Pop them from the stack while it isn't empty. The effect of this is that the order is reversed (LIFO):

<<usage>>=
Stack<String> stack = new Stack<String>();
List<String> elements = Arrays.asList("first", "second", "third","fourth");
for (String e : elements) {
    stack.push(e);
}
List<String> result = new ArrayList<String>();
while (!stack.empty()) {
    result.add(stack.pop());
}
assertEquals(Arrays.asList("fourth", "third", "second", "first"),result);

• The complete program:

<<Stack.java>>=
import static org.junit.Assert.*;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class EmptyStackException extends Exception { }
class Element<E> {
	final E value;
	final Element<E> next;
	Element(E value, Element<E> next) {
		this.value = value;
		this.next = next;
	}
}
public class Stack<E> {
    Element<E> head;
    push
    pop
    empty
    @Test
    public static void testStack() {
		usage
    }
}

Download code