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:

public void push(E element) {
    Element<E> newElement = new Element<E>(element);
    if (empty()) {
        head = newElement; = null;
    } else { = 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:

public E pop() {
    E result = null;
    if (!empty()) {
        result = head.value;
        head =;
    return result;
  • Empty: return true if the stack is empty, indicated by an empty head:

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):

Stack<String> stack = new Stack<String>();
List<String> elements = Arrays.asList("first", "second", "third","fourth");
for (String e : elements) {
List<String> result = new ArrayList<String>();
while (!stack.empty()) {
assertEquals(Arrays.asList("fourth", "third", "second", "first"),result);
  • The complete program:

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;
    public void testStack() {
Download code