LeetCode栈与队列全解析：从基础到高级应用

// 使用Deque实现栈
Deque<Integer> stack = new ArrayDeque<>();

// 入栈操作
stack.push(1);
stack.push(2);
stack.push(3);

// 查看栈顶元素
int top = stack.peek(); // 返回3，但不删除

// 出栈操作
int popped = stack.pop(); // 返回3，并从栈中删除

// 检查栈是否为空
boolean isEmpty = stack.isEmpty();

// 获取栈的大小
int size = stack.size();

// 使用LinkedList实现队列
Queue<Integer> queue = new LinkedList<>();

// 入队操作
queue.offer(1);
queue.offer(2);
queue.offer(3);

// 查看队头元素
int front = queue.peek(); // 返回1，但不删除

// 出队操作
int removed = queue.poll(); // 返回1，并从队列中删除

// 检查队列是否为空
boolean isEmpty = queue.isEmpty();

// 获取队列的大小
int size = queue.size();

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    
    for (char c : s.toCharArray()) {
        // 如果是左括号，压入栈中
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            // 如果是右括号，检查栈是否为空
            if (stack.isEmpty()) {
                return false;
            }
            
            // 检查括号是否匹配
            char top = stack.pop();
            if ((c == ')' && top != '(') || 
                (c == '}' && top != '{') || 
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    
    // 遍历结束后，栈应该为空
    return stack.isEmpty();
}

class MinStack {
    private Deque<Integer> stack;     // 主栈
    private Deque<Integer> minStack;  // 辅助栈，用于跟踪最小值
    
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        stack.push(val);
        // 如果辅助栈为空或新元素小于等于辅助栈顶元素，则将新元素压入辅助栈
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }
    
    public void pop() {
        // 如果弹出的元素等于辅助栈顶元素，则辅助栈也需要弹出栈顶元素
        if (stack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return heights[0];
    }
    
    int maxArea = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    
    // 遍历所有柱子
    for (int i = 0; i < n; i++) {
        // 当前柱子的高度小于等于栈顶柱子的高度，需要计算面积
        while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
            int h = heights[stack.pop()]; // 当前要计算的柱子的高度
            int w; // 宽度
            if (stack.isEmpty()) {
                w = i; // 如果栈为空，说明左边没有比它小的柱子，宽度为i
            } else {
                w = i - stack.peek() - 1; // 宽度为当前索引减去栈顶索引再减1
            }
            maxArea = Math.max(maxArea, h * w);
        }
        // 将当前柱子的索引压入栈中
        stack.push(i);
    }
    
    // 处理栈中剩余的元素
    while (!stack.isEmpty()) {
        int h = heights[stack.pop()];
        int w;
        if (stack.isEmpty()) {
            w = n;
        } else {
            w = n - stack.peek() - 1;
        }
        maxArea = Math.max(maxArea, h * w);
    }
    
    return maxArea;
}

public int trap(int[] height) {
    int n = height.length;
    if (n <= 2) {
        return 0; // 至少需要3个柱子才能形成凹槽
    }
    
    int totalWater = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    
    // 遍历所有柱子
    for (int i = 0; i < n; i++) {
        // 当前柱子的高度大于栈顶柱子的高度，需要计算能接多少雨水
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop(); // 凹槽的底部
            if (stack.isEmpty()) {
                break; // 如果栈为空，说明左边没有柱子，无法形成凹槽
            }
            int left = stack.peek(); // 凹槽的左边界
            int width = i - left - 1; // 凹槽的宽度
            int h = Math.min(height[left], height[i]) - height[bottom]; // 凹槽的高度
            totalWater += width * h; // 计算该凹槽能接的雨水量
        }
        // 将当前柱子的索引压入栈中
        stack.push(i);
    }
    
    return totalWater;
}

class MyQueue {
    private Deque<Integer> inStack;  // 用于入队操作的栈
    private Deque<Integer> outStack; // 用于出队操作的栈
    
    public MyQueue() {
        inStack = new ArrayDeque<>();
        outStack = new ArrayDeque<>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        // 确保outStack不为空
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.pop();
    }
    
