# 2026年7月30日 课后作业 — LinkedList 队列与栈操作

> **说明**：本次作业基于今日 LinkedList 双链表课程内容，包含两道编程题 — **队列操作（Queue）** 和 **栈操作（Stack）**。请新建 Java 项目，编写并运行代码，将运行结果截图提交。

---

## 作业 1：银行叫号系统 — Queue 队列操作

**知识点**：`offer()` / `poll()` / `peek()`、FIFO（先进先出）队列特性

**场景描述**：LinkedList 实现了 `Queue` 接口，可以用作**队列（FIFO）**。模拟银行叫号系统——客户先到先服务。

**题目要求**：

在 `QueueDemo` 类的 `main` 方法中，完成以下操作：

```java
import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        // 1. 创建一个 Queue<String>，使用 LinkedList 实现
        //    提示：Queue<String> queue = new LinkedList<>();

        // 2. 三个客户依次取号排队：
        //    "客户A" → offer() 入队
        //    "客户B" → offer() 入队
        //    "客户C" → offer() 入队

        // 3. 查看当前排队人数（size()）

        // 4. 查看队首是谁但不离开队列（peek()）
        //    输出："当前排队人数：3，队首：客户A"

        // 5. 叫号服务：队首"客户A"出队（poll()）
        //    输出："请客户A前往1号窗口"

        // 6. 新客户"客户D"取号排队

        // 7. 再次叫号：队首"客户B"出队
        //    输出："请客户B前往1号窗口"

        // 8. 输出剩余排队客户
        //    输出："剩余排队客户：[客户C, 客户D]"

        // 9. 演示 poll() 与 peek() 的空队列安全行为：
        //    创建一个空队列，调用 poll() 和 peek()
        //    观察它们返回什么，而不是抛异常
    }
}
```

**预期输出**：
```
当前排队人数：3，队首：客户A
请客户A前往1号窗口
请客户B前往1号窗口
剩余排队客户：[客户C, 客户D]
空队列 poll() 返回：null
空队列 peek() 返回：null
```

**Queue 方法对比**：

| 操作 | 抛出异常 | 返回特殊值 |
|------|----------|-----------|
| 插入 | `add(e)` | `offer(e)` |
| 移除 | `remove()` | `poll()` |
| 查看 | `element()` | `peek()` |

**思考题**（选做，不要求提交代码）：
1. `poll()` 和 `remove()` 在空队列时行为有什么不同？
2. 队列的 FIFO 特性和栈的 LIFO 特性在实际开发中分别适用于什么场景？

---

## 作业 2：浏览器后退功能 — Stack 栈操作

**知识点**：`push()` / `pop()` / `peek()`、LIFO（后进先出）栈特性、`Deque` 接口的栈语义

**场景描述**：LinkedList 实现了 `Deque` 接口，而 `Deque` 提供了完整的**栈（Stack）操作**。Java 官方建议：**使用 `Deque` 代替 `Stack` 类**，因为 `Stack` 继承自 `Vector`，性能较差且线程安全开销不必要。模拟一个"浏览器后退"功能——每次访问新页面就入栈，点击后退就从栈顶弹出。

**题目要求**：

在 `StackDemo` 类的 `main` 方法中，完成以下操作：

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

