第3天：栈与队列算法 - 问题分析与Java实现

1. 问题分析

问题1：有效的括号

问题描述

给定一个只包含 '('、)、'{'、'}'、'['、']' 的字符串，判断输入字符串是否有效。

示例

输入: s = "()"
输出: true

输入: s = "()[]{}"
输出: true

输入: s = "(]"
输出: false

2. 解决方案（多种方法）

方法1：使用栈（O(n))

思路：

• 遍历字符串，使用栈来跟踪左括号。
• 对于每个右括号，检查它是否匹配栈顶的左括号。
• 如果匹配，弹出栈顶元素；否则，返回false。
• 如果栈为空，返回true，否则返回false。

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    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 != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}

优点：

• 时间复杂度：O(n)，遍历字符串一次。
• 空间复杂度：O(n)，使用栈来存储字符。

问题2：用栈实现队列

问题描述

用两个栈实现一个队列，队列应该实现以下操作：

• push(x)：将元素x推到队列的末尾。
• pop()：从队列的前端移除元素。
• peek()：获取队列前端的元素。
• empty()：返回队列是否为空。

示例

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop();  // 返回 1
queue.empty(); // 返回 false

2. 解决方案（多种方法）

方法1：使用两个栈（O(1)的push，O(n)的pop和peek）

思路：

• 使用两个栈：一个用于入队，一个用于

出队。

• 出队或查看队列前端时，如果出队栈为空，则从入队栈中转移元素到出队栈。
• 这样可以保证元素按照FIFO顺序被处理。

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

优点：

• 时间复杂度：**O(1)**的push，**O(n)**的pop和peek。
• 空间复杂度：O(n)，使用了两个栈。

问题3：用队列实现栈

问题描述

用两个队列实现一个栈，栈应该实现以下操作：

• push(x)：将元素x推到栈顶。
• pop()：移除栈顶的元素。
• top()：获取栈顶元素。
• empty()：返回栈是否为空。

示例

MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // 返回 2
stack.pop(); // 返回 2
stack.empty(); // 返回 false

2. 解决方案（多种方法）

方法1：使用两个队列（O(n)的pop，O(1)的push）

思路：

• 使用两个队列，一个存储元素，另一个临时保存元素进行pop操作。
• 在模拟栈操作时，将除最后一个元素外的所有元素转移到第二个队列。

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue1.offer(x);
    }

    public int pop() {
        while (queue1.size() > 1) {
            queue2.offer(queue1.poll());
        }
        int top = queue1.poll();
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
        return top;
    }

    public int top() {
        while (queue1.size() > 1) {
            queue2.offer(queue1.poll());
        }
        int top = queue1.peek();
        queue2.offer(queue1.poll());
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
        return top;
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

优点：

• 时间复杂度：**O(n)**的pop和top，**O(1)**的push。
• 空间复杂度：O(n)，使用了两个队列。

总结

🔥 掌握这些栈和队列算法，强化大厂面试题的解决能力！ 🚀