滑动窗口队列详解
滑动窗口（Sliding Window）是一种常见的数据处理技术，广泛应用于网络协议（如TCP）、流数据处理、算法优化（如子数组问题）等场景。结合队列（Queue）可以高效实现滑动窗口的逻辑。
1. 什么是滑动窗口？
滑动窗口是一种在固定或可变大小的窗口内动态维护数据的技术，通常用于：
- 流量控制（如TCP的发送/接收窗口）
- 实时数据分析（如计算最近N秒的平均值）
- 算法优化（如求最长无重复字符的子串）
2. 滑动窗口 + 队列的实现
队列（FIFO结构）天然适合实现滑动窗口，核心操作：
- 入队（Enqueue）：新数据加入窗口。
- 出队（Dequeue）：旧数据移出窗口。
- 维护窗口大小：确保不超过最大容量。
C++ 示例代码
#include <iostream>
#include <queue>
using namespace std;
class SlidingWindow {
private:
queue<int> window; // 用队列存储窗口数据
int maxSize; // 窗口最大容量
public:
SlidingWindow(int size) : maxSize(size) {}
// 添加数据到窗口
void add(int value) {
if (window.size() >= maxSize) {
window.pop(); // 移除最旧的数据
}
window.push(value);
}
// 计算当前窗口数据的平均值
double getAverage() {
if (window.empty()) return 0.0;
queue<int> temp = window;
double sum = 0;
while (!temp.empty()) {
sum += temp.front();
temp.pop();
}
return sum / window.size();
}
// 打印当前窗口内容
void printWindow() {
queue<int> temp = window;
cout << "Window: [ ";
while (!temp.empty()) {
cout << temp.front() << " ";
temp.pop();
}
cout << "]" << endl;
}
};
int main() {
SlidingWindow sw(3); // 设置窗口大小为3
sw.add(1);
sw.add(2);
sw.add(3);
sw.printWindow(); // Window: [1, 2, 3]
sw.add(4);
sw.printWindow(); // Window: [2, 3, 4] （最旧的1被移除）
cout << "Average: " << sw.getAverage() << endl; // (2+3+4)/3 = 3
return 0;
}
3. TCP中的滑动窗口
在TCP协议中，滑动窗口用于：
- 流量控制：接收方通过
Advertised Window告知发送方可发送的数据量。 - 拥塞控制：动态调整发送速率避免网络拥塞。
(1) TCP发送端维护两个关键变量
| 变量 | 作用 |
|---|---|
SendBase |
最早未被确认的字节序号 |
LastByteSent |
最后一个已发送的字节序号 |
(2) TCP接收端的关键变量
| 变量 | 作用 |
|---|---|
LastByteRead |
应用层最后读取的字节序号 |
NextByteExpected |
期望收到的下一个字节序号 |
4. LeetCode经典题目
(1) 209. Minimum Size Subarray Sum
给定一个数组和一个目标值，找到和 ≥ target的最短子数组长度。
int minSubArrayLen(int target, vector<int>& nums) {
int left = -1, right = -1;
int sum =0 , res=INT_MAX ;
for(right=0 ;right<nums.size();right++){
sum+=nums[right];
while(sum>=target){
res=min(res , right-left );
left++;
sum-=nums[left];
}
}
return res==INT_MAX?0:res ;
}
(时间复杂度 O(n))
5. Kafka中的时间滑动窗
Kafka Streams使用时间滑动窗统计最近N秒的数据，例如：
TimeWindows.of(Duration.ofSeconds(30)).advanceBy(Duration.ofSeconds(10));
表示每10秒统计过去30秒内的数据。
6. Redis Stream的消费者组ACK机制
Redis Stream采用类似TCP的ACK机制，消费者通过 XREADGROUP读取消息后需显式 XACK确认，否则会触发重新投递。
总结
✅ |场景 |数据结构 |典型应用 |
| ✔️ | 固定大小滑窗 | 循环队列/双端队列 |
| ✔️ | 可变滑窗 | 双指针+哈希表 |
| ✔️ | 时间滑窗 | 优先级队列+定时器 |
如果需要更详细的某个方向解析（如TCP/Kafka/算法），可以告诉我！
内容由零声教学AI助手提供，问题来源于学员提问
