循环队列（Circular Queue） 的实现，循环队列是队列的一种优化形式，特别适合需要高效利用空间的场景

循环队列（Circular Queue） 的实现，循环队列是队列的一种优化形式，特别适合需要高效利用空间的场景。

以下我将对循环队列进行详细解析，包括中文解释、适用场景、示例代码、测试用例，并针对半导体产线或测试机场景提供定制化的代码示例。

循环队列在项目（https://github.com/aalhour/C-Sharp-Algorithms）中作为 Circular Buffer 列出，是队列的一种实现方式。内容将基于 C# 类库项目的结构，结合半导体产线应用进行扩展，确保清晰、简洁且全面。

一、循环队列 (Circular Queue) 详解中文解释循环队列是一种基于数组的队列实现，通过将数组的首尾连接形成“环状”结构，避免了普通数组队列的空间浪费。普通队列在出队（Dequeue）后，前端空间无法重用，而循环队列通过模运算使索引循环利用，最大化空间效率。

循环队列遵循 先进先出（FIFO, First In First Out） 原则，主要操作包括：

• Enqueue：将元素加入队列尾部，时间复杂度 O(1)。
• Dequeue：移除并返回队列头部元素，时间复杂度 O(1)。
• Peek：查看队列头部元素但不移除，时间复杂度 O(1)。
• IsEmpty/IsFull：检查队列是否为空或已满，时间复杂度 O(1)。

循环队列通常用于固定容量或动态扩展的场景，相比链表实现的队列，循环队列具有更高的内存局部性和更低的内存开销。

适用场景

• 通用场景：
  • 缓冲区管理：如网络数据包缓冲、音频/视频流处理。
  • 任务调度：按顺序处理固定数量的任务。
  • 生产者-消费者模型：如多线程环境中数据传递。
• 半导体产线场景：
  • 测试机：管理固定数量的晶圆测试任务缓冲区，避免频繁内存分配。
  • 贴片机 (SMT)：调度有限的元件贴片任务，优化任务处理顺序。
• 优点：
  • 高效的空间利用（通过循环避免前端空间浪费）。
  • 操作高效（O(1)）。
  • 适合固定容量或高频入队/出队的场景。
• 缺点：
  • 固定容量可能限制灵活性（需扩容机制）。
  • 不支持随机访问或复杂查询。
  • 动态扩展需要重新分配数组，增加复杂度。

二、示例代码以下是循环队列的 C# 实现，基于项目的 Circular Buffer 结构，使用动态数组支持扩容，保持高效的空间利用：csharp

using System;

public class CircularQueue<T>
{
private T[] items;
private int front; // 队列头部索引
private int rear; // 队列尾部索引
private int size;
private int capacity;

public CircularQueue(int initialCapacity)
{
if (initialCapacity <= 0)
throw new ArgumentException("Initial capacity must be positive");
capacity = initialCapacity;
items = new T[capacity];
front = 0;
rear = -1;
size = 0;
}

public int Count => size;

public bool IsEmpty => size == 0;

public bool IsFull => size == capacity;

public void Enqueue(T item)
{
if (IsFull)
Resize(capacity * 2); // 容量翻倍
rear = (rear + 1) % capacity; // 循环索引
items[rear] = item;
size++;
}

public T Dequeue()
{
if (IsEmpty)
throw new InvalidOperationException("Queue is empty");
T item = items[front];
items[front] = default; // 释放引用
front = (front + 1) % capacity; // 循环索引
size–;
if (size > 0 && size <= capacity / 4)
Resize(capacity / 2); // 缩容
return item;
}

public T Peek()
{
if (IsEmpty)
throw new InvalidOperationException("Queue is empty");
return items[front];
}

private void Resize(int newCapacity)
{
T[] newItems = new T[newCapacity];
for (int i = 0; i < size; i++)
newItems[i] = items[(front + i) % capacity];
items = newItems;
front = 0;
rear = size – 1;
capacity = newCapacity;
}
}

代码说明

• 构造：初始化循环数组，设置初始容量，front 和 rear 跟踪队列头尾。
• Enqueue：将元素加入队列尾部，使用模运算实现循环，必要时扩容。
• Dequeue：移除并返回队列头部元素，必要时缩容。
• Peek：查看队列头部元素。
• Resize：动态调整数组大小，重新排列元素以保持连续性。
• 清理：Dequeue 时将数组元素置为 default 以释放引用，防止内存泄漏。
• 循环机制：通过 (index + 1) % capacity 实现首尾相连，避免空间浪费。

三、测试用例以下是使用 MSTest 框架的单元测试代码：csharp

