# 栈与队列

## 目录
- [栈基础](#栈基础)
- [队列基础](#队列基础)
- [栈与队列应用](#栈与队列应用)
- [算法题](#算法题)
- [面试常见问题](#面试常见问题)

---

## 栈基础

### 栈定义

```java
// 栈：后进先出（LIFO）
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // 2
```

### 栈实现

```java
public class MyStack {
    private List<Integer> list = new ArrayList<>();
    
    public void push(int x) {
        list.add(x);
    }
    
    public int pop() {
        return list.remove(list.size() - 1);
    }
    
    public int peek() {
        return list.get(list.size() - 1);
    }
    
    public boolean empty() {
        return list.isEmpty();
    }
}
```

---

## 队列基础

### 队列定义

```java
// 队列：先进先出（FIFO）
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll(); // 1
```

### 队列实现

```java
public class MyQueue {
    private List<Integer> list = new ArrayList<>();
    
    public void offer(int x) {
        list.add(x);
    }
    
    public int poll() {
        return list.remove(0);
    }
    
    public int peek() {
        return list.get(0);
    }
    
    public boolean empty() {
        return list.isEmpty();
    }
}
```

---

## 栈与队列应用

### 栈应用

```java
// 1. 括号匹配
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 != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

// 2. 表达式求值
// 3. 函数调用栈
```

### 队列应用

```java
// 1. 广度优先搜索（BFS）
// 2. 任务调度
// 3. 消息队列
```

---

## 算法题

### 题1：用栈实现队列

```java
class MyQueue {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> 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();
    }
}
```

---

## 面试常见问题

### Q1: 栈和队列的区别？

**答案：**
- **栈**：后进先出（LIFO）
- **队列**：先进先出（FIFO）

### Q2: 栈的应用？

**答案：**
- 括号匹配
- 表达式求值
- 函数调用栈

---

*最后更新：2024年*
