Stack and Queue Applications

Generated on 2025-07-10 02:09:54 Algorithm Cheatsheet for Technical Interviews

---

Stack & Queue Applications Cheatsheet

1. Quick Overview

• Stack: LIFO (Last-In, First-Out) data structure. Use when you need to track a history of operations, reverse order, or handle nested structures.
• Queue: FIFO (First-In, First-Out) data structure. Use when you need to process items in the order they arrived, handle asynchronous tasks, or manage shared resources.

2. Time & Space Complexity

Operation	Stack (Array/Linked List)	Queue (Array/Linked List)	Queue (Deque)
Push/Enqueue	O(1)	O(1)	O(1)
Pop/Dequeue	O(1)	O(1)	O(1)
Peek/Front	O(1)	O(1)	O(1)
Search	O(n)	O(n)	O(n)
Space Complexity	O(n)	O(n)	O(n)

3. Implementation

Python

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

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None  # Or raise an exception

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

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


# Queue (using deque for O(1) enqueue/dequeue)
from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

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

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

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        else:
            return None  # Or raise an exception

    def front(self):
        if not self.is_empty():
            return self.items[0]
        else:
            return None

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

Java

// Stack
import java.util.Stack;

// Queue
import java.util.LinkedList;
import java.util.Queue;
import java.util.Deque;
import java.util.ArrayDeque;

public class StackQueue {

    public static void main(String[] args) {
        // Stack Example
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        System.out.println("Stack Pop: " + stack.pop()); // Output: 2

        // Queue Example
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        queue.offer(2);
        System.out.println("Queue Dequeue: " + queue.poll()); // Output: 1

        // Deque as Queue
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(1);
        deque.offer(2);
        System.out.println("Deque Dequeue: " + deque.poll()); // Output: 1
    }
}

C++

#include <iostream>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

int main() {
    // Stack Example
    stack<int> s;
    s.push(1);
    s.push(2);
    cout << "Stack Pop: " << s.top() << endl; // Output: 2
    s.pop();

    // Queue Example
    queue<int> q;
    q.push(1);
    q.push(2);
    cout << "Queue Dequeue: " << q.front() << endl; // Output: 1
    q.pop();

    // Deque as Queue
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    cout << "Deque Dequeue: " << dq.front() << endl; // Output: 1
    dq.pop_front();

    return 0;
}

4. Common Patterns

Pattern	Stack	Queue	Example
Reversal	Reverse order of elements.	Maintain order of elements.	Reversing a string, undo operations in a text editor.
Backtracking	Keep track of previous states.	Not applicable.	Solving mazes, generating permutations.
Parenthesis Matching	Validating balanced parentheses.	Not applicable.	Checking if (a + b) * {c - d} is balanced.
Expression Evaluation	Evaluating postfix expressions.	Not applicable.	Evaluating 2 3 + 5 *.
Level Order Traversal	Not typically used directly.	Traversing a tree level by level.	Binary tree level order traversal.
Breadth-First Search (BFS)	Not typically used directly.	Exploring a graph layer by layer.	Finding the shortest path in an unweighted graph.
Task Scheduling	Not typically used.	Processing tasks in arrival order.	Print jobs in a printer queue.
Resource Management	Not typically used.	Managing shared resources.	Handling requests to a server.
Sliding Window	Not typically used.	Maintain a fixed-size window of data.	Finding the maximum element in each sliding window of an array (using Deque for O(1) max retrieval).

5. Pro Tips

• Stack Overflow: Be mindful of stack depth, especially in recursive functions. Use iterative solutions when possible to avoid stack overflow errors.
• Queue vs. Deque: Use collections.deque (Python) or ArrayDeque (Java) or deque (C++) for queues that require O(1) enqueue and dequeue operations. LinkedList in Java can be used for queues, but ArrayDeque is generally faster.
• Circular Queue: For fixed-size queues, consider implementing a circular queue to avoid shifting elements after dequeue operations. This optimizes performance.
• Stack vs. Recursion: Recursion uses the call stack implicitly. Consider using a stack directly for more control and potentially better performance, especially for deep recursion.
• Exception Handling: Always handle empty stack/queue scenarios to prevent errors (e.g., returning None or throwing an exception).

