Introduction: Stack in Python

A stack is a linear data structure that allows us to store and retrieve data in Last In First Out (LIFO) manner. LIFO means that whatever element goes in last, comes out first.

Think about a stack of plates in your dining room. In order to access the last plate in the stack, it is ideal to remove every plate on top of it. The concept of stack in Data Structures is just that!

Stack Methods in Python:

• push(elem) = inserting an element into the stack
• pop(elem) = removing an element from the stack
• top()/peek() = returns the reference of the top-most element in the stack
• isEmpty() = checks whether the stack is empty
• isFull() = checks whether the stack is full
• size() = calculates the size of the stack

Implementation of Stack:

There are 4 ways in which we can implement stack in Python. We’ll go into the specifics of the first 3 of the below:

1. List
2. collections.deque
3. queue.LifoQueue
4. Linked Lists (dynamic stack)

Using List:

This is a built-in data structure in Python that can be used to implement a stack. Here, instead of using push(), we use append(). The pop() method remains the same. Although it the easiest way to implement a stack, list has its shortcomings: as the stack grows bigger than the memory block allocated to the list, Python needs to perform memory allocations. This is time consuming, so speed becomes a major limitation.

Below, we see how to implement a simple stack using lists:

stack = []
def push():
    if len(stack)==n:
        print("stack is full")
    else:
        elem = input("Enter the value of element: ")
        stack.append(elem)
        print(stack)def popElem():
    if stack is None:
        print("stack is empty.")
    else:
        rem = stack.pop()
        print("Removed Element: ",rem)
        print(stack)n = int(input("Maximum Elements: "))
while True:
    print("Select the operation: 1=Push, 2=Pop, 3=Quit")
    choice = int(input())
    if choice == 1:
        push()
    elif choice==2:
        popElem()
    elif choice==3:
        break
    else:
        print("Enter Valid Choice.")

Using collections.deque:

From the collections module, we can implement a Python stack using deque class. Deque stands for double ended queue, and it allows us to insert & delete elements from both sides of a stack. Often times, this is preferred over implementing stacks with lists as deque operates the append() and pop() functions at a faster pace.

Below, we see how to implement a stack using deque:

import collectionsstack = collections.deque()def push():
    elem = input("Enter the element: ")
    stack.append(elem)
    print(stack)def popElem():
    if not stack:
        print("stack is empty")
    else:
        rem = stack.pop()
        print(stack)while True:
    print("Select the operation: 1=Push, 2=Pop, 3=Quit")
    choice = int(input())
    if choice == 1:
        push()
    elif choice == 2:
        popElem()
    elif choice == 3:
        break
    else:
        print("Invalid Choice.")

Using queue.LifoQueue:

From the queue module, we can implement a LIFO queue. This is the most effective way of implementing a stack, and we will see why that is when we talk about Threading. LifoQueue consists of alternatives for push and pop: put()and get(), respectively.

Below, we see how to implement a stack using LifoQueue:

import queuestack = queue.LifoQueue(3)def push():
    elem = input("Enter the element: ")
    stack.put(elem)
    print("Added Element: ",elem)
    print(stack)def popElem():
    if not stack:
        print("stack is empty")
    else:
        rem = stack.get()
        print("Removed Element: ",rem)
        print(stack)while True:
    print("Select the operation: 1=Push, 2=Pop, 3=Quit")
    choice = int(input())
    if choice == 1:
        push()
    elif choice == 2:
        popElem()
    elif choice == 3:
        break
    else:
        print("Invalid Choice.")

When to Implement What:

Python is a multi-threading language, meaning a processor is able to run multiple processes at the same time. Using Python Lists for data structures that tend to be accessed by multiple threads is not recommended — this is because Lists are not thread-safe. We can use deque for a thread program as long as we use append() and pop() functions only. However, when a program requires a thread-safe environment, the best method to implement is LifoQueue, as long as the program is not highly affected by the speed of the operations. If we are talking non-threading programs, it’s better to implement deque as well.

Thanks for reading!