What is a Stack and how to Create one in Java
A stack, also known as LIFO (last in, first out), is a linear data structure with two main operations — push and pop. Items are added to the top of the stack, and items are removed from the top of the stack. The name ‘stack’ is very self explanatory, think of having some boxes and stacking them one on top of the other. You place boxes only on the top of the stack, and to remove them, you need to take boxes back off from the top.
A stack can be implemented as an array or linked list. I like to use the linked list approach because a stack created with a singly linked list is basically a linked list where operations to the front of the list are removed. For this reason, a stack feels less complicated than a linked list.
The goal of this article is to understand the data structure. Java has a stack class that you can import if needed.
Implementation — an Integer Stack in Java
First, we need to make a node class. The node contains an element and a pointer to the next node.
Now that we have a node class, we can make a stack class. The stack class only keeps track of one thing — the last node of the stack, named top.
Now we need to add some methods. The stack should have two main operations, push and pop.
To push to the stack, first we need to check if it has any nodes in the stack. For this, we check if top is null, because if top is null, then no nodes are in the stack. If there is an element, we will create a node, point that node’s ‘next’ to the current ‘top’, and then point ‘top’ at this new node.
We can visualize this operation in the following diagram. Going left to right, we are inserting a new node to the top of the stack.
Next we need to remove nodes from the stack, and return its data. Pop is pretty straightforward for a stack. Since the top element is always tracked, we can get its data, and then point top to whatever top was pointing at.
We can visualize this with another diagram. We just set the data from the top node aside, move the ‘top’ pointer to whatever ‘top’ was pointing at before, then return the data.
Now that we have push, we can also add a method to initialize a stack from an array, print the stack, and peek stack (return top’s data, but dont remove it). Here is the finished stack class.
Now we can test the stack. I created a method that uses all of the methods that we created.
The output from this method is:
Creating empty stack, then pushing 5,19,30,35...
Peek of stack is: 35
Printing Stack ...
35 <--
30
19
5Popped 35 from stack
Popped 30 from stack
Popped 19 from stack
Printing Stack ...
5 <--Pushing 5, 10 to stack...
Printing Stack ...
10 <--
5
5
Creating stack from array {1,2,3,4,5}
Printing Stack ...
5 <--
4
3
2
1Process finished with exit code 0
There are some other methods that can be added as needed. Can you figure out how to add a size property? Solution and full project can be found on my GitHub.