6. Practice Problems

1. Valid Parentheses (LeetCode #20): Given a string containing just the characters ’(’, ’)’, ’{’, ’}’, ’[’ and ’]’, determine if the input string is valid.

   • Solution: Use a stack to track opening brackets. When a closing bracket is encountered, check if it matches the top of the stack.

2. Implement Queue using Stacks (LeetCode #232): Implement a first in first out (FIFO) queue using only two stacks.

   • Solution: Use one stack for enqueue operations and another for dequeue operations. When dequeuing, if the dequeue stack is empty, transfer all elements from the enqueue stack to the dequeue stack.

3. Sliding Window Maximum (LeetCode #239): You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

   • Solution: Use a deque to store indices of potentially maximum elements. Maintain the deque such that the elements are in decreasing order. Remove elements that are out of the window.

7. Templates

C++

// Stack Template
#include <stack>
#include <iostream>

using namespace std;

template <typename T>
class MyStack {
private:
    stack<T> s;

public:
    bool isEmpty() {
        return s.empty();
    }

    void push(T val) {
        s.push(val);
    }

    T pop() {
        if (!isEmpty()) {
            T top = s.top();
            s.pop();
            return top;
        } else {
            cerr << "Error: Stack is empty!" << endl;
            return T(); // Default value for type T
        }
    }

    T peek() {
        if (!isEmpty()) {
            return s.top();
        } else {
            cerr << "Error: Stack is empty!" << endl;
            return T(); // Default value for type T
        }
    }
};

// Queue Template
#include <queue>

template <typename T>
class MyQueue {
private:
    queue<T> q;

public:
    bool isEmpty() {
        return q.empty();
    }

    void enqueue(T val) {
        q.push(val);
    }

    T dequeue() {
        if (!isEmpty()) {
            T front = q.front();
            q.pop();
            return front;
        } else {
            cerr << "Error: Queue is empty!" << endl;
            return T(); // Default value for type T
        }
    }

    T front() {
        if (!isEmpty()) {
            return q.front();
        } else {
            cerr << "Error: Queue is empty!" << endl;
            return T(); // Default value for type T
        }
    }
};

Python

# Stack Template
class StackTemplate:
    def __init__(self):
        self.items = []

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None

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

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


# Queue Template
from collections import deque

class QueueTemplate:
    def __init__(self):
        self.items = deque()

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

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

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        else:
            return None

    def front(self):
        if not self.is_empty():
            return self.items[0]
        else:
            return None

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

Java

// Stack Template
import java.util.Stack;

class StackTemplate<T> {
    private Stack<T> stack = new Stack<>();

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public void push(T item) {
        stack.push(item);
    }

    public T pop() {
        if (!isEmpty()) {
            return stack.pop();
        } else {
            System.err.println("Error: Stack is empty!");
            return null; // Or throw an exception
        }
    }

    public T peek() {
        if (!isEmpty()) {
            return stack.peek();
        } else {
            System.err.println("Error: Stack is empty!");
            return null; // Or throw an exception
        }
    }
}

// Queue Template
import java.util.LinkedList;
import java.util.Queue;

class QueueTemplate<T> {
    private Queue<T> queue = new LinkedList<>();

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public void enqueue(T item) {
        queue.offer(item);
    }

    public T dequeue() {
        if (!isEmpty()) {
            return queue.poll();
        } else {
            System.err.println("Error: Queue is empty!");
            return null; // Or throw an exception
        }
    }

    public T front() {
        if (!isEmpty()) {
            return queue.peek();
        } else {
            System.err.println("Error: Queue is empty!");
            return null; // Or throw an exception
        }
    }
}