Stack in Python

What is a Stack?

A stack is a data structure operating on the Last In, First Out (LIFO) principle. This means that the last element added to the stack is first removed. Consider a stack of plates:

• The last placed plate is the first one you remove.
• You can only come to the top plate without dislodging anything else.

Key Operations of a Stack

1. Push:

• Adds an element to the top of the stack.
• Example: If the stack is [10, 20] and you push 30, the stack becomes [10, 20, 30].

2. Pop:

• Removes and returns the top element of the stack.
• Example: If the stack is [10, 20, 30] and you pop, it returns 30 and the stack becomes [10, 20].

3. Peek (or Top):

• Retrieves the top element of the stack without removing it.
• Example: If the stack is [10, 20, 30], the top element is 30.

4. IsEmpty:

• Checks if the stack contains any element.
• Example: If the stack is [], it is empty; otherwise, it is not.

Why Use a Stack?

Stacks are simple yet powerful and are widely used in:

• Programming: Managing function calls, undo/redo actions.
• Algorithms: DFS (Depth-First Search), evaluating mathematical expressions.
• Data Processing: Balance symbols (parentheses, brackets), reverse a word.

Implementing Stacks in Python

Python does not have an in-built class Stack, however you can develop one using:

1. Lists, basic and direct.
2. collections.deque (optimized for add/remove operations).
3. queue.LifoQueue (thread-safe for multi-threaded programs).

1. Stack Using Lists

Lists in Python support methods like append() and pop() to mimic stack behavior. However, they are not specifically designed for stacks.

Code Example:

stack = []  # Initialize an empty stack

# Push elements onto the stack
stack.append(10)  # Stack: [10]
stack.append(20)  # Stack: [10, 20]
stack.append(30)  # Stack: [10, 20, 30]
print("Stack after pushes:", stack)

# Pop an element from the stack
popped_element = stack.pop()  # Removes 30
print("Popped element:", popped_element)  # Outputs: 30
print("Stack after pop:", stack)  # Outputs: [10, 20]

# Peek the top element
if stack:
    top_element = stack[-1]  # Get the last element
    print("Top element:", top_element)  # Outputs: 20

# Check if the stack is empty
print("Is the stack empty?", len(stack) == 0)  # Outputs: False

Limitations:

• Lists are dynamic arrays. When they resize, operations such as append() may take longer.
• Inefficiency: It suffers performance degradation upon many resize or big stack.

2. Stack Using

A deque is a double-ended queue, which is ideal for stacks because:

• It is optimized for appending and popping elements from both ends.
• Implemented as a doubly linked list, hence making operations quite fast.

Code Example:

from collections import deque

stack = deque()  # Initialize an empty stack

# Push elements
stack.append(10)  # Stack: deque([10])
stack.append(20)  # Stack: deque([10, 20])
stack.append(30)  # Stack: deque([10, 20, 30])
print("Stack after pushes:", stack)

# Pop an element
popped_element = stack.pop()  # Removes 30
print("Popped element:", popped_element)  # Outputs: 30
print("Stack after pop:", stack)  # Outputs: deque([10, 20])

# Peek the top element
if stack:
    top_element = stack[-1]
    print("Top element:", top_element)  # Outputs: 20

# Check if the stack is empty
print("Is the stack empty?", len(stack) == 0)  # Outputs: False

Advantages:

• Fast and memory-efficient for stack operations.
• More appropriate for stacks than list.

3. Stack Using queue.LifoQueue

The queue.LifoQueue class provides a thread-safe stack implementation. This is especially useful in multi-threaded environments.

Code Example:

from queue import LifoQueue

stack = LifoQueue()  # Initialize an empty stack

# Push elements
stack.put(10)  # Stack: [10]
stack.put(20)  # Stack: [10, 20]
stack.put(30)  # Stack: [10, 20, 30]
print("Stack size after pushes:", stack.qsize())  # Outputs: 3

# Pop an element
popped_element = stack.get()  # Removes 30
print("Popped element:", popped_element)  # Outputs: 30
print("Stack size after pop:", stack.qsize())  # Outputs: 2

# Check if the stack is empty
print("Is the stack empty?", stack.empty())  # Outputs: False

Advantages:

• Thread-safe for concurrent programs.
• Built-in methods (put(), get(), empty()) make it robust.

Disadvantages:

• Slightly slower due to thread-safety overhead.

Choosing the Right Implementation

• Use a list for basic stack operations in single-threaded, non-performance-critical applications.
• Use deque for better performance and memory efficiency in most cases.
• Use LifoQueue when working in multi-threaded environments.

Real-World Applications of Stacks

1. Expression Evaluation:
   • Parsing and evaluating mathematical expressions.
   • Example: Infix to postfix conversion.
2. Function Call Stack:
   • Stacks are used in programming languages to track the function calls and local variables.
   • Example: Recursive function calls.
3. Backtracking:
   • Algorithms such as depth-first search use stacks to traverse the paths.
   • Example: Maze solving or puzzles.
4. Undo Operations:
   • Text editors maintain a stack to keep track of the user actions to provide the undo/redo feature.
5. Balanced Parentheses:
   • It is used to check if an expression contains balanced brackets or parentheses.
   • For instance: ((a + b) * c) is balanced but (a + b)) isn’t.

Conclusion

• A stack is a versatile and widely-used data structure.
• In Python:
  • list is simple but less efficient for large-scale operations.
  • deque is optimized and more efficient.
  • LifoQueue is for thread-safe applications.