Stack in Python: How, why, and where?

Credit: https://unsplash.com/@eklektikum

Stack is a linear data structure that stores data in LIFO (Last In First Out) manners. Web browser’s back button is a stack application.

We perform two major operations in the stack that are PUSH and POP. The PUSH operation adds an element/ value to the stack, and the POP operation removes or deletes an element/value from the stack.

Some basic operations in the stack

1. PUSH — Add an element or value to the stack. The time complexity is O(1)
2. POP — Remove the topmost element or value from the stack. The time complexity is O(1)
3. TOP — Get the top element or value of the stack without removing it. It is also known as PEEK. The time complexity is O(1)
4. EMPTY — Check if the stack is empty or not. The time complexity is O(1)
5. FULL — Check if the stack is full. The time complexity is O(1)
6. SIZE — Check the size of the stack. The time complexity is O(1)

Implementation of stack

There are various options to implement the stack in Python. Here, we discuss stack implementation using Python, and its modules. Stack in Python can be implemented in the following ways:

• list
• collections.deque
• queue.LifoQueue

Implementation using List

Python list can be used as the stack. List append() method used for adding elements in the stack, which is similar to stack push operation. List pop() method used for removing elements from the stack, which is similar to stack pop() operation. Python lists have performance issues. The list push(), pop() operation becomes slow as it grows. If the list grows and out of a block of memory then python allocates some memory. This is the reason why Python lists become slow gradually. The time complexity is O(n).

Let’s understand the following example

# Define empty stack
stack = []
# Add element to stack
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
print("Display stack after PUSH operation")
print(stack)
print("Remove element from stack")
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
print("Display stack after POP operation")
print(stack)

Output:

Display stack after PUSH operation
[1, 2, 3, 4, 5]
Remove element from stack
5
4
3
2
1
Display stack after POP operation
[]

In the above code, we defined an empty list. Then append some elements in the stack, which is similar to stack PUSH() operation. We also removed the elements using the pop() method. The pop() method returns the last element from the list.

Implementation using collection.deque

The Python collection module provides the deque class. By using deque, we can create a stack. The deque is pronounced as the deck which means double-ended queue. The deque is better than the Python list because its append and pop operation faster than the Python list. The time complexity is O(1).

Let’s understand the following example

# Define empty stack
from collections import deque
stack = deque()
# Add element to stack
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)
print("Display stack after PUSH operation")
print(stack)
print("Remove element from stack")
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
print("Display stack after POP operation")
print(stack)

Output:

Display stack after PUSH operation
[1, 2, 3, 4, 5]
Remove element from stack
5
4
3
2
1
Display stack after POP operation
[]

Implementation using LifoQueue

The Python queue module has LifoQue, which is the same as a stack. It’s has put() method to add element in stack and put() method to remove from the stack.

Some basic operations in LifoQueue

1. put() — Add element to stack. If the queue is full, it waits until space is available.
2. put_nowait() — Add element to stack. Only enqueue the item if a free slot is immediately available. Otherwise, raise the Full exception.
3. qsize() — Return the approximate size of the queue (not reliable!)
4. empty() — Return True if the queue is empty, False otherwise (not reliable!)
5. maxsize — The used to set a maximum size of the queue. If maxsize is <= 0, the queue size is infinite.
6. full() — Return True if the queue is full, False otherwise (not reliable!)
7. get() — Remove and return an item from the queue.
8. get_nowait() — Remove and return an item from the queue without blocking. Only get an item if one is immediately available. Otherwise raise the Empty exception.

Let’s understand the following example

# Define empty stack
from queue import LifoQueue
stack = LifoQueue(maxsize=5)
print(f"Size of stack: {stack.qsize()}")
# Add element to stack
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)
print(f"Stack is Full: {stack.full()}")
print(f"Size of Stack: {stack.qsize()}")
print("Remove element from stack")
print(stack.get())
print(stack.get())
print(stack.get())
print(stack.get())
print(stack.get())
print(f"Stack is Empty: {stack.empty()}")

Output:

Size of stack: 0
Stack is Full: True
Size of Stack: 5
Remove element from stack
5
4
3
2
1
Stack is Empty: True

Initially, the stack size is 0. Then we push 5 elements in the stack using the put() method. Then, we check stack is full or not. Then, we check stack size. After that, we remove elements from the stack using the get() method. Finally, we check does stack is empty or not.

Python stack and threading

We can use the Python stack in multi-threaded programs. Using a list in multi-threading programming can dangerous because it’s not thread-safe.

The deque is a little complex because its append() and pop() methods are atomic, which means they will not interrupt by the other thread.

So, to build a program of Python stack with treading, LifoQueue is better. It uses put() and get() to add and remove the stack element.

Applications of Stack

Although stack is a simple data structure to implement, it is very powerful. The most common uses of a stack are:

1. To reverse a word — Put all the letters in a stack and pop them out. Because of the LIFO order of the stack, you will get the letters in reverse order.
2. In compilers — Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
3. In browsers — The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack, and the previous URL is accessed.
4. Function call and return process — When we call a function from one other function, that function call statement may not be the first statement. After calling the function, we also have to come back from the function area to the place, where we have left our control. So we want to resume our task, not restart. For that reason, we store the address of the program counter into the stack, then go to the function body to execute it. After completion of the execution, it pops out the address from the stack and assigns it to the program counter to resume the task again.
5. Backtracking Procedure — Backtracking is one of the algorithm designing techniques. For that purpose, we dive into some way, if that way is not efficient, we come back to the previous state and go into some other paths. To get back from the current state, we need to store the previous state. For that purpose, we need a stack. Some examples of backtracking are finding the solution for the Knight Tour problem or N-Queen Problem etc.
6. Memory management — The assignment of memory takes place in contiguous memory blocks. We call this stack memory allocation because the assignment takes place in the function call stack. The size of the memory to be allocated is known to the compiler. When a function is called, its variables get memory allocated on the stack. When the function call is completed, the memory for the variables is released. All this happens with the help of some predefined routines in the compiler. The user does not have to worry about memory allocation and release of stack variables.
7. Expression Conversion — Converting one form of expression to another is one of the important applications of stacks.

• Infix to prefix
• Infix to postfix
• Prefix to Infix
• Prefix to Postfix
• Postfix to Infix
• Postfix to Infix

8. Parenthesis Matching — Given an expression, you have to find if the parenthesis is either correctly matched or not. For example, consider the expression ( a + b ) * ( c + d). In the above expression, the opening and closing of the parenthesis are given properly and hence it is said to be a correctly matched parenthesis expression. Whereas, the expression, (a + b * [c + d ) is not a valid expression as the parenthesis are incorrectly given.

9. Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.

10. In Graph Algorithms like Topological Sorting and Strongly Connected Components

Conclusion

We have mentioned three methods of implement the stack in Python. The above methods have their own advantages or disadvantages.

We are using stack with the threading, you should use the LifoQueue but make sure about its performance for popping and pushing elements. But if you are not using threading, use a deque.

We can also use the list to implement the stack but the list can have potential memory reallocation issues. The list and deque are the same in the interface, but the deque doesn’t memory allocation issues.