Stack (Java)

From LiteratePrograms
Jump to: navigation, search

[edit] 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.

[edit] 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.

UML class diagram for the stack implementation.

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) {
    Element<E> newElement = new Element<E>(element);
    if (empty()) {
        head = newElement;
        head.next = null;
    } else {
        newElement.next = head;
        head = newElement;
    }
}
  • Pop: return the reference to the first element in the stack, removing it from the stack by setting the head to the next element:
<<pop>>=

public E pop() {
    E result = null;
    if (!empty()) {
        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;
}

[edit] 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 Element<E> {
	final E value;
	Element next;
	Element(E value) {
		this.value = value;
	}
}
public class Stack<E> {
    Element<E> head;
    push
    pop
    empty
    @Test
    public void testStack() {
		usage
    }
}
Download code
hijacker
hijacker
hijacker
hijacker