DSA Series Chapter 5 : STACKS IN PYTHON — Using Arrays & Linked Lists

on

 


 [Follow here] for daily coding insights.

DSA Series  Chapter 5 : STACKS IN PYTHON — Using Arrays & Linked Lists

1. STACK IMPLEMENTATION USING ARRAY (PYTHON LIST)

Concept

In Python, an array-based stack can be efficiently implemented using the built-in list, because:

  • append() → behaves like push

  • pop() → behaves like pop

  • Both operations are O(1) amortized

Python Code – Array Based Stack

class ArrayStack:
    def __init__(self):
        self.stack = []   # internal list

    def push(self, item):
        self.stack.append(item)   # O(1)
        print(f"Pushed {item}")

    def pop(self):
        if self.is_empty():
            print("Stack Underflow!")
            return None
        return self.stack.pop()   # O(1)

    def peek(self):
        if self.is_empty():
            print("Stack is Empty!")
            return None
        return self.stack[-1]

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

    def size(self):
        return len(self.stack)

    def display(self):
        print("Stack (top → bottom):", self.stack[::-1])

Example Usage

s = ArrayStack()
s.push(10)
s.push(20)
s.push(30)
s.display()
print("Popped:", s.pop())
print("Top Element:", s.peek())

Time Complexity

Operation Complexity
Push O(1)
Pop O(1)
Peek O(1)
Display O(n)

2. STACK IMPLEMENTATION USING LINKED LIST

Concept

A linked-list stack uses:

  • Each node → stores data + reference to next

  • top → points to the first node (top of stack)

  • Push & Pop operations occur at the head for O(1) complexity

Used when:

  • Dynamic size is needed

  • No memory wastage

Python Code – Linked List Based Stack

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

# Linked List Stack class
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
        print(f"Pushed {data}")

    def pop(self):
        if self.is_empty():
            print("Stack Underflow!")
            return None
        popped = self.top.data
        self.top = self.top.next
        return popped

    def peek(self):
        if self.is_empty():
            print("Stack is Empty!")
            return None
        return self.top.data

    def is_empty(self):
        return self.top is None

    def display(self):
        print("Stack (top → bottom): ", end="")
        temp = self.top
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
        print()

Example Usage

s = LinkedListStack()
s.push(5)
s.push(15)
s.push(25)
s.display()
print("Popped:", s.pop())
print("Top Element:", s.peek())

Time Complexity

Operation Complexity
Push O(1)
Pop O(1)
Peek O(1)
Display O(n)

 ARRAY vs LINKED LIST STACK — Comparison Table

----------------------------------------------------

Feature Array (List) Linked List
Dynamic Size Yes, but slower expansion Fully dynamic
Memory usage Lower Higher (Node overhead)
Implementation Simple Slightly complex
Overflow Possible if memory full Almost none
Speed Faster indexing No indexing

When to Use Which?

✔ Use ArrayStack if:

  • You need fast performance

  • Size is known or moderate

  • Lower memory usage is required

✔ Use LinkedListStack if:

  • Size changes frequently

  • No memory wastage allowed

  • Constant-time insertions/removals required

STACK APPLICATIONS IN PYTHON

Labels: DSA – Stacks, Stack Applications, Python

Description:

This post covers three major applications of stacks used in real-world software systems and competitive programming: DFS traversal, expression conversion, and parenthesis validation, explained with full Python code.

---------------------------------------------------

1. APPLICATION OF STACK — Depth First Search (DFS)

Concept

DFS is normally recursive.
But recursion internally uses call stack.

We can convert DFS into iterative DFS using an explicit stack.

Used in:

  • Graph traversal

  • Path finding

  • Cycle detection

  • Topological sorting

  • Network connectivity

Python Code – Iterative DFS using Stack

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)

            # Push neighbors in reverse order
            # so that left-most gets processed first
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

Example Usage

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs_iterative(graph, 'A')

2. APPLICATION OF STACK — Expression Conversion

Infix → Postfix (using Stack)

Concept

Infix expression: A + B * C
Postfix expression: A B C * +

Stack is used to:

  • Store operators

  • Maintain precedence

  • Ensure correct order of operations

Precedence & Associativity

Operator Precedence Associativity
^ Highest Right to Left
*, / Middle Left to Right
+, - Lowest Left to Right

Python Code – Infix → Postfix Conversion

def precedence(op):
    if op == '^':
        return 3
    if op in ['*', '/']:
        return 2
    if op in ['+', '-']:
        return 1
    return 0

def infix_to_postfix(expression):
    stack = []
    postfix = ""

    for char in expression:
        if char.isalnum():   # operand
            postfix += char

        elif char == '(':
            stack.append(char)

        elif char == ')':
            while stack and stack[-1] != '(':
                postfix += stack.pop()
            stack.pop()

        else:  # operator
            while (stack and precedence(stack[-1]) >= precedence(char)
                   and char != '^'):  # ^ is right associative
                postfix += stack.pop()
            stack.append(char)

    # pop remaining operators
    while stack:
        postfix += stack.pop()

    return postfix

Example Usage

exp = "A+(B*C-(D/E^F)*G)*H"
print("Postfix:", infix_to_postfix(exp))

3. APPLICATION OF STACK — Parenthesis Checking

Concept

Used in:

  • Compilers

  • Expression validation

  • Syntax checking in IDEs

  • XML/HTML tag matching

We check the matching of:

  • ()

  • {}

  • []

Python Code – Balanced Parentheses

def is_balanced(expression):
    stack = []
    pairs = {')': '(', '}': '{', ']': '['}

    for ch in expression:
        if ch in "({[":
            stack.append(ch)
        elif ch in ")}]":
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()

    return len(stack) == 0

Example Usage

print(is_balanced("{(A+B)*[C-D]}"))   # True
print(is_balanced("{(A+B]*C}"))       # False

SUMMARY — Why Stack is Powerful

Stacks simplify:

  • Graph traversal

  • Expression parsing

  • Compiler design

  • Undo/redo operations

  • Backtracking algorithms

Understanding stack-based operations is essential for higher-level algorithms.

ALSO CHECK 

DS(Data Structure) Python&C Edition

DSA Series Chapter 1 Time & Space Complexity ( C Edition)

DSA Series Chapter 2 Arrays  (C Version)


DSA Series Chapter 2 Arrays  (Python Version)

DSA Series Chapter 3 Strings (C Version)


DSA Series Chapter 3 Strings (Python Version)


DSA Series Chapter 4 Linked Lists (Python Version)


DSA Series Chapter 4 Linked Lists (C Version)


DSA Series Chapter 5 Stacks (Python Version)


DSA Series Chapter 5  Stacks  (C Version)









Tail Recursion Optimization: How Compilers Convert Recursion Into Iteration


Advanced Recursion: Memoization vs. Tabulation — The Deep Optimization Blueprint for Professionals


Advanced Sorting Algorithms: Merge Sort Internals — Merge Tree, Cache Behavior & Real Cost Analysis


Enjoyed this post? [Follow here] for daily coding insights.

Comments

Post a Comment