Stack: The LIFO Data Structure

A stack is a fundamental data structure in computer science that follows the LIFO principle, which stands for Last In, First Out.

That means the last element you push onto the stack is always the first one to come out.

Loading simulation...

Even though stacks sound simple, they power some of the most critical parts of modern software systems like:

Expression evaluation in compilers
Undo and redo functionality in text editors
The function call stack in programming languages
Algorithms like iterative DFS and backtracking

In this chapter, I'll break down:

What a stack is and how it works
The key operations and their complexities
Different ways to implement a stack in code

What is a Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle: the last item added is the first one removed.

A stack of plates is the standard analogy. New plates go on top, and the plate you take off is always the one most recently added. Removing a plate from the middle is not allowed; everything above it has to come off first.

Whenever you need to access the most recently added item first, a stack is a natural fit.

Common Stack Operations

A stack supports four standard operations:

Push: Adds a new element to the top of the stack. It runs in O(1) constant time, no matter how many elements are already in the stack.
Pop: Removes the topmost element from the stack. The previous element becomes the new top. It also runs in O(1) time.
Peek / Top: Returns the value at the top of the stack without removing it. This also runs in O(1) time.
IsEmpty: Checks whether the stack contains any elements. This is useful for guarding against popping from an empty stack, and it runs in O(1) time too.

All four operations run in O(1) time, which is what makes stacks efficient.

Stack Implementation

There are two common ways to implement a stack from scratch, each with its own trade-offs.

1. Using Arrays

The most common approach is to use an array.

You maintain two things:

An array to store the elements
A pointer called top to track the index of the last inserted element. It is initially set to -1 to represent an empty stack.

With this setup, you perform all stack operations at the end of the array, which makes them run in O(1) time.

For push operation, first check if there's room in the stack. If yes, increment top and place the new value at new top index.
For pop operation, first check if the stack is empty. If not, return the element at stack[top] and then decrement top.
For peek, return the element at top without changing top.
For isEmpty, check if top is still at -1, which means no elements have been added yet.

The main limitation of this approach is that the stack size is fixed.

Once the array is full, you can't push new elements unless you manually resize it.

This is why many modern languages provide dynamic arrays (like ArrayList in Java or list in Python) that resize automatically.

2. Using Linked Lists

Another popular way to implement a stack is by using a linked list.

In this approach, the head of the linked list represents the top of the stack.

That means:

Push means inserting a new node at the head.
Pop means removing the node from the head.

Since all operations are focused at the head, they run in O(1) time, just like the array implementation.

For push operation, create a new node and point its next to the current head. Then, update head to this new node. This makes the new node the top of the stack.
For pop operation, first check if the head is null, which means the stack is empty. If not, return the value at the head and move the head to the next node. This effectively removes the current top element.
For peek, if the head is null return -1 since the stack is empty; otherwise return head.value without removing it.
For isEmpty, if head is null, it means the stack is empty.

Since the size of linked list is dynamic, you don't need to worry about resizing like you would with a static array.

The trade-off is that each node stores an extra pointer (next), which means more memory is used compared to a plain array.

3. Built-in Libraries

In most real-world applications and coding interviews, you rarely need to implement a stack from scratch. Most modern languages provide a tested stack implementation in their standard library.

Java provides two main ways to work with stacks: Legacy stack class and recommended Deque interface.

ArrayDeque is faster and more memory-efficient than Stack. It supports all standard stack operations and is the preferred choice for new code.

Quiz

Introduction Quiz

10 quizzes

Introduction to Stacks