    public int peek() {
        // 确保outStack不为空
        if (outStack.isEmpty()) {
            inToOut();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    
    // 将inStack中的所有元素转移到outStack中
    private void inToOut() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

class MyStack {
    private Queue<Integer> queue1; // 主队列
    private Queue<Integer> queue2; // 辅助队列
    
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        // 先将元素添加到queue2
        queue2.offer(x);
        // 将queue1中的所有元素添加到queue2
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        // 交换queue1和queue2的引用
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k == 0) {
        return new int[0];
    }
    
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // 单调递减队列，存储的是元素的索引
    
    for (int i = 0; i < n; i++) {
        // 移除队列中所有小于当前元素的索引
        while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
            deque.pollLast();
        }
        
        // 将当前元素的索引添加到队列中
        deque.offerLast(i);
        
        // 移除队列中所有不在当前滑动窗口范围内的索引
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // 如果已经形成了一个完整的滑动窗口，则记录当前的最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    
    return result;
}

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();      // 返回 3
circularQueue.isFull();    // 返回 true
circularQueue.deQueue();   // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();      // 返回 4

class MyCircularQueue {
    private int[] data;   // 存储元素的数组
    private int front;    // 队首指针
    private int rear;     // 队尾指针
    private int capacity; // 队列的容量
    
    public MyCircularQueue(int k) {
        capacity = k + 1; // 预留一个位置
        data = new int[capacity];
        front = 0;
        rear = 0;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        data[rear] = value;
        rear = (rear + 1) % capacity; // 循环更新队尾指针
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity; // 循环更新队首指针
        return true;
    }
    
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[front];
    }
    
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // 注意：rear指向的是队尾元素的下一个位置，所以需要减1
        int realRear = (rear - 1 + capacity) % capacity;
        return data[realRear];
    }
    
    public boolean isEmpty() {
        return front == rear;
    }
    
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }
}

public String decodeString(String s) {
    Deque<Integer> numStack = new ArrayDeque<>(); // 存储重复次数
    Deque<StringBuilder> strStack = new ArrayDeque<>(); // 存储字符串
    StringBuilder currentStr = new StringBuilder(); // 当前正在构建的字符串
    int num = 0; // 当前的重复次数
    
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            // 解析数字
            num = num * 10 + (c - '0');
        } else if (c == '[') {
            // 遇到左括号，将当前的重复次数和字符串压入栈中
            numStack.push(num);
            strStack.push(currentStr);
            // 重置当前的重复次数和字符串
            num = 0;
            currentStr = new StringBuilder();
        } else if (c == ']') {
            // 遇到右括号，需要解码
            StringBuilder prevStr = strStack.pop(); // 弹出之前的字符串
            int repeat = numStack.pop(); // 弹出重复次数
            // 将当前字符串重复repeat次，并追加到prevStr后面
            for (int i = 0; i < repeat; i++) {
                prevStr.append(currentStr);
            }
            // 更新当前字符串
            currentStr = prevStr;
        } else {
            // 遇到字母，直接添加到当前字符串中
            currentStr.append(c);
        }
    }
    
    return currentStr.toString();
}

public String simplifyPath(String path) {
    // 将路径按照'/'分割成多个部分
    String[] components = path.split("/");
    Deque<String> stack = new ArrayDeque<>();
    
    for (String component : components) {
        // 忽略空字符串和'.'
        if (component.isEmpty() || component.equals(".")) {
            continue;
        }
        // 如果是'..'，则从栈中弹出一个元素（如果栈不为空）
        if (component.equals("..")) {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else {
            // 否则，将该部分压入栈中
            stack.push(component);
        }
    }
    
    // 将栈中的元素用'/'连接起来
    StringBuilder result = new StringBuilder();
    for (String dir : stack) {
        result.insert(0, "/" + dir);
    }
    
    // 如果结果为空，则返回"/"
    return result.length() > 0 ? result.toString() : "/";
}

public int calculate(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    int num = 0;
    char sign = '+'; // 初始运算符为'+'
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        // 如果是数字，更新num
        if (Character.isDigit(c)) {
            num = num * 10 + (c - '0');
        }
        
        // 如果是运算符或到达字符串末尾，处理之前的数字
        if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
            switch (sign) {
                case '+':
                    stack.push(num);
                    break;
                case '-':
                    stack.push(-num);
                    break;
                case '*':
                    stack.push(stack.pop() * num);
                    break;
                case '/':
                    stack.push(stack.pop() / num);
                    break;
            }
            // 更新运算符和数字
            sign = c;
            num = 0;
        }
    }
    
    // 计算栈中所有元素的和
    int result = 0;
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    
    return result;
}

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 存储较小的一半元素
    private PriorityQueue<Integer> minHeap; // 存储较大的一半元素
    
    public MedianFinder() {
        // 最大堆，默认是最小堆，所以需要传递一个比较器
        maxHeap = new PriorityQueue<>((a, b) -> b - a);
        // 最小堆
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        if (maxHeap.size() == minHeap.size()) {
            // 先添加到maxHeap，然后将maxHeap的堆顶元素添加到minHeap
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        } else {
            // 先添加到minHeap，然后将minHeap的堆顶元素添加到maxHeap
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            // 两个堆大小相等，中位数是两个堆顶元素的平均值
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            // 两个堆大小不相等，中位数是minHeap的堆顶元素
            return minHeap.peek();
        }
    }
}