Stack implementation in Python

Posted on Edited on In , Views:

What is stack

Stack is a linear data structure in which the items are in a Last-In-First-Out(LIFO)manner.

The stack may include the following key functions.

  • push() - add an item to the top of the stack
  • pop() - remove the item at the top
  • size() - return the number of items in stack
  • peek() - return the item from top of the stack
  • is_empty() - check if the stack is empty

How to implement

There are various ways to implement a stack in Python. In this post, we will learn how to implement it with the following ways.

  • list
  • collections.deque
  • queue.LifoQueue
  • linked list

using list

In Python, list is like dynamic array. The items in list are stored contiguously in memory. Thus, the random access to list is as fast as array. However, as it grows bigger than the allocated memory it currently holds, it needs to have more memory allocation to increase the capacity dynamically. In such case, the stack append call could take longer time.

st = []
st.append(1)
st.append(2)
st.append(3)
print("stack size: {}".format(len(st)))
print(st.pop())
print(st.pop())
print(st.pop())
print("stack size: {}".format(len(st)))

Using deque

deque is pronounced “deck” and stands for “double-ended queue”. It is built upon a doubly linked list which allows insert/remove nodes from both ends with constant time(O(1)). Deque is the prefered method to implement a stack in Python. Note that deque is not thread-safe.

from collections import deque

st = deque()
st.append(1)
st.append(2)
st.append(3)
print("stack size: {}".format(len(st)))
print(st.pop())
print(st.pop())
print(st.pop())
print("stack size: {}".format(len(st)))

Using LifoQueue

If you need multi-threading, you can use queue.LifoQueue module. However, it comes at a performance cost to achieve the thread-safety.

from queue import LifoQueue

st = LifoQueue()
st.put(1)
st.put(2)
st.put(3)
print("stack size: {}".format(st.qsize()))
print(st.get())
print(st.get())
print(st.get())
print("stack size: {}".format(st.qsize()))

Using linked list

You also can implement your own stack with the linked list data structure.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def get_size(self):
        return self.size

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

    def push(self, val):
        n = Node(val)
        if self.top == None:
            self.top = n
        else:
            n.next = self.top
            self.top = n

        self.size += 1

    def pop(self):
        if self.is_empty():
            raise Exception("empty stack")

        val = self.top.val
        self.top = self.top.next
        self.size -= 1
        return val

    def peek(self):
        if self.is_empty():
            raise Exception("empty stack")

        return self.top.val

    def __str__(self):
        curr = self.top
        st_str = ""
        while curr:
            st_str += str(curr.val) + "->"
            curr = curr.next
        return st_str[:-2]


st = Stack()
st.push(1)
st.push(2)
st.push(3)
print("Stack: {}".format(st))
print("stack size: {}".format(st.size))
print("stack top: {}".format(st.peek()))
print(st.pop())
print(st.pop())
print(st.pop())
print("stack size: {}".format(st.size))