Lecture 7: Stack and Queues in Python | DSA in Python

Every programmer encounters problems where data must be processed in a specific, chronological order. Managing history in a browser tab or scheduling background tasks in web applications requires specific data structures.

What is Stack in Python?

A stack is a linear data structure that functions on a specific, strict sequence protocol. It follows the Last-In-First-Out (LIFO) principle. This means the element added most recently is always the first one to be removed.

Think of a stack like a narrow container or a bottle filled with tennis balls. You can only add or remove items from the single open end at the top.

Basic Stack Operations

To utilise a stack effectively within DSA concepts, you must understand its five primary operations:

• Push: Adds a new item directly to the top of the container.

• Pop: Removes and returns the top-most item. If the container is completely vacant, it triggers an underflow condition.

• Peek/Top: Allows you to look at the top-most item without removing it from the structure.

• isEmpty: Returns a boolean value checking whether the structure contains zero items.

• isFull: Checks whether the structure has reached its maximum predefined capacity limit.

How to Implement Stack in Python?

While Python does not have a built-in standalone stack class, you can easily implement one. The most common approaches involve using standard lists or dynamic linked lists.

1. Implementation Using a Standard List

A standard list works perfectly for structural replication because it allows fast end-insertions and removals.

The table below provides a quick operational mapping for list-based stacks:

Before writing custom code, look at how easily you can manage data with a list wrapped inside a professional class format:

Python

class StandardStack:
    def __init__(self):
        self.container = []

    def push(self, item):
        self.container.append(item)

    def pop(self):
        if not self.is_empty():
            return self.container.pop()
        return "Underflow Condition"

    def peek(self):
        if not self.is_empty():
            return self.container[-1]
        return None

    def is_empty(self):
        return len(self.container) == 0

2. Implementation Using a Linked List

When working with a low-level Python stack implementation, a linked list offers dynamic memory allocation without resizing overhead. Instead of operating at the end, we perform insertions and deletions at the head node (top) to maintain optimal performance.

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.top = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
    def pop(self):
        if self.top is None:
            return "Underflow Condition"
        popped_value = self.top.data
        self.top = self.top.next
        return popped_value

What is Queue in Python?

Unlike a stack, a queue data structure operates on the First-In-First-Out (FIFO) principle. It replicates a real-world queue, such as a line at a supermarket checkout. The person who arrives first gets served first, and new arrivals join the back of the line.

A standard queue uses two pointers to manage data flow:

• Front: Points to the first or oldest element in the structure (used for deletion).

• Rear/Back: Points to the last or newest element added to the structure (used for insertion).

Primary Queue Operations

Managing a sequence requires precise control over both entry and exit points:

• Enqueue: Adds an item to the rear end of the line.

• Dequeue: Removes and returns the item sitting at the front of the line.

• Front/Peek: Returns the element at the front position without deleting it.

How to Implement Queue in Python?

Implementing a queue requires careful design. Using a simple Python list for structural management can slow down operations, as removing an item from index 0 shifts all remaining elements in memory.

1. Implementation Using a List (With Front Pointer)

To avoid shifting elements during deletion, maintain a dedicated tracking index for the front pointer instead of deleting items physically.

The following list demonstrates how indices track elements while optimizing performance:

• Initial State: [Element A, Element B, Element C] (Front pointer at index 0)

• Dequeue Operation: Front pointer moves to index 1.

• Current State: [Element A (ignored), Element B, Element C] (Front pointer at index 1)

Python

class ListQueue:
    def __init__(self):
        self.queue = []
        self.front_pointer = 0

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if self.front_pointer >= len(self.queue):
            return "Queue is Empty"
        item = self.queue[self.front_pointer]
        self.front_pointer += 1
        return item

2. Implementation Using a Linked List

A linked list provides a highly efficient structure for queues. By tracking both head and tail nodes, insertions at the back and removals from the front run in constant time.

Python

class QueueNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = QueueNode(data)
        if self.rear is None:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return "Queue is Empty"
        temp = self.front
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return temp.data

What are Different Types of Queues?

Depending on your production requirements, a standard pipeline might not fit every scenario. You can use several specialised variations of the queue structure:

• Circular Queue: The last position connects back to the first position, creating a circle to reuse empty slots left by dequeued items.

• Priority Queue: Each element has an associated priority value. Elements with higher priority are dequeued before lower-priority ones, regardless of arrival order.

• Double-Ended Queue (Deque): Allows insertions and deletions from both the front and rear ends.

Uses of Stack and Queue in Python

Both of these structures are fundamental to system architecture and daily computational operations.

Stack Applications

• System Call Memory: Tracks active subroutines, tracking execution states when functions run recursively.

• Undo/Redo Mechanics: Text editors save your changes in a historical stack, popping items whenever you trigger a revert command.

• Browser History: Pressing the back button pops your most recent URL, returning you to the previous site.

Queue Applications

• Asynchronous Submissions: Online learning portals use backend worker lines to queue code submissions, validating scripts in order without crashing servers.

• Operating System Scheduling: CPU tasks and print jobs wait in shared memory lines to be processed in order.

• Network Buffering: Routers queue incoming packets to prevent data loss during traffic spikes.

Common DSA Interview Problems

Let us review a classic interview problem: verifying valid brackets in an expression using a stack.

Problem: Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if opening brackets are closed by the same type of brackets in the correct order.

Python

def isValid(s: str) -> bool:
    if len(s) % 2 != 0:
        return False
       
    bracket_stack = []
    mapping = {")": "(", "}": "{", "]": "["}
   
    for char in s:
        if char in mapping.values():
            bracket_stack.append(char)
        elif char in mapping:
            if not bracket_stack or bracket_stack.pop() != mapping[char]:
                return False
        else:
            return False
           
    return len(bracket_stack) == 0