Learning Data Structures with Python: Stacks

Previously, I explained how linked list works and its common methods. In this episode, I am going to explain about the stack. I am going to use Python in examples but it should be easy to understand for people from another language base as well. Let’s get into it.

What is a Stack?

A stack is a data structure which has to be in a particular order and each order is dependent on other elements like Linked List. You can only access by neighbour’s reference(pointer). Stack follows Last In First Out(LIFO), in other words, A data comes, at last, will be out first when you remove a data from the stack.

Visualise you have a stack of plates animals images on and you want to get a plate from the middle of the stack which is a giraffe, how would you get it? First, you need to take the plate on a pig then bear out. We can’t simply access to a random position of the stack like an array. I know! It seems like very inefficient ways of doing it.

Then Why Use Stack?

If you need to store data in a data structure its size has to frequently change, it is better to use stack over an array because the array will have to create the new bigger size of an empty array to fit the new data, then it will copy from older array to new empty array which takes linear time O(n), whereas Stack only takes constant time O(1). So it would be better to use a stack if the data comes and goes very often.

Unlike arrays, size of stack dynamically changes depending on how many elements are contained within it and that is why we do not need to specify the size of the stack and exactly why we need to use a stack.

Real-World Example

• undo function (like ctrl + z)
• the back button on web browser to see your history
• tracking pairs of bracket and parentheses in code editors

Common Methods in Stack

There are four common methods in Stack, which are Push, Pop, Peek, isEmpty.

Push(element): Adding an element onto the top of the stack

pop(): Removing an element from the top of the stack

Peek(): Print a top element

isEmpty(): Return boolean value to check whether or not the stack is empty.

Implementation of Stack

A stack is used in conjunction with other data structures, and two common ways to implement stack are using an array or linked list.

Array

Implementation with an array is fairly straight forward, just create an array with a constructor. In other languages like Java, however, you will have to initialise size of the stack, in advance with a big number like 1000, so the array will not create new array whenever a new element is appended.

Initialising a stack using an array(Java)

class Stack {
  static final int MAX = 1000;
  int arr[] = new int[MAX]; // create a 1000 size of array
}

Array Stack in Python

class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return len(self.items) == 0   
    def push(self, element):
        self.items.append(element)
    def pop(self):
        return self.items.pop()
    def peek(self):
        if not is_empty():
           return self.items[len(self.items) - 1]

Breakdown

def __init__ is a constructor that initialises an instance, it will create an empty stack when it is initialised.

# constructor
def __init__(self):
        self.items = []
# initialise a empty stack
new_stack = Stack()

def is_empty() would return boolean data. True if the length of the stack is 0 False is length isn’t 0. Time complexity: O(1)

def push(element) is a void function that will append an element on the top of a stack O(1). Time complexity: O(1)

def pop() removes an element from the top of a stack and returns the removed item. Time complexity: O(1)

def peek() will return a stack’s top item which is the last item of an array. Because the index starts from 0, so last item’s index would be array size-1 if the stack is not empty. Time complexity: O(1)

Based on the code above, let’s create an empty stack and stack it up.

# create an empty stack
stack = Stack()
# stack it up with elements
stack.push("rabbit") # first item on the bottom
stack.push("tiger")
stack.push("giraffe")
stack.push("bear")
stack.push("pig") # last item on the top

As a result of this code, your stack would look like this:

Linked List

Stack in a linked list exactly works the same way, apart from an entry point that is top instead of a head. First, we will need to have Node which is identical one from the linked list that has a pointer to attribute for data and next reference.

Class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:
    def __init__(self):
        self.top = None
    def is_empty(self):
        return self.top is None
    def peek(self):
        return self.top.data
 
    def push(self, data):
        node = Node(data)
        node.next = self.top
        self.top = node
    def pop(self):
        data = self.top.data
        self.top = self.top.next
        return data

Example of a stack in a linked list

As in this image above, when the top element in a stack is popped, in this case, it is “pig”, the next element will be the top. Likewise, when a new element is pushed to a top, the new element will be a top, that is “panda” in this case.

In conclusion, a stack is a useful data structure as the time complexity of the common methods are O(1), despite a drawback of inconvenience with incapability of random access. and it can be implemented with an array and linked list. Thanks for reading, see you until next time!

Enjoyed this article? If so, get more similar content by subscribing to Decoded, our YouTube channel!