Stacks and Queues

Stacks and queues are fundamental linear data structures used for organizing and managing data in computer science. They provide specific ways to add and remove elements, which makes them suitable for a variety of applications.

Stack

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 is the first one to be removed.

• Operations:
  • Push: Adds an element to the top of the stack.
  • Pop: Removes and returns the element from the top of the stack.
  • Peek (or Top):strong> Returns the element at the top of the stack without removing it.
• Applications:
  • Implementing function call stacks in programming languages.
  • Evaluating and converting mathematical expressions (e.g., postfix notation).
  • Managing browser history (back/forward navigation).
• Implementation: Can be implemented using arrays or linked lists.

Queue

A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. The first element added to the queue is the first one to be removed.

• Operations:
  • Enqueue: Adds an element to the rear (or tail) of the queue.
  • Dequeue: Removes and returns the element from the front (or head) of the queue.
  • Peek (or Front):strong> Returns the element at the front of the queue without removing it.
• Applications:
  • Task scheduling in operating systems.
  • Implementing breadth-first search (BFS) in graph algorithms.
  • Print spoolers in printers.
• Implementation: Can be implemented using arrays or linked lists. A special variant is the Deque (Double-Ended Queue), which allows insertion and deletion from both ends.

Key Characteristics

• Restricted Access: Both structures limit how data can be accessed. A stack only allows access to its top element, while a queue only allows access to its front element.
• Core Operations: The fundamental operations are adding (push/enqueue) and removing (pop/dequeue) elements, along with the ability to view the top/front element.

Practical Examples

1. Valid Parentheses

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

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public boolean isValid(String s) {
        // A string with an odd length cannot be valid
        if (s.length() % 2 != 0) {
            return false;
        }

        // Use a deque as a stack to store opening brackets
        Deque<character> bracketStack = new LinkedList<>();

        for (char c : s.toCharArray()) {
            switch (c) {
                case '(':
                    bracketStack.push(')');
                    break;
                case '[':
                    bracketStack.push(']');
                    break;
                case '{':
                    bracketStack.push('}');
                    break;
                default:
                    // For closing brackets, check if the stack is empty or the top doesn't match
                    if (bracketStack.isEmpty() || c != bracketStack.pop()) {
                        return false;
                    }
            }
        }

        // If the stack is empty, all brackets were matched correctly
        return bracketStack.isEmpty();
    }
}
</character>

2. Remove All Adjacent Duplicates in String

Given a string s, recursively remove adjacent duplicate characters until no duplicate exists. The final string will have no two adjacent characters that are the same.

import java.util.Stack;

class Solution {
    public String removeDuplicates(String s) {
        // Use a stack to keep track of characters
        Stack<character> charStack = new Stack<>();

        for (char c : s.toCharArray()) {
            // If the stack is not empty and the top character matches the current one, pop it
            if (!charStack.isEmpty() && charStack.peek() == c) {
                charStack.pop();
            } else {
                // Otherwise, push the current character onto the stack
                charStack.push(c);
            }
        }

        // Build the result string from the stack
        StringBuilder result = new StringBuilder();
        for (char c : charStack) {
            result.append(c);
        }
        return result.toString();
    }
}
</character>

3. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN). Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<integer> evaluationStack = new LinkedList<>();

        for (String token : tokens) {
            if (isOperator(token)) {
                // Pop the two operands for the operation
                int operand2 = evaluationStack.pop();
                int operand1 = evaluationStack.pop();
                int result = performOperation(operand1, operand2, token);
                evaluationStack.push(result);
            } else {
                // Push the numeric operand onto the stack
                evaluationStack.push(Integer.parseInt(token));
            }
        }

        return evaluationStack.pop();
    }

    private boolean isOperator(String token) {
        return "+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token);
    }

    private int performOperation(int a, int b, String operator) {
        switch (operator) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "*":
                return a * b;
            case "/":
                return a / b; // Integer division
            default:
                throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}
</integer>

4. Sliding Window Maximum

Given an integer array nums and a positive integer k, find the maximum value in each contiguous subarray (or sliding window) of size k.

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] inputArray, int windowSize) {
        if (inputArray == null || windowSize <= 0) {
            return new int[0];
        }

        int n = inputArray.length;
        int[] result = new int[n - windowSize + 1];
        int resultIndex = 0;

        // This deque will store indices of array elements. The elements in the deque are in decreasing order.
        Deque<integer> monotonicQueue = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 1. Remove indices that are out of the current window (i - windowSize)
            while (!monotonicQueue.isEmpty() && monotonicQueue.peek() < i - windowSize + 1) {
                monotonicQueue.poll();
            }

            // 2. Remove indices whose corresponding values are smaller than the current element
            // This maintains the decreasing order in the deque
            while (!monotonicQueue.isEmpty() && inputArray[monotonicQueue.peekLast()] < inputArray[i]) {
                monotonicQueue.pollLast();
            }

            // Add the current element's index to the deque
            monotonicQueue.offer(i);

            // The front of the deque is the index of the maximum element for the current window
            if (i >= windowSize - 1) {
                result[resultIndex++] = inputArray[monotonicQueue.peek()];
            }
        }

        return result;
    }
}
</integer>