Stacks

Stacks

A stack is a linear data structure that follows the LIFO (Last-In, First-Out) principle. All insertions and deletions occur at the "top" of the stack, enabling constant-time operations.

Think of a stack of plates: you can only add or remove plates from the top.

Stack Operations

graph LR
    A[Empty Stack] --> B[Push A]
    B --> C[Push B]
    C --> D[Push C]
    D --> E[Peek: C]
    E --> F[Pop: C]
    F --> G[Pop: B]
    G --> H[Pop: A]
    H --> I[Empty Stack]

    style A fill:#f9f9f9
    style I fill:#f9f9f9
    style E fill:#e8f5e8
    style F fill:#ffe8e8
    style G fill:#ffe8e8
    style H fill:#ffe8e8

Core Operations

graph TD
    A[Stack Operations] --> B[Push]
    A --> C[Pop]
    A --> D[Peek]
    A --> E[isEmpty]

    B --> B1[Add to top]
    C --> C1[Remove from top]
    D --> D1[View top element]
    E --> E1[Check if empty]

    style B fill:#c8e6c9
    style C fill:#ffcdd2
    style D fill:#e1f5fe
    style E fill:#fff3e0

Key Properties

• LIFO Access: Last element added is first removed
• Single Access Point: Only top element is accessible
• Constant Time: All operations are O(1)

Applications

graph TD
    A[Stack Applications] --> B[Function Calls]
    A --> C[Expression Evaluation]
    A --> D[Undo Operations]
    A --> E[Backtracking]

    B --> B1[Call Stack Management]
    C --> C1[Infix/Postfix Conversion]
    D --> D1[Text Editor Undo]
    E --> E1[Maze Solving]

    style A fill:#e3f2fd
    style B fill:#c8e6c9
    style C fill:#fff3e0
    style D fill:#f3e5f5
    style E fill:#e8f5e8

Time & Space Complexity

Operation	Time	Space	Description
push(item)	O(1)	O(1)	Add to top
pop()	O(1)	O(1)	Remove from top
peek()	O(1)	O(1)	View top element
isEmpty()	O(1)	O(1)	Check if empty

All operations are O(1) because they only access the top element. Overall space complexity is O(n) for n elements.

Implementation

Array-based: Fixed/dynamic array with top pointer - good cache locality

Linked List: Head as top - true dynamic sizing, pointer overhead

Built-ins: Use language-provided implementations (queues, deques) for best performance

JavaKotlinTypeScriptDartSwiftPython

import java.util.Stack;

Stack<String> stack = new Stack<>();
stack.push("first");           // O(1)
stack.push("second");          // O(1)
String top = stack.peek();     // O(1)
String popped = stack.pop();   // O(1)
boolean empty = stack.isEmpty(); // O(1)

import java.util.Stack

val stack = Stack<String>()
stack.push("first")            // O(1)
stack.push("second")           // O(1)
val top = stack.peek()         // O(1)
val popped = stack.pop()       // O(1)
val empty = stack.isEmpty()    // O(1)

// npm install @datastructures-js/stack
import { Stack } from '@datastructures-js/stack';

const stack = new Stack<string>();
stack.push("first");                 // O(1)
stack.push("second");                // O(1)
const top = stack.peek();            // O(1)
const popped = stack.pop();          // O(1)
const empty = stack.isEmpty();       // O(1)

// Deque provides efficient stack operations
import 'package:collection/collection.dart';

final stack = DoubleLinkedQueue<String>();
stack.addLast("first");              // O(1)
stack.addLast("second");             // O(1)
String top = stack.last;             // O(1)
String popped = stack.removeLast();  // O(1)
bool empty = stack.isEmpty;          // O(1)

// Deque provides efficient stack operations
import Collections

var stack = Deque<String>()
stack.append("first")                // O(1)
stack.append("second")               // O(1)
let top = stack.last                 // O(1)
let popped = stack.removeLast()      // O(1)
let empty = stack.isEmpty            // O(1)

# deque provides efficient stack operations
from collections import deque

stack = deque()
stack.append("first")                # O(1)
stack.append("second")               # O(1)
top = stack[-1]                      # O(1)
popped = stack.pop()                 # O(1)
empty = len(stack) == 0              # O(1)

Example: Balanced Parentheses

Uses LIFO property to match opening/closing brackets. Push opening brackets, pop when finding closing brackets.

JavaKotlinTypeScriptDartSwiftPython

public static boolean isBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    for (char ch : s.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if ((ch == ')' && open != '(') ||
                (ch == ']' && open != '[') ||
                (ch == '}' && open != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

import java.util.Stack

fun isBalanced(s: String): Boolean {
    val stack = Stack<Char>()
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    for (ch in s) {
        when (ch) {
            '(', '[', '{' -> stack.push(ch)
            ')', ']', '}' -> {
                if (stack.isEmpty() || stack.pop() != pairs[ch]) {
                    return false
                }
            }
        }
    }
    return stack.isEmpty()
}

import { Stack } from '@datastructures-js/stack';

function isBalanced(s: string): boolean {
    const stack = new Stack<string>();
    const pairs: Record<string, string> = {')': '(', ']': '[', '}': '{'};
    for (const ch of s) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);
        } else if (ch === ')' || ch === ']' || ch === '}') {
            if (stack.isEmpty() || stack.pop() !== pairs[ch]) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

import 'package:collection/collection.dart';

bool isBalanced(String s) {
    final stack = DoubleLinkedQueue<String>();
    Map<String, String> pairs = {')': '(', ']': '[', '}': '{'};
    for (int i = 0; i < s.length; i++) {
        String ch = s[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.addLast(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (stack.isEmpty || stack.removeLast() != pairs[ch]) {
                return false;
            }
        }
    }
    return stack.isEmpty;
}

import Collections

func isBalanced(_ s: String) -> Bool {
    var stack = Deque<Character>()
    let pairs: [Character: Character] = [')': '(', ']': '[', '}': '{']
    for ch in s {
        if ch == '(' || ch == '[' || ch == '{' {
            stack.append(ch)
        } else if ch == ')' || ch == ']' || ch == '}' {
            if stack.isEmpty || stack.removeLast() != pairs[ch] {
                return false
            }
        }
    }
    return stack.isEmpty
}

from collections import deque

def is_balanced(s: str) -> bool:
    pairs = {')':'(', ']':'[', '}':'{'}
    stack = deque()
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack