Data Structures for Dummies: Stacks & Queues
How they work and how to build your own
(Quick note: If you haven’t read the previous articles in this series on Linked Lists and Binary Search Trees, be sure to check them out as well!)
If binary search trees are the 10k marathon, stacks and queues would be the 5 minute stroll to the park. They’re actually super intuitive and reflect lots of real life situations, so let’s jump right in and get to know them!
Stacks and queues are essentially dynamic, linear arrays in which you can only manipulate the insertion and deletion of data entries in one specific way.
As its name suggests, you can think of a stack as a stack of plates; when you want to add a plate to the stack, you have to put it on the top of the stack. Likewise, when you want to take out a plate, you can only take out the topmost plate on the stack, i.e. the one you added last. Therefore, stacks are LIFO — Last In, First Out. Stacks therefore have two main functions: one, called push, is when you insert items onto the “top” of the stack. The other, called pop, is when you remove the topmost element on the stack and retrieve its data.
On the other hand, for a queue, you can imagine it as a group of people lining up for a movie; the newest person to join is added to the end of line, whereas the first person to leave the queue was the first in the line. Therefore, queues are FIFO — First In First Out. Usually the two methods we use to alter queues are enqueue, which adds a value to the end of the queue, and dequeue, which removes and returns the frontmost (or oldest) entry in the queue.
The beauty of stacks and queues is that instead of just being implemented solo, they are usually built on top of other structures as a kind of overarching framework. For example, you can build a stack on top of a linked list! Moreover, stacks and queues are normally used as tools to complete a certain task; whereas other structures like linked lists and trees are used to store actual objects.
Since stacks and queues both only offer sequential access rather than random access, they will have an efficiency of O(1) — constant time. (Learn about Big O notation here!)
Code a Queue!
Let’s jump right in. To begin, let’s define a class:
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
}So first off, we defined the overarching class Queue. Inside Queue, we defined a class called Node — essentially a struct — which will contain the information needed for each entry in our queue. Like nodes in a linked list, each node in the queue needs to have at least two items; some data and a pointer to the next node in the queue. The first line in the Node class, private int data, outlines the data; private Node next gives us a pointer; private Node(int data) is a constructor that’ll make it easier for us to set data values later.
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
} private Node head;
private Node tail; public boolean isEmpty() {
return head == null;
} public int peek() {
return head.data;
}
}
Next, we defined two elements; private Node head and private Node tail. Remember, we want to be able to remove elements from the head, and add elements to the tail of the queue. So before we do that, we’re actually going to quickly create two functions that’ll help us avoid any glitches with the structure: the first, public boolean isEmpty(), notifies you when the queue is empty/does not exist. The other, public int peek(), allows you to retrieve the data from the head of the queue.
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
} private Node head;
private Node tail; public boolean isEmpty() {
return head == null;
} public int peek() {
return head.data;
} public void add(int data) {
Node node = new Node(data);
if (tail != null) {
tail.next = node;
}
tail = node;
if (head == null) {
head = node;
}
}
}
The newest addition to our code is a function called public void add(int data) that’ll allow us to add a new node to the tail of the queue; also known as the enqueue function. So first with the line Node node = new Node(data) we create a new node using the Node class and insert some data into this new node. Then with if (tail != null), we check if the tail of the queue exists; if it does, then we point to the next slot after the tail and place our new node there. Afterwards in the line tail = node, we update and set this new node as our present tail.
But wait! Before we close off this function, we need to check if our queue exists at all; if not (head == null) then we set the new node as the head of the new queue. Alright, now we’re good to go.
public static class Queue {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
} private Node head;
private Node tail; public boolean isEmpty() {
return head == null;
} public int peek() {
return head.data;
} public void add(int data) {
Node node = new Node(data);
if (tail != null) {
tail.next = node;
}
tail = node;
if (head == null) {
head = node;
}
}
public int remove() {
int data = head.data;
head = head.next;
if (head == null) {
tail == null;
}
return data;
}
}
Okay, so the newest function we’ve written here is a remove function, which will delete and return the head of the queue a.k.a the first person in the line. This is also what I’ve previously described as the dequeue function.
We start off the function by first retrieving the data in the head with int data = head.data. Afterwards, we update the head node by replacing it with our new node, therefore moving the head node to the position after it, which is head.next. We also include an if statement to define a case where the queue does not exist (if there’s no head, then there shouldn’t be a tail either), and then we finally return the data of the new head.
Okay, so that was your queue! Let’s move on to stacks.
Coding a Stack
Let’s just start off with the basics first:
public static class Stack {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node top;}
So same as with the queue, we first define a class Node that contains some data, a pointer, and a constructor. Then, we define the element top. Since a stack is LIFO (Last In, First Out), we only really need to deal with the element that’s at the top of the stack, so no need for a head or a tail like in a queue.
public static class Stack {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node top;
public boolean isEmpty() {
return top == null;
}
public int peek() {
return top.data;
}}
Then, similarly to the queue, we check whether the stack exists or not with public boolean isEmpty(), and we also create a function that lets us simply retrieve the data of the topmost element with peek().
public static class Stack {
public static class Node {
private int data;
private Node next;
private Node(int data) {
this.data = data;
}
}
private Node top;
public boolean isEmpty() {
return top == null;
}
public int peek() {
return top.data;
} public void push(int data) {
Node node = new node(data);
node.next = top;
top = node;
} public void pop() {
int data = top.data;
top = top.next;
return data;
}
}
As previously mentioned, when it comes to stacks, the push function adds a new element to the top of the stack, and the pop function will remove and return the topmost element. This is exactly what these new methods that we’ve added will do; push creates a new node with some data, and moves the pointer of this new node to point to the top, therefore making the “original” top the 2nd element in the stack. It then updates the top element with the new node we’ve just created. Afterwards, in the pop function, we want to be able to return the “original” top’s data, so first we’re just going to access that data with top.data. Then, we’re going to update the topmost element with the node after the “original” top, and then return the data of the new top.
And voila! You’re now able to implement your very own stacks and queues.
Thank you for reading! If you found this helpful, here’s some next steps you can take:
- Send some claps this way!
- Follow me on Medium or connect with me on LinkedIn to be updated when next article of this series is out!
- Get some more practice by doing some more problems with stacks and queues!
- Read the next article in this series on hash tables!
