Learning Paths/Foundations/Stacks & Queues

Stacks & Queues

Stacks and queues are fundamental data structures with specific access patterns. This module covers their implementations, operations, and common applications in algorithm design.

Module Contents

Learning Resources

Introduction to Stacks & Queues

Stacks and queues are abstract data types that serve as collections of elements with specific access patterns. They are fundamental in algorithm design and system architecture.

Stack

A stack is a Last-In-First-Out (LIFO) data structure. Elements are added and removed from the same end, called the "top" of the stack.


    │       │
    │   C   │ ← Top (Last In, First Out)
    │   B   │
    │   A   │
    └───────┘

Queue

A queue is a First-In-First-Out (FIFO) data structure. Elements are added at one end (rear) and removed from the other end (front).


    ┌───┬───┬───┐
    │ A │ B │ C │
    └───┴───┴───┘
      ↑       ↑
    Front    Rear
    (First In, First Out)

Common Operations

Data Structure	Operations	Time Complexity
Stack	push(element)	O(1)
	pop()	O(1)
	peek()	O(1)
Queue	enqueue(element)	O(1)
	dequeue()	O(1)
	peek()	O(1)

Stack Implementation

Java Implementation

// Stack implementation in Java using an array
class Stack {
    private int maxSize;
    private int[] stackArray;
    private int top;
    
    // Constructor
    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1; // Initialize top of stack
    }
    
    // Add element to top of stack
    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack is full");
            return;
        }
        stackArray[++top] = value;
    }
    
    // Remove element from top of stack
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        }
        return stackArray[top--];
    }
    
    // Return element at top of stack
    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        }
        return stackArray[top];
    }
    
    // Check if stack is empty
    public boolean isEmpty() {
        return (top == -1);
    }
    
    // Check if stack is full
    public boolean isFull() {
        return (top == maxSize - 1);
    }
}

// Using Java's built-in Stack class
import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        
        // Push elements
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        // Peek at the top element
        System.out.println("Top element: " + stack.peek()); // Output: 30
        
        // Pop elements
        System.out.println("Popped: " + stack.pop()); // Output: 30
        System.out.println("Popped: " + stack.pop()); // Output: 20
        
        // Check if empty
        System.out.println("Is empty: " + stack.isEmpty()); // Output: false
    }
}

Python Implementation

# Stack implementation in Python using a list
class Stack:
    def __init__(self):
        self.stack = []
    
    # Add element to top of stack
    def push(self, item):
        self.stack.append(item)
    
    # Remove element from top of stack
    def pop(self):
        if self.is_empty():
            return "Stack is empty"
        return self.stack.pop()
    
    # Return element at top of stack
    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return self.stack[-1]
    
    # Check if stack is empty
    def is_empty(self):
        return len(self.stack) == 0
    
    # Return the size of the stack
    def size(self):
        return len(self.stack)

# Example usage
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)

print("Top element:", stack.peek())  # Output: 30
print("Popped:", stack.pop())        # Output: 30
print("Popped:", stack.pop())        # Output: 20
print("Is empty:", stack.is_empty()) # Output: False

# Using Python's built-in list as a stack
stack = []
stack.append(10)  # push
stack.append(20)
stack.append(30)

print("Top element:", stack[-1])  # peek
print("Popped:", stack.pop())     # pop
print("Popped:", stack.pop())
print("Is empty:", len(stack) == 0)

Queue Implementation

Java Implementation

// Queue implementation in Java using an array
class Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int nItems;
    
    // Constructor
    public Queue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }
    
    // Add element to rear of queue
    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full");
            return;
        }
        
        // Circular queue implementation
        if (rear == maxSize - 1) {
            rear = -1;
        }
        
        queueArray[++rear] = value;
        nItems++;
    }
    
    // Remove element from front of queue
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        
        int temp = queueArray[front++];
        
        // Circular queue implementation
        if (front == maxSize) {
            front = 0;
        }
        
        nItems--;
        return temp;
    }
    
    // Return element at front of queue
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return -1;
        }
        return queueArray[front];
    }
    
    // Check if queue is empty
    public boolean isEmpty() {
        return (nItems == 0);
    }
    
    // Check if queue is full
    public boolean isFull() {
        return (nItems == maxSize);
    }
    
    // Return the size of the queue
    public int size() {
        return nItems;
    }
}

// Using Java's built-in Queue interface
import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        
        // Add elements
        queue.add(10);
        queue.add(20);
        queue.add(30);
        
        // Peek at the front element
        System.out.println("Front element: " + queue.peek()); // Output: 10
        
        // Remove elements
        System.out.println("Removed: " + queue.remove()); // Output: 10
        System.out.println("Removed: " + queue.remove()); // Output: 20
        
        // Check if empty
        System.out.println("Is empty: " + queue.isEmpty()); // Output: false
    }
}

Python Implementation

# Queue implementation in Python using a list
class Queue:
    def __init__(self):
        self.queue = []
    
    # Add element to rear of queue
    def enqueue(self, item):
        self.queue.append(item)
    
    # Remove element from front of queue
    def dequeue(self):
        if self.is_empty():
            return "Queue is empty"
        return self.queue.pop(0)  # O(n) operation, not efficient for large queues
    
    # Return element at front of queue
    def peek(self):
        if self.is_empty():
            return "Queue is empty"
        return self.queue[0]
    
    # Check if queue is empty
    def is_empty(self):
        return len(self.queue) == 0
    
    # Return the size of the queue
    def size(self):
        return len(self.queue)

# Example usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print("Front element:", queue.peek())    # Output: 10
print("Removed:", queue.dequeue())       # Output: 10
print("Removed:", queue.dequeue())       # Output: 20
print("Is empty:", queue.is_empty())     # Output: False

# Using Python's collections.deque for efficient queue operations
from collections import deque

queue = deque()
queue.append(10)      # enqueue
queue.append(20)
queue.append(30)

print("Front element:", queue[0])    # peek
print("Removed:", queue.popleft())   # dequeue (O(1) operation)
print("Removed:", queue.popleft())
print("Is empty:", len(queue) == 0)

Applications

Stacks and queues are used in a wide variety of algorithms and applications. Here are some common use cases:

Stack Applications

Expression evaluation and conversion (infix to postfix)
Backtracking algorithms (maze solving, game trees)
Function call management (call stack)
Undo mechanisms in text editors
Balanced parentheses checking
Depth-first search in graphs

Queue Applications

Breadth-first search in graphs
Task scheduling
Print job spooling
Handling of requests on a single shared resource (printer, CPU)
Buffering for data streams
Implementing other data structures like stacks and priority queues

Example: Balanced Parentheses

A classic application of stacks is checking for balanced parentheses in an expression.

// Java implementation to check for balanced parentheses
public boolean isBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            // Push opening brackets onto the stack
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            // For closing brackets, check if stack is empty
            if (stack.isEmpty()) {
                return false;
            }
            
            // Pop the top element and check if it matches
            char top = stack.pop();
            if ((c == ')' && top != '(') || 
                (c == ']' && top != '[') || 
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    
    // If stack is empty, all brackets are matched
    return stack.isEmpty();
}

Practice Problems

Apply your knowledge of stacks and queues by solving these carefully selected problems:

1. Valid Parentheses

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

EasyStackString

Solve this problem →

2. Implement Queue using Stacks

Implement a first-in-first-out (FIFO) queue using only two stacks.

EasyStackDesign

Solve this problem →

3. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

MediumStackDesign

Solve this problem →

4. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

MediumStackMath

Solve this problem →

Previous: Linked Lists Next: Basic Sorting