力扣1700题：无法吃午餐的学生数量 - 队列模拟解法详解

内容简介

本文详细解析了力扣1700题"无法吃午餐的学生数量"的队列模拟解法。通过模拟学生排队取餐的过程，统计无法吃到喜欢三明治的学生数量。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握队列模拟问题的解决技巧。

算法思路

‌1.队列模拟‌：使用双指针模拟学生队列和三明治栈

‌2.匹配处理‌：当学生偏好与栈顶三明治匹配时，两者都出队

‌3.不匹配处理‌：不匹配时学生重新排到队尾

‌4.终止条件‌：当一轮遍历没有学生能吃到三明治时结束

代码实现（带详细注释）

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int front = 0;          // 学生队列头部指针
        int rear = students.size() - 1; // 学生队列尾部指针(初始位置)
        int top = 0;            // 三明治栈顶指针
        int stu_num = students.size(); // 剩余学生数量
        
        int num = stu_num;      // 当前轮次待处理学生数

        while(num != 0) {       // 当还有学生需要处理时循环
            if(students[front] == sandwiches[top]) { // 学生偏好匹配栈顶三明治
                front++;        // 学生出队
                top++;          // 三明治出栈
                stu_num--;      // 剩余学生数减1
                num = stu_num;  // 重置待处理学生数
            }
            else {              // 不匹配情况
                students.push_back(students[front]); // 学生排到队尾
                front++;        // 移动队首指针
                num--;          // 待处理学生数减1
            }
        }
        return stu_num;         // 返回无法就餐的学生数
    }
};

复杂度分析

‌时间复杂度‌：O(n^2)，最坏情况下每个学生需要遍历整个队列

‌空间复杂度‌：O(1)，仅使用常数个额外空间

优化方向

‌计数优化‌：统计学生偏好数量，提前判断无法分配的情况

‌提前终止‌：当剩余学生都偏好同一种三明治且栈顶不是该类型时提前终止

‌队列优化‌：使用标准队列容器替代vector模拟

总结

队列模拟是解决此类学生-三明治匹配问题的有效方法，通过模拟实际排队过程可以直观地统计无法就餐的学生数量。理解这种解法有助于掌握队列数据结构的应用场景和模拟类问题的解决思路。