using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class CircularQueueTests
{
[TestMethod]
public void EnqueueAndDequeue_ValidItems_ReturnsCorrectOrder()
{
// Arrange
var queue = new CircularQueue<int>(3);
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

// Act
int item1 = queue.Dequeue();
int item2 = queue.Dequeue();
int item3 = queue.Dequeue();

// Assert
Assert.AreEqual(1, item1);
Assert.AreEqual(2, item2);
Assert.AreEqual(3, item3);
Assert.IsTrue(queue.IsEmpty);
}

[TestMethod]
public void Peek_ValidQueue_ReturnsFrontItem()
{
// Arrange
var queue = new CircularQueue<int>(3);
queue.Enqueue(1);
queue.Enqueue(2);

// Act
int frontItem = queue.Peek();

// Assert
Assert.AreEqual(1, frontItem);
Assert.AreEqual(2, queue.Count);
}

[TestMethod]
[ExpectedException(typeof(InvalidOperationException))]
public void Dequeue_EmptyQueue_ThrowsException()
{
// Arrange
var queue = new CircularQueue<int>(3);

// Act
queue.Dequeue(); // 应抛出异常
}

[TestMethod]
public void Enqueue_FullQueue_TriggersResize()
{
// Arrange
var queue = new CircularQueue<int>(2);
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3); // 触发扩容

// Act
int count = queue.Count;
int frontItem = queue.Peek();

// Assert
Assert.AreEqual(3, count);
Assert.AreEqual(1, frontItem);
}

[TestMethod]
public void EnqueueDequeue_CircularBehavior_WorksCorrectly()
{
// Arrange
var queue = new CircularQueue<int>(3);
queue.Enqueue(1);
queue.Enqueue(2);
queue.Dequeue(); // 移除 1
queue.Enqueue(3); // 应循环利用空间

// Act
int item1 = queue.Dequeue();
int item2 = queue.Dequeue();

// Assert
Assert.AreEqual(2, item1);
Assert.AreEqual(3, item2);
Assert.IsTrue(queue.IsEmpty);
}
}

测试说明

• 测试 Enqueue 和 Dequeue，确保先进先出（FIFO）的正确性。
• 测试 Peek，验证查看队列头部元素不影响队列状态。
• 测试空队列操作，确保抛出异常。
• 测试扩容，验证动态调整容量。
• 测试循环行为，确保首尾空间循环利用。

四、半导体产线示例在半导体测试机中，循环队列可用于管理固定大小的晶圆测试任务缓冲区。例如，测试机接收晶圆测试任务，缓冲区容量有限，任务按到达顺序处理，循环队列可高效利用空间。示例代码csharp

public class WaferTestTask
{
public int WaferId { get; set; }
public DateTime SubmissionTime { get; set; }
public string TestType { get; set; }

public WaferTestTask(int waferId, DateTime submissionTime, string testType)
{
WaferId = waferId;
SubmissionTime = submissionTime;
TestType = testType;
}
}

public class WaferTestBuffer
{
private CircularQueue<WaferTestTask> taskBuffer;

public WaferTestBuffer(int capacity)
{
taskBuffer = new CircularQueue<WaferTestTask>(capacity);
}

public void AddTestTask(int waferId, DateTime submissionTime, string testType)
{
if (taskBuffer.IsFull)
throw new InvalidOperationException("Test buffer is full");
taskBuffer.Enqueue(new WaferTestTask(waferId, submissionTime, testType));
}

public WaferTestTask ProcessNextTest()
{
return taskBuffer.Dequeue();
}

public WaferTestTask PeekNextTest()
{
return taskBuffer.Peek();
}

public int TaskCount => taskBuffer.Count;

public bool IsFull => taskBuffer.IsFull;
}

测试用例csharp

[TestMethod]
public void WaferTestBuffer_AddAndProcess_ReturnsCorrectTask()
{
// Arrange
var buffer = new WaferTestBuffer(2);
var time1 = new DateTime(2025, 8, 6, 13, 0, 0);
var time2 = new DateTime(2025, 8, 6, 13, 1, 0);
buffer.AddTestTask(1001, time1, "VoltageTest");
buffer.AddTestTask(1002, time2, "DefectTest");

// Act
var nextTask = buffer.ProcessNextTest();

// Assert
Assert.AreEqual(1001, nextTask.WaferId);
Assert.AreEqual("VoltageTest", nextTask.TestType);
Assert.AreEqual(1, buffer.TaskCount);
}

[TestMethod]
public void WaferTestBuffer_Peek_ReturnsNextTask()
{
// Arrange
var buffer = new WaferTestBuffer(2);
var time = new DateTime(2025, 8, 6, 13, 0, 0);
buffer.AddTestTask(1001, time, "VoltageTest");

// Act
var nextTask = buffer.PeekNextTest();

// Assert
Assert.AreEqual(1001, nextTask.WaferId);
Assert.AreEqual(1, buffer.TaskCount);
}