public class StackDemo {
    public static void main(String[] args) {
        // 1. 创建一个 Deque<String>，使用 LinkedList 实现，作为栈使用
        //    提示：Deque<String> stack = new LinkedList<>();

        // 2. 模拟小明浏览网页：
        //    "首页" → push() 入栈
        //    "新闻页" → push() 入栈
        //    "体育频道" → push() 入栈
        //    "NBA战报" → push() 入栈

        // 3. 查看当前栈顶页面（peek()），不弹出
        //    输出："当前页面：NBA战报"

        // 4. 点击后退：依次弹出 3 次（pop()）
        //    每次输出："后退到：XXX"
        //    顺序应该是：NBA战报 → 体育频道 → 新闻页

        // 5. 输出栈中剩余页面
        //    输出："剩余浏览记录：[首页]"

        // 6. 小明又访问了新页面："科技频道" → push()
        //    "AI专题" → push()

        // 7. 再次查看栈顶（peek()）

        // 8. 连续弹出所有页面（用循环 pop() 直到栈为空）
        //    提示：while (!stack.isEmpty()) { ... }

        // 9. 尝试在空栈时调用 pop()，观察发生了什么
        //    提示：NoSuchElementException（与 Queue 的 poll() 不同）
    }
}
```

**预期输出**：
```
========== 浏览器后退模拟 ==========
当前页面：NBA战报
后退到：NBA战报
后退到：体育频道
后退到：新闻页
剩余浏览记录：[首页]
当前页面：AI专题
连续后退：
后退到：AI专题
后退到：科技频道
后退到：首页
浏览记录已清空
```

**关键方法说明**：

| 方法 | 栈的等价操作 | 说明 |
|------|-------------|------|
| `push(E e)` | 入栈（压栈） | 将元素压入栈顶，等价于 `addFirst()` |
| `pop()` | 出栈（弹栈） | 移除并返回栈顶元素，空栈时抛 `NoSuchElementException` |
| `peek()` | 查看栈顶 | 返回栈顶元素但不移除，空栈时抛 `NoSuchElementException` |

**LinkedList 三种角色对比**：

| 角色 | 接口 | 核心操作 | 数据结构 |
|------|------|---------|---------|
| 列表（List） | `List` | `add()` / `get()` / `set()` / `remove(index)` | 线性表 |
| 队列（Queue） | `Queue` | `offer()` / `poll()` / `peek()` | FIFO 先进先出 |
| 栈（Stack） | `Deque` | `push()` / `pop()` / `peek()` | LIFO 后进先出 |

**思考题**（选做，不要求提交代码）：
1. Java 官方为什么不推荐使用 `java.util.Stack` 类？
2. `Deque` 的 `push()` 和 `addFirst()` 本质上是同一个方法，为什么提供两个名字？
3. 用 `Deque` 实现栈时，`pop()` 和 `poll()` 在空栈时行为有何不同？

---

## 提交要求

1. 新建 Java 项目（或使用现有项目），包名建议：`homework0730`
2. 编写 `QueueDemo` 和 `StackDemo` 两个类，分别实现作业 1 和作业 2
3. 运行代码，控制台输出结果需与预期输出一致
4. **将代码源文件和运行结果截图**提交到班级群

## 参考答案（供批改参考）

### 作业 1 参考代码

```java
import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("客户A");
        queue.offer("客户B");
        queue.offer("客户C");

        System.out.println("当前排队人数：" + queue.size()
            + "，队首：" + queue.peek());

        System.out.println("请" + queue.poll() + "前往1号窗口");
        queue.offer("客户D");
        System.out.println("请" + queue.poll() + "前往1号窗口");
        System.out.println("剩余排队客户：" + queue);

        Queue<String> emptyQueue = new LinkedList<>();
        System.out.println("空队列 poll() 返回：" + emptyQueue.poll());
        System.out.println("空队列 peek() 返回：" + emptyQueue.peek());
    }
}
```

### 作业 2 参考代码

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

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new LinkedList<>();

        stack.push("首页");
        stack.push("新闻页");
        stack.push("体育频道");
        stack.push("NBA战报");

        System.out.println("当前页面：" + stack.peek());

        System.out.println("后退到：" + stack.pop());
        System.out.println("后退到：" + stack.pop());
        System.out.println("后退到：" + stack.pop());

        System.out.println("剩余浏览记录：" + stack);

        stack.push("科技频道");
        stack.push("AI专题");
        System.out.println("当前页面：" + stack.peek());

        System.out.println("连续后退：");
        while (!stack.isEmpty()) {
            System.out.println("后退到：" + stack.pop());
        }
        System.out.println("浏览记录已清空");

        Deque<String> emptyStack = new LinkedList<>();
        try {
            emptyStack.pop();
        } catch (Exception e) {
            System.out.println("空栈调用 pop()：" + e.getClass().getSimpleName());
        }
    }
}
```