Explain Stack in Python

A stack is a structure where items follow the Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) rule. You add a new item on one side and remove an item from the same side. Adding is termed ‘push,’ and removing is known as ‘pop.’

The ‘push’ action, as shown in the diagram below, places an element on the top of the stack. see the image for a better understanding:

The ‘pop’ action, as shown in the diagram below, takes off an element from the top of the stack. see the image for a better understanding:

How to Create a Stack in Python?

In Python, we can make a stack using the built-in List, which has methods that mimic both stack and queue actions. Alternatively, the deque library in Python offers efficient ways to perform stack and queue tasks within a single structure. Another method is using the LifoQueue class to create a stack in Python.

Methods of Python Stack

1. empty()
2. size()
3. top()/ peek()
4. push(a)
5. pop()

1. empty(): Returns ‘True’ if the stack has no items; otherwise, it returns ‘False’.

2. size(): Returns the number of items or elements present in the stack.

3. top()/ peek() :  Returns a reference to the topmost available element of the stack

4. push(a): insert the element at the top of the stack

5. pop(): Delete the topmost element of the stack

Implementation

There are multiple methods to create a stack in Python. This article focuses on building a stack using data structures and modules from the Python library.

Here’s how you can implement a stack in Python:

1. Implementation using list
2. Implementation using Collections.deque
3. Implementation using queue.LifoQueue

1. Implementation using list

In Python, you can use the built-in list as a stack. To add items to the top, you use append() instead of push(), and to remove them in a last-in-first-out (LIFO) manner, you use pop().

However, there’s a drawback with using a list: as it grows, it can become slower. This happens because items are stored consecutively in memory. If the stack becomes larger than the current memory block, Python has to allocate more memory, making some append() operations slower than others.

Example

# Python example to
# Show stack using the list
my_stack = []
# Use append() to add
# items to the stack
my_stack.append('x')
my_stack.append('y')
my_stack.append('z')
print('Initial stack:')
print(my_stack)
# Use pop() to remove
# items from the stack
print('\nItems removed from the stack:')
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print('\nStack after removals:')
print(my_stack)
# Uncommenting print(my_stack.pop())
# will result in an IndexError
# Since the stack is empty

Output

Initial stack:
[‘x’, ‘y’, ‘z’]
Items removed from the stack:
z
y
x
Stack after removals:
[]

2. Implementation using collections.deque

In Python, you can use the deque class from the collections module to create a stack. Using deque is better than using a list when you want fast add and remove operations from both ends of the stack. This is because deque offers constant-time complexity (O(1)) for these operations, whereas a list has a linear time complexity (O(n)).

The methods used with deque are similar to those with lists: append() and pop().

Example

# Python example to
# Illustrate stack using collections.deque
from collections import deque
my_stack = deque()
# Use append() to add
# items to the stack
my_stack.append('x')
my_stack.append('y')
my_stack.append('z')
print('Initial stack:')
print(my_stack)
# Use pop() to remove
# items from the stack
print('\nItems removed from the stack:')
print(my_stack.pop())
print(my_stack.pop())
print(my_stack.pop())
print('\nStack after removals:')
print(my_stack)
# Uncommenting print(my_stack.pop())
# will lead to an IndexError
# Since the stack is empty

Output

Initial stack:
deque([‘x’, ‘y’, ‘z’])
Items removed from the stack:
z
y
x
Stack after removals:
deque([])

3. Implementation using queue module

The Queue module also provides a Last-In-First-Out (LIFO) Queue, essentially functioning like a Stack. You can add data to this queue using the put() method, while the get() method retrieves data from it.

Several functions are available within this module:

1. maxsize: Indicates the maximum number of items allowed in the queue.
2. empty(): Returns True if the queue has no items; otherwise, returns False.
3. full(): Returns True if the queue contains the maximum allowable items. However, if the queue was initialized with a maxsize of 0 (which is the default), this
4. the function will never return True.
5. get(): Retrieves and removes an item from the queue. If the queue is empty, it will wait until an item becomes available.
6. get_nowait(): Fetches an item if one is immediately present; otherwise, raises a QueueEmpty exception.
7. put(item): Insert an item into the queue. If the queue is at its maximum capacity, it will wait until there’s an available slot.
8. put_nowait(item): Inserts an item into the queue without waiting. If there’s no immediate slot available, it raises a QueueFull exception.
9. qsize(): Provides the count of items currently present in the queue.