[TestMethod]
[ExpectedException(typeof(InvalidOperationException))]
public void WaferTestBuffer_AddToFull_ThrowsException()
{
// Arrange
var buffer = new WaferTestBuffer(2);
var time = new DateTime(2025, 8, 6, 13, 0, 0);
buffer.AddTestTask(1001, time, "VoltageTest");
buffer.AddTestTask(1002, time, "DefectTest");
buffer.AddTestTask(1003, time, "CurrentTest"); // 应抛出异常
}

半导体场景说明

• 场景：测试机接收晶圆测试任务（如电压测试、缺陷检测），缓冲区容量有限（例如，硬件限制）。循环队列按提交顺序存储任务，高效利用固定容量。
• 优势：循环队列避免了前端空间浪费，适合固定容量的缓冲区，Enqueue 和 Dequeue 操作高效（O(1)）。
• 局限性：固定容量可能限制任务数量，需扩容机制或优先队列支持动态优先级。
• 优化建议：可结合优先队列（如项目中的 Min-Priority Queue）支持高优先级任务的调度，或增加动态扩容机制。

五、贴片机场景示例在贴片机 (SMT) 中，循环队列可用于管理有限的元件贴片任务缓冲区。例如，贴片机按任务到达顺序处理元件贴片任务，循环队列优化缓冲区空间利用。示例代码csharp

public class ComponentPlacementTask
{
public int ComponentId { get; set; }
public double X { get; set; }
public double Y { get; set; }
public DateTime SubmissionTime { get; set; }

public ComponentPlacementTask(int componentId, double x, double y, DateTime submissionTime)
{
ComponentId = componentId;
X = x;
Y = y;
SubmissionTime = submissionTime;
}
}

public class SmtPlacementBuffer
{
private CircularQueue<ComponentPlacementTask> taskBuffer;

public SmtPlacementBuffer(int capacity)
{
taskBuffer = new CircularQueue<ComponentPlacementTask>(capacity);
}

public void AddPlacementTask(int componentId, double x, double y, DateTime submissionTime)
{
if (taskBuffer.IsFull)
throw new InvalidOperationException("Placement buffer is full");
taskBuffer.Enqueue(new ComponentPlacementTask(componentId, x, y, submissionTime));
}

public ComponentPlacementTask ProcessNextPlacement()
{
return taskBuffer.Dequeue();
}

public ComponentPlacementTask PeekNextPlacement()
{
return taskBuffer.Peek();
}

public int TaskCount => taskBuffer.Count;

public bool IsFull => taskBuffer.IsFull;
}

测试用例csharp

[TestMethod]
public void SmtPlacementBuffer_AddAndProcess_ReturnsCorrectTask()
{
// Arrange
var buffer = new SmtPlacementBuffer(2);
var time = new DateTime(2025, 8, 6, 13, 0, 0);
buffer.AddPlacementTask(2001, 10.5, 20.5, time);

// Act
var nextTask = buffer.ProcessNextPlacement();

// Assert
Assert.AreEqual(2001, nextTask.ComponentId);
Assert.AreEqual(10.5, nextTask.X);
Assert.AreEqual(20.5, nextTask.Y);
Assert.AreEqual(0, buffer.TaskCount);
}

[TestMethod]
public void SmtPlacementBuffer_CircularBehavior_WorksCorrectly()
{
// Arrange
var buffer = new SmtPlacementBuffer(2);
var time = new DateTime(2025, 8, 6, 13, 0, 0);
buffer.AddPlacementTask(2001, 10.5, 20.5, time);
buffer.AddPlacementTask(2002, 15.0, 25.0, time);
buffer.ProcessNextPlacement(); // 移除 2001
buffer.AddPlacementTask(2003, 12.0, 22.0, time); // 循环利用空间

// Act
var nextTask = buffer.ProcessNextPlacement();

// Assert
Assert.AreEqual(2002, nextTask.ComponentId);
Assert.AreEqual(1, buffer.TaskCount);
}

贴片机场景说明

• 场景：贴片机接收元件贴片任务（包括元件 ID 和坐标），缓冲区容量有限。循环队列按任务到达顺序存储任务，高效利用空间。
• 优势：循环队列的 O(1) 操作和空间复用适合高频贴片任务的缓冲区管理。
• 局限性：固定容量可能限制任务数量，需扩容机制或优先级调度。
• 优化建议：可结合优先队列优化贴片任务优先级，或使用数组列表存储任务历史以支持查询。

六、总结与注意事项

如果您需要更详细的循环队列实现（如线程安全版本或基于链表的变体）、其他算法或数据结构的解析，或针对特定半导体设备（如晶圆切割机）的定制代码，请进一步说明，我将提供更深入的示例！