Understanding a Stack data structure
Introduction
In this article, I’m going to give a try to make this data structure easy for you to understand and work with. I’ll start with the theoretical basics, what this data structure is, how it works under the hood, its complexity analysis, and implementations, and then we will solve common problems that you may find on leetcode.
What is a stack?
First, let’s answer the question, what is a stack? I think the best way to put it, is to use the definition from a well-grounded book, “Introduction to algorithms”: “Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is prespecified.” Pay close attention to the phrase “dynamic sets”. If we talk about an array, we know, that it has a fixed size and cannot contain more than N elements. From the moment it is initialized, it stores all N elements. The stack, on the opposite, is empty when being initialized, and is a dynamic set, meaning, the number of elements it stores can be changed.
A stack operates on a simple principle: the last element added to the stack will be the first one to be removed. This is why it’s often compared to a stack of plates in a cafeteria. You add plates to the top of the stack, and when you need one, you take it from the top. The stack implements a last-in, first-out, or LIFO policy.
Another real-world example can be taken from my school years: first, I put my copybooks for separate subjects in a stack, and then, one by one, I took an element(copybook itself) from it and did homework for the specific subject the copybook was made for.
Operations on stack
The main operations on a stack are push(insert) and pop(remove). It also contains peek(get the top element value without removing the element) and isEmpty(check whether the stack is empty) methods. All listed operations have constant time complexity O(1). It’s easy to understand why exactly are operations have this constant time complexity. To push an element you don’t have to go through all the stack — you just add it to the top. To pop an element, you also just need one operation — to remove one top element. Peek — you just check the top element’s value. isEmpty() just checks, if the top element is null.
Stack implementations
There are two ways to implement a stack: using an array or using a linked list. First, let’s do it using a linked list.
Linked list implementation of a stack
Let’s define a node. It will store data and a pointer to a next element(the lower one) in a stack. We will keep a pointer to the top node.
public static class StackNode<T> {
private T data;
private StackNode<T> next;
public StackNode(T elem) {
data = elem;
}
}Now let’s define the push operation. What do we need to do here? As we are now looking into the linked list implementation, we will have a top node. If the stack is not empty, we need the new element to point to the current top element, appending it to the current stack. Now, having done that, top still points to the element below the element we just added. So at this point, the only thing we are left with — change the top pointer to the new element. If the stack is empty, there is no top element, we just have to initialize it with the data given as a parameter to the push method.
public void push(T elem) {
if (top == null) {
top = new StackNode<>(elem);
return;
}
StackNode<T> adding = new StackNode<>(elem);
adding.next = top;
top = adding;
}Let’s proceed with the peek method. It should return the data stored in the top element without removing it. If the stack is empty, there is nothing to return, we can throw EmptyStackException here.
public T peek() {
if (top == null) {
throw new EmptyStackException();
}
return top.data;
}The next operation — pop. It removes the top element from the stack and returns the data stored in it. If the stack is empty, we should throw EmptyStackException hence we can’t get any data from the empty stack. If the stack is not empty, we should return the data stored in the current top element, and change the top element to the one below it. It now will be handled by the garbage collector, or you have to free memory manually, if you use C++, for example.
public T pop() {
if (top == null) {
throw new EmptyStackException();
}
T res = top.data;
top = top.next;
return res;
}The last one — isEmpty(). It checks whether the stack is empty. If it is — we should return true, otherwise — false. If there are no elements in the stack, the top points to null(it’s either not initialized or we removed all elements from the stack). So if the top is equal to null, the stack is empty.
public boolean isEmpty() {
return top == null;
}Here is the complete implementation of the Stack using a linked list in java.
import java.util.EmptyStackException;
public class StackUsingLinkedList<T> {
public static class StackNode<T> {
private T data;
private StackNode<T> next;
public StackNode(T elem) {
data = elem;
}
}
private StackNode<T> top;
public T pop() {
if (top == null) {
throw new EmptyStackException();
}
T res = top.data;
top = top.next;
return res;
}
public T peek() {
if (top == null) {
throw new EmptyStackException();
}
return top.data;
}
public void push(T elem) {
if (top == null) {
top = new StackNode<>(elem);
return;
}
StackNode<T> adding = new StackNode<>(elem);
adding.next = top;
top = adding;
}
public boolean isEmpty() {
return top == null;
}
}Array implementation of a stack
As we use array indexing and don’t have to point to the next one, each stack node only stores the data. When the stack is empty, we don’t have a top element. So for anempty stack let’s have the top index -1.
For the simplicity of explanation, let’s have a fixed-size stack, meaning it can only store N elements. In more advanced implementation, you can resize the array when it reaches it limit.
int[] arr = new int[10];
int top = -1;Now, let’s implement the push operation. As outlined previously, we need to shift top pointer one position to the right and fill this array cell with the value passed to the push method as a parameter. If the stack is already full — throw StackOverflowError.
public void push(int val) {
if (top + 1 == arr.length) {
throw new StackOverflowError();
}
top++;
arr[top] = val;
}Next operation we are going to implement — peek. Meaning we have to return the data, stored in the current top cell. If the stack is empty — throw EmptyStackException.
public int peek() {
if (top == -1) {
throw new EmptyStackException();
}
return arr[top];
}Next — pop operation. Here we need to return the element in the cell with the top index and decrement the top index, so that the top element is removed from the stack. If the stack is empty, we will throw EmptyStackException.
public int pop() {
if (top == -1) {
throw new EmptyStackException();
}
int val = arr[top];
top--;
return val;
}The last operation — isEmpty. As noted previously, when there are no elements in the array, we’ll have a top index set to -1.
public boolean isEmpty() {
return top == -1;
}Here is the complete implementation of stack using array in java:
import java.util.EmptyStackException;
public class StackUsingArray {
int[] arr = new int[10];
int top = -1;
public void push(int val) {
if (top + 1 == arr.length) {
throw new StackOverflowError();
}
top++;
arr[top] = val;
}
public int peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return arr[top];
}
public int pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
int val = arr[top];
top--;
return val;
}
public boolean isEmpty() {
return top == -1;
}
}Common problems
A good start will be to solve the 125. Valid Palindrome leetcode task. Of course, you can solve it just by comparing characters, but I think we should solve it with Stack to build up your understanding of how to work with this data structure on practice.
First thing first, we should process the string in order to work with it. As the problem’s description states, we need to turn the uppercase letters to lowercase letters and remove all non-alphanumeric characters.
Approach with a stack is the following: we fill the stack with the first half of the string. The first character will be at the bottom of the stack and the last of the first half of the string will be on top of a stack. Then, we are left with the second half of a string. Palindrome reads the same forward and backward. We are now at the centre of the string, from where we will go both ways, one to the first character through the stack and another way through the remaining second half of the string to the last character. It means for each element we traverse, we peek the top of the stack, if these characters are the same, we poll element from the stack and go to the next character. If the characters do not match, we break from the loop, because we do not meet the criteria for the palindrome string. If the stack is empty at the end of procedures we have done, meaning all the characters matched, the string is a palindrome. Otherwise, there was a mismatch, meaning the string is not a palindrome.
Below is the solution for the palindrome problem using stack in java programming language.
class Solution {
public boolean isPalindrome(String s) {
if (s.length() < 2) {
return true;
}
s = processString(s);
Stack<Character> chars = new Stack<>();
int curr = 0;
while (curr < s.length() / 2) {
chars.push(s.charAt(curr));
curr++;
}
if (s.length() % 2 != 0) {
curr++;
}
while (curr < s.length()) {
if (chars.peek().equals(s.charAt(curr))) {
chars.pop();
curr++;
} else {
break;
}
}
return chars.isEmpty();
}
public String processString(String s) {
return s.toLowerCase().replaceAll("[^a-z0-9]", "");
}
}Another popular problem on a stack is 20. Valid Parentheses.
You have three types of parentheses: (), {}, [].
Here is the general idea of how to approach this problem:
you process the string with brackets character by character. Open brackets must be closed by the same type of brackets.
If the character is an open bracket, just put it to the stack.
If the character is the closing bracket and top of the stack contains the opening bracket of a the same type, pop the element from the stack — that way we have a pair of valid brackets and we don’t need them anymore to check other ones.
If the character is the closing bracket and top of the stack contains the opening bracket of a the different type, than we should return false, hence it’s not a valid pair.
Another important case, when the stack is empty — meaning it has no elements or we have closed valid brackets, and the next character is the closing bracket, we have to return false as there is no opening bracket.
Below is the solution for the valid parentheses problem in java programming language.
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c: s.toCharArray()) {
if (stack.isEmpty() && (c == ')' || c == '}' || c == ']')) {
return false;
}
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
continue;
}
boolean isClosedRound = c == ')' && stack.peek() == '(';
boolean isClosedCurvy = c == '}' && stack.peek() == '{';
boolean isClosedStraight = c == ']' && stack.peek() == '[';
if (isClosedRound || isClosedCurvy || isClosedStraight) {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
}Another important problem is from the “Cracking the coding interview” book.
“How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should ail operate in 0 ( 1 ) time.”
There is also the same coding problem on leetcode, 155. Min Stack
If we talk about the brute-force solution, it will take O(n) time complexity, as we will have to traverse all n nodes.
Once you get the idea, the problem becomes an easy one. Alongside with the data value we are storing in the node, we can store the min value for the [0, k] stack. k is in 0 to n, representing the “index” of the stack node, counting from 0 from the bottom of the stack. For each node, we will store the min value of the stack from the bottom to this node. Meaning, for each value added we compare it with the current minimum of the current top(that comes to O(1) time complexity). If it’s not lower, we assign the same min value for this node, otherwise we assign to it the value passed to the push method. The min value at the current top node should remain the same, as in case we pop the elements above it, we won’t have access to them.
Below is the solution for the min stack problem using the java programming language.
class MinStack {
public static class StackNode {
private int data;
private int localMin;
private StackNode next;
public StackNode(int val) {
data = val;
localMin = val;
}
}
private StackNode top;
public MinStack() {
}
public void push(int val) {
StackNode node = new StackNode(val);
if (top == null) {
top = new StackNode(val);
return;
}
node.next = top;
node.localMin = Math.min(val, top.localMin);
top = node;
}
public void pop() {
top = top.next;
}
public int top() {
return top.data;
}
public int getMin() {
return top.localMin;
}
}Afterword
I hope this material was useful for you and helped you to understand the stack data structure, that was the original idea of this article. I highly encourage you to solve more problems on your own, as the real skill comes with practice. There is a leetcode list of the stack problems. I suggest you to start from easy problems, climbing up to the more complex ones. 150. Evaluate Reverse Polish Notation, even though it’s a medium problem, it’s a classic example of a stack problem and will help you to understand the pattern of these puzzles.
