Stack Data Structure

A Last In, First Out (LIFO) data structure where elements are added and removed from the same end, called the top.

Definition

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last element added to the stack will be the first one to be removed. Think of it like a stack of plates - you can only add or remove plates from the top.

Key Properties

LIFO Principle

Last In, First Out - most recent element is accessed first

Single Access Point

Only the top element can be accessed

Limited Operations

Only push, pop, peek, and isEmpty operations

Dynamic Size

Can grow and shrink as needed

Memory Efficient

Only stores necessary elements

Simple Implementation

Easy to implement using arrays or linked lists

Stack Operations

Push(element)

Adds an element to the top of the stack

Time Complexity: O(1)

Pop()

Removes and returns the top element

Time Complexity: O(1)

Peek() / Top()

Returns the top element without removing it

Time Complexity: O(1)

isEmpty()

Checks if the stack is empty

Time Complexity: O(1)

Python Code Examples

Python Implementation

# Stack implementation using List
class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """Add element to the top"""
        self.items.append(item)

    def pop(self):
        """Remove and return top element"""
        if self.is_empty():
            return "Stack is empty"
        return self.items.pop()

    def peek(self):
        """Return top element without removing"""
        if self.is_empty():
            return "Stack is empty"
        return self.items[-1]

    def is_empty(self):
        """Check if stack is empty"""
        return len(self.items) == 0

    def size(self):
        """Return stack size"""
        return len(self.items)

    def display(self):
        """Display stack from top to bottom"""
        return self.items[::-1]

# Usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print("Stack:", stack.display())  # [30, 20, 10]
print("Top element:", stack.peek())  # 30
print("Popped:", stack.pop())  # 30
print("Stack after pop:", stack.display())  # [20, 10]

# Using built-in list as stack
stack_list = []
stack_list.append(1)  # push
stack_list.append(2)
stack_list.append(3)
print(stack_list.pop())  # 3 (pop)
print(stack_list[-1])  # 2 (peek)

# Using collections.deque (more efficient)
from collections import deque
deque_stack = deque()
deque_stack.append(1)  # push
deque_stack.append(2)
deque_stack.append(3)
print(deque_stack.pop())  # 3 (pop)
print(deque_stack[-1])  # 2 (peek)

# Stack application: Balanced parentheses checker
def is_balanced(expression):
    """Check if parentheses are balanced using stack"""
    stack = []
    opening = ['(', '[', '{']
    closing = [')', ']', '}']
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in closing:
            if not stack:
                return False
            last_opening = stack.pop()
            if opening.index(last_opening) != closing.index(char):
                return False
    
    return len(stack) == 0

# Test balanced parentheses
print(is_balanced("()[]{}"))  # True
print(is_balanced("([)]"))    # False
print(is_balanced("{[()]}"))  # True

Common Use Cases

Function Call Management

Call stack in programming languages

Expression Evaluation

Infix to postfix conversion

Undo Operations

Storing previous states

Browser History

Back button functionality

Balanced Parentheses

Checking syntax validity

Memory Management

Stack-based memory allocation

Backtracking Algorithms

DFS, maze solving

Compiler Design

Syntax analysis and parsing