Example

# Python program to demonstrate stack implementation using the queue module
from queue import LifoQueue
# Initializing a stack with a different variable name
my_stack = LifoQueue(maxsize=3)
# Display the number of elements in the stack using qsize()
print(my_stack.qsize())
# Add elements to the stack using put()
my_stack.put('a')
my_stack.put('b')
my_stack.put('c')
# Check if the stack is full and display its size
print("Full: ", my_stack.full())
print("Size: ", my_stack.qsize())
# Remove elements from the stack using get() in LIFO order
print('\nElements popped from the stack:')
print(my_stack.get())
print(my_stack.get())
print(my_stack.get())
# Check if the stack is empty
print("\nEmpty: ", my_stack.empty())

Output
0
Full:  True
Size:  3
Elements popped from the stack:
c
b
a
Empty:  True

Implementation using a singly linked list

The linked list provides two methods, addHead(item) and removeHead(), which operate in constant time. These methods are well-suited for implementing a stack.

• getSize(): Retrieves the count of items present in the stack.
• isEmpty(): Indicates whether the stack is empty; returns True if empty and False otherwise.
• peek(): Fetches the top item from the stack. If the stack is devoid of elements, it throws an exception.
• push(value): Inserts a value at the top of the stack.
• pop(): Eliminates and returns the topmost value from the stack. If the stack is devoid of elements, it raises an exception.

Example

# Python program to demonstrate stack implementation using a linked list and different variable names.
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:
    # Initializing the stack with a dummy node for handling edge cases.
    def __init__(self):
        self.top = Node("top_dummy")
        self.count = 0
    # String representation of the stack
    def __str__(self):
        current = self.top.next
        representation = ""
        while current:
            representation += str(current.data) + "->"
            current = current.next
        return representation[:-2]
    # Obtain the current size of the stack
    def getStackSize(self):
        return self.count
    # Check if the stack is empty
    def checkEmpty(self):
        return self.count == 0
    # Peek at the top item of the stack
    def topItem(self):
        if self.checkEmpty():
            raise Exception("Attempting to peek an empty stack")
        return self.top.next.data
    # Push a value onto the stack
    def pushValue(self, data):
        node = Node(data)
        node.next = self.top.next
        self.top.next = node
        self.count += 1
    # Remove and retrieve the top item from the stack
    def popValue(self):
        if self.checkEmpty():
            raise Exception("Attempting to pop from an empty stack")
        remove_item = self.top.next
        self.top.next = self.top.next.next
        self.count -= 1
        return remove_item.data
# Driver Code
if __name__ == "__main__":
    my_stack = Stack()
    for num in range(1, 11):
        my_stack.pushValue(num)
    print(f"My Stack: {my_stack}")
 
    for _ in range(1, 6):
        removed = my_stack.popValue()
        print(f"Removed Item: {removed}")
    print(f"My Stack: {my_stack}")

Output

My Stack: 10->9->8->7->6->5->4->3->2->1
Removed Item: 10
Removed Item: 9
Removed Item: 8
Removed Item: 7
Removed Item: 6
My Stack: 5->4->3->2->1

Advantages of Stack in Python

• Stacks are straightforward data structures characterized by clear operations, making them user-friendly and intuitive.
• With a time complexity of O(1), stacks excel in adding and removing elements efficiently.
• The stack data structure proves beneficial for reversing element sequences.
• Furthermore, stacks find applications in implementing undo/redo functionalities within software applications.

Disadvantages of Stack in Python

• The limitation on the size of a stack poses a challenge; once it reaches its capacity, additional elements cannot be accommodated.
• Beyond the topmost element, stacks do not offer swift access to other elements.
• Searching within stacks can be inefficient since you must sequentially pop elements until you locate the desired item.

Conclusion

Stacks in Python offer efficient LIFO operations, with implementations using lists, and collections. deque, and the queue module. While efficient for certain tasks like reversing sequences, they have size limitations and lack direct access beyond the top element.