Stacks and queues are two separate data structures that are built off a similar concept where the data being stored is in the format of a contiguous list. Data can be added/pushed and removed/popped from both the stack and queue, however the main difference between the two data structures is the sequence of how the data is pushed or popped from the list.
A stack data structure can be compared to a physical stack of plates where each new plate added to the stack must be placed on top of the last plate added. When a plate is taken off of the stack it must be removed from the top or else the entire stack will collapse. This concept is represented by the term ‘LIFO’ (Last In First Out) because the last item added to the stack will be the first item removed. Data that is pushed to the stack is added to the top of the list and when data is popped from the stack then the top most item in the list will be removed.
A queue data structure on the other hand can be visualized as a line of people ordering food at a fast food restaurant. The first person that enters the line waits until there is an available employee to take their order and every subsequent person that enters the restaurant will join the end of the line. The person who has waited the longest in the line will be the next person that exits the line. This concept is called ‘FIFO’ (First In First Out) because the oldest item in the queue will be the next item to be removed from the list. Data that is pushed to the queue is added to the end of the list and when data is popped from the queue then the data at the head of the list will be removed.
To begin the implementation of the stack data structure, we must first create a class called 'Stack' which will hold the objects in the list that make up the stack. The Stack class will also contain an instance variable called 'top' which denotes which item is at the top of the list. We will keep the type of data in the Stack class generic which allows the instance objects to contain different types of data such as integers, strings, characters, etc.
Once we have created our Stack class, we will need a way to create the containers that store the data and ultimately make up the list. We can create these containers by implementing a subclass called Node which will allow us to create node instances that represent the stack containers. The Node class will have a variable called 'data' which stores the value of the particular object and a Node variable called 'next' that points to the next node in the list. We will define a constructor inside of the Node class that will automatically assign the data variable to the value passed in by the user.
class
Stack<T>{
public class
Node{
T data;
Node next;
public
Node(T data){
this
.data = data;
}
}
}
To finish off the basic structure of the stack, we will need a Node variable in the Stack class called 'top' which will point to the most recent node added to the list. Without the top node we will have no way of accessing the other nodes in the list and is also a way for us to track which item should be removed next.
class
Stack<T>{
public class
Node{
T data;
Node next;
public
Node(T data){
this
.data = data;
}
}
Node top;
}
We have completed the basic structure of a Stack, however we are missing a few of the basic methods that allow us to add and remove items from the list.
Four basic methods involved with the stack data structure is to add items, remove items, check if the stack is empty, and to retrieve the top item in the stack. These four methods are described below:
isEmpty():
Returns whether a list is empty or not
push(T data):
Adds a new item to the top of the stack
pop():
Removes and returns the top item in the stack
peek():
Returns the value of the top item in the stack
The isEmpty() method is a very straight forward method. If our list is empty then that means the top node has not been assigned to a value. The method will check to see what the top node is assigned to and returns whether the list is empty or not.
public boolean
isEmpty(){
if
(top ==
null
){
return true
;
}
return false
;
}
The push() method allows us to create nodes and connect these nodes to our existing list. The logic behind this method is to connect the new node to the current top node in the list then to move the top pointer to point to the new node being added. If the list is completely empty (top == null) then we know that we can assign the new node to top since this will be the first item in the stack.
public void
push(T data){
Node newNode =
new
Node(data);
if
(top ==
null
){
top = newNode;
return
;
}
newNode.next = top;
top = newNode;
}
The pop() method deletes the most recent item added to the stack which is whichever node is assigned to the top variable. To remove a node from the stack, all we have to do is move the top variable to point to the next node in the stack sequence. Prior to deleting the node, we want to store the data in the node into a variable so that we can return it at the end of the method. If the stack is completely empty and a user attempts to remove an item, the method will automatically return null and exit.
public
T pop(){
if
(top ==
null
){
return null
;
}
T removedData = top.data;
top = top.next;
return
removedData;
}
The peek() method is very straight forward since we have access to the top variable. All we have to do is return the data contained in the top node assumming that the stack is not empty. If the stack is empty we will return null.
public
T peek(){
if
(top ==
null
)
return null
;
return
top.data;
}
The queue has a very similar code structure to the stack. The only difference is that in the Queue class we will replace the node variable 'top' with two node variables called 'head' and 'tail'. These two variables speak for themselves as the head variable will point to the first node in the list while the tail variable will be assigned to the last node in the list.
class
Queue<T>{
public class
Node{
T data;
Node next;
public
Node(T data){
this
.data = data;
}
}
Node head;
Node tail;
}
Similar to a stack, we have the same four basic methods that need to be included in this Queue class however the push() and pop() methods will slightly differ in implementation to satisfy the concept of FIFO. These four methods are described below:
isEmpty():
Returns whether a list is empty or not
push(T data):
Adds a new item to the end of the queue
pop():
Removes and returns the value of the head node in the queue
peek():
Returns the value of the head node in the queue
The isEmpty() method is a very straight forward method. If our list is empty then that means both the head and tail nodes have not been assigned a value. The method only needs to check if either one of the head or tail nodes is null, however we can add some safety to our code by checking to make sure they are both null in cases we forgot to update these node variables in the push() and pop() methods.
public boolean
isEmpty(){
if
(head ==
null
&& tail ==
null
){
return true
;
}
return false
;
}
The push() method allows us to create nodes and connect these nodes to the end of the list. The logic behind this method is to connect the existing tail node to the new node and update the tail variable to point to the new node. If the list is completely empty (head == null && tail == null) then we know that both the head and tail variables must be assigned to this new node.
public void
push(T data){
Node newNode =
new
Node(data);
if
(head ==
null
&& tail ==
null
){
head = newNode;
tail = newNode;
return
;
}
tail.next = newNode;
tail = newNode;
}
The pop() method deletes the node that the head variable is pointing to. To remove a node from the queue, all we have to do is move the head variable to point to the next node in the list. Prior to deleting the node, we want to store the data contained in the node in a variable so that we can return it at the end of the method. If the node being deleted happens to be the only node in the queue then we must also update the tail variable to point to null.
public
T pop(){
if
(head ==
null
&& tail ==
null
){
return null
;
}
T removedData = head.data;
head = head.next;
if
(head ==
null
){
tail =
null
;
}
return
removedData;
}
The peek() method is very straight forward since we have access to the head variable. All we have to do is return the data contained in the node that the head pointer is pointing to assumming that the queue is not empty. If the queue is empty we will return null.
public
T peek(){
if
(head ==
null
)
return null
;
return
head.data;
}
