Implementing a Stack in Java

Lets begin implementing a stack in Java. In our stack implementation we will implement it internally like a linked list (this is a popular way to implement a stack). Implementing it as a linked list will allow us to achieve good performance for the add and remove methods for our stack (these are the essential methods of a stack).

To start with we need to declare our Stack class:

public class MyStack<T> {
	
}

Our Stack class is declared to have a type of T. This means that a new MyStack class is instantiated to hold objects of a chosen data type.

Since internally we’re implementing it similarly to a linked list we’ll need to declare a node class:

private class Node<u> {
	public U data;
	public Node<u> next;
	public Node(U data) {
		this.data = data;
		next = null;
	}
}

This is just like the node class we used in our linked list implementation! It needs to hold a pointer to the next node in the stack as well as the data contained in the node.

We’ll need class level variables to hold the head node of the stack as well as the size of the stack:

private Node<T> head;
private int size;

Declare a constructor for our MyStack class. It needs to initialize our head and size variables to null and 0 respectively: javapublic MyStack() { head = null; size = 0; }

We need to add a functions to add nodes to our stack. Unlike the add function in our linked list implementation we need the add function for our stack to add items to the top of our stack (AKA the beginning of the list).

The function has two use cases to cover:

1. An empty list (the head node is null)
2. A non-empty list (the head node is not null)

Here’s how we will handle each case:

1. Declare a new node and set the head node to be the node.
2. Declare a new node. Set the next node of the new node to the head of the list. Set the new head of the list to be the new node.

Declare our function:

public void add(T data) {

}

First we need to declare a new node for our data to be added.

        Node newNode = new Node(data);

Next add an if statement to deal with both of our two use cases:

	if(head == null) {
		//add code to deal with an empty list (null head)
	} else {
		//add code to deal with a non-empty list
	}

Set the head node to be the newly declared node for an empty list:

	head = newNode;

Set the next node of the newly declared node to the current head and then reset the current head to be the newly declared node for a non empty list:

	newNode.next = head;
	head = newNode;

Finally increment the size of the stack: java size++;

Our completed add function looks as follows:

public void add(T data) {
        Node newNode = new Node(data);
	if(head == null) {
		head = newNode;
	} else {
		newNode.next = head;
		head = newNode;
	}
	size++;
}

Next let’s implement a function to remove the element from the top of our stack and return it. This function is essential for implementing a stack. The function will be called ‘pop’.

The function has two use cases to cover:

1. An empty list (the head node is null)
2. A non-empty list (the head node is not null)

Here’s how we will handle each case:

1. Return null since there is no element to return.
2. Get the value at the head node of the stack. Set the head node of the stack to be the next node of the head node. Return the value that we got earlier.

Here’s the function definition:

public T pop() {

}

Return null if our stack is empty:

	if(head == null)
	     return null;

Store the value of the head node in result. Set the head node to be the next node in the stack. Decrement the size of our stack (since we are removing an element). Finally return the value in result.

	T result = head.data;
	head = head.next;
	size--;
	return result;

Here’s the finished function:

public T pop() {
	if(head == null)
		return null;
	T result = head.data;
	head = head.next;
	size--;
	return result;
}

We will finish implementing our stack in: Implementing a Stack in Java - Part Two.

Data Structures