Mastering Stacks: A Comprehensive Guide with Python Examples

NOTE: Some of the code examples here assume you have a basic understanding of Runtime Complexity and Linked Lists. If you are not familiar with the subjects, we suggest you read our runtime complexity article and our linked list article.

What Are Stacks?

Stacks are data structures that work in a simple principle named LIFO (Last In First Out) or FILO (First In Last Out). Imagine a stack of plates, if you want to add a new plate, you add it to the top of it. If you want to remove a plate, you also remove it from the top. This means that you can only remove the last plate that you have added. We assume any other operation, like adding/removing to/from the middle or bottom, is impossible.
The same principle holds for a magazine of bullets. The last bullet loaded into the magazine is the first bullet to be unloaded.

Common Operations

IsEmpty

Returns whether the stack is empty or not.

Push

Pushes a new element to the top of the stack.

Pop

Removes the element at the top of the stack and returns it.

Peek / Top

Gets the element that is at the top of the stack without changing the stack.

Runtime Complexity

Runtime complexity for all operations: O(1)
Runtime complexity usually depends on a specific implementation, so you theoretically could have a very inefficient implementation, but a good one would have all operations be in constant time complexity.

Possible Implementations

The most common ways to implement a stack are with either a Linked List or an Array.

Implementation using an Array

Using an array is a straight forward implementation. We act as if the last index always points to the top of the stack. Each time an element is added, we add it to the next available index. The same is done for removal, by removing the element at the last index.

Code

class Stack:
    def __init__(self):
        self._array = []

    def is_empty(self):
        return len(self._array) == 0

    def peek(self):
        if self.is_empty():
            return None
        return self._array[-1]

    def push(self, value):
        self._array.append(value)

    def pop(self):
        if self.is_empty():
            return None
        return self._array.pop()

This code example uses a Python list to “simulate” an array. This already provides us with the needed functionality like adding at the last index (append) and removing from the last index (pop).
In other languages, for example Java, arrays are static and we would have to track the last index ourselves.

Implementation using a Linked List

Code

We can leverage the Linked List that we implemented in the previous article to implement our stack.

class Stack:
    def __init__(self):
        self._linked_list = LinkedList()

    def is_empty(self):
        return self._linked_list.size == 0

    def peek(self):
        if self.is_empty():
            return None
        return self._linked_list.head()

    def push(self, value):
        self._linked_list.insert_at_beginning(value)

    def pop(self):
        if self.is_empty():
            return None
        return self._linked_list.remove_from_beginning()

This models a stack behavior because we only add elements at the beginning of the list, and are also removing elements only from the beginning of the list as well. This is basically the same thing with did in the previous implementation, but with a different data structure underneath.

Tradeoffs Between Linked List / Array Implementation

Both implementations are easy and have the same time complexity in this case.
However, in some languages, for example Java, arrays are static. This means they have a fixed size when allocated, which is perfectly fine if you are okay with limiting the maximum number of elements your stack can hold. If you do not, you’ll have to change the implementation by creating a new array when the original array is full, with a larger size (for example double) and copy all the elements to the new array from the old one. Then you could discard the old array and treat the new one as your data.

The drawback of this approach is that once in a while, we would have a costly O(n) operation because we are copying the data to a new array.

Usage Example

Regardless of the implementation, if we run the code:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())
print(s.peek())
s.push(4)
print(s.pop())
print(s.pop())
s.push(5)
print(s.pop())
print(s.pop())
print(s.pop())

We get the output:

3
2
4
2
5
1
None