A Linked List Implementation of a Stack—Stacking ints
The following three classes are used to illustrate a simple stack implemented with a linked list.
What to Place on the Stack: Class Node
We want to stack integers (values of type int). Because we want to implement the stack as a linked list, we can't just implement the stack with integers alone. We need to also keep the integers in order, by pointing each integer pushed onto the stack to the one just below it on the stack. In order to link them together like this we create a "node" (the term often used for objects placed into a linked list) that has two instance variables:
- an instance variable to store the int value
- an instance variable to store a reference to the node below this one on the stack.
Look at class Node below to see how we design a node to have these two instance fields.
public class Node
{ // instance variables
private int data; // an instance variable that can hold a value of type int private Node next; // an instance variable that can contain a reference to another Node object
public Node(int dataItem) // Constructor for objects of class Node that initializes just the data instance variable
{ data = dataItem; next = null; }
public Node(int dataItem, Node nodeReference) // Constructor for objects of class Node that initializes // both instance variables: data and next
{ data = dataItem; next = nodeReference; }
public int get() // public method for Node objects that returns the integer data value stored in the node { return (data); }}
The only difference between this class and others you have already written is that this class has instance variable next, defined as
private Node next
Since this class itself is named Node, making instance variable next to be of type Node just means that next can contain a reference to other objects of type Node. That is, we will use the instance variable next a Node object to refer to (point to) the object just below it on the stack.
The Stack
Class Stack is pretty simple. Check it out
import java.util.*;
public class Stack
{
private Node top; // A stack class implemented as a linked list needs to have a variable that
// points to the top node on the stack.
private int data;
Stack() // This constructor builds a stack with top initially set to null,
// because there are no nodes on the stack initially
{
top = null;
}
public void push (int item) // method push accepts an int value, item, as a parameter.
{
Node newNode = new Node(item); // it then creates a new Node object with item as its instance data value
newNode.next = top; // then it sets the instance variable next to top (remember that top points to
// the top node of the stack).
top = newNode; // finally top is set to be newNode. Thus, this new node is now pointed to by top
// so it is the new top node, and the new node's next variable is pointing to the
// node that top previously pointed to, so it is pointing to the node just below it
// on the stack
}
public int pop() throws EmptyStackException
{
if (empty()) // check to see if the stack is empty before trying to pop a value off it
{
throw new EmptyStackException();
}
else // the stack is not empty
{
data = top.data; // so pick the data value from the Node object pointed to by top
top = top.next; // set top to point to the Node object just below the current top node
return(data); // return the data value to the method that called pop()
}
}
public int peek() throws EmptyStackException // peek does the same thing as pop, exept that
// it does not take the top node off of the stack
{
if (empty())
{
throw new EmptyStackException();
}
else
{
return(top.data);
}
}
public boolean empty ( ) // method empty determines whether the stack is empty
// by checking whether top is null (points to no object)
{
return top == null;
}
public String printStack() // this method is not normally part of the Stack ADT;
// it is placed here for testing purposes
{
Node temp = top;
String stackString = "";
while (temp != null) {
stackString = stackString + " " + temp.data;
temp = temp.next;
}
return (stackString);
}
}
Tying it all together—method Main
Method Main has been constructed to test the stack. Read it to see how it works.
import javax.swing.JOptionPane;
public class Main
{
public static void main (String args [])
{
Stack s = new Stack ();
String choice;
boolean done = false;
while (!done) {
try{
choice = JOptionPane.showInputDialog(
"1. push \n" +
"2. pop \n" +
"3. peek \n" +
"4. check empty \n" +
"5. print the stack \n" +
"6. exit \n \n" +
"choose one:");
switch (Integer.parseInt(choice)){
case 1:
String temp = JOptionPane.showInputDialog("Input integer to push:");
s.push(Integer.parseInt(temp));
break;
case 2:
JOptionPane.showMessageDialog(null, "The value popped is " + s.pop());
break;
case 3:
JOptionPane.showMessageDialog(null, "The value peeked at is " + s.peek());
break;
case 4:
if (s.empty()) {
JOptionPane.showMessageDialog(null, "The stack is empty.");
}
else {
JOptionPane.showMessageDialog(null, "The stack is not empty.");
}
break;
case 5:
JOptionPane.showMessageDialog(null, s.printStack());
break;
case 6:
JOptionPane.showMessageDialog(null, "...exiting");
done = true;
break;
default:
JOptionPane.showMessageDialog(null, "You entered an invalid choice. \n"
+ "Please try again!");
} //switch
} //try
catch (NumberFormatException ex) {
JOptionPane.showMessageDialog(
null,
"You must type an integer. Please Try again!");
} //catch
} //while
} // method main
} // class Main