Stack in Python

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 stack that are PUSH and POP.
The PUSH operation adds an element/ value in the stack, and the POP operation removes or deletes an element / value from the stack.

Some basic operations in stack

  1. PUSH - Add an element or value in the stack. The time complexity is O(1)
  2. POP - Remove topmost element or value from the stack. The time complexity is O(1)
  3. TOP - Get the top element or value of 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 size of the stack. The time complexity is O(1)

Implementation of stack

There are various options to implement stack in Python.
Here, we discuss stack implementation using Python, and it’s modules.
Stack in Python can be implemented by 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 stack, which is similar to stack push operation.
List pop() method used for removing elements from 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 above code, we defined empty list.
Then append some elements in stack, which is similar to stack PUSH() operation.
We also removed the elements using 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 Python list, because it's 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 hase LifoQue, which is the same as stack.
It's have put() method to add element in stack and put() method to remove from stack.

Some basic operations in LifoQueue

  1. put() - Add element to stack. If queue is full, it's wait 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 maximum size of 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 stack size is 0. Then we push 5 elements in stack using put() method.
Then, we check stack is full or not. Then, we check stack size.
After that, we remove element from stack using get() method.
Finally, we check does stack is empty or not.

Python stack and threading

We can use Python stack in multi-threaded program. Using list in multi-threading programming can dangerous because it's not thread safe.

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

So, for build 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 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 stack and assign it into the program counter to resume the task again.
  5. Backtracking Procedure - Backtracking is one of the algorithm designing technique. 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 current state, we need to store the previous state. For that purpose, we need stack. Some examples of backtracking is finding the solution for 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 expressions to another is one of the important applications of stacks.

    1. Infix to prefix
    2. Infix to postfix
    3. Prefix to Infix
    4. Prefix to Postfix
    5. Postfix to Infix
    6. 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 same in the interface, but the deque doesn't memory allocation issues.

29

Categories:

Python

Tags:

PythonStackDatastructure