C#循环顺序队列与链式队列实现详解
队列是一种特殊的线性表，遵循“先进先出”（FIFO）原则，限制元素仅在表尾添加、在表头删除。本文详细介绍C#中通过数组实现的循环顺序队列（解决空间浪费的伪满问题）和基于链表的链式队列的完整泛型实现。
队列的核心特征与接口设计
队列的本质是将数据存取限制在线性结构的两端：入队（Enqueue）只能在尾部进行，出队（Dequeue）只能在头部进行。这种机制广泛应用于操作系统任务调度、消息缓冲区及算法模拟等场景。
为了实现通用的队列逻辑，首先定义一个泛型接口 IQueue<T>，包含以下基本操作：
Count()：获取当前元素数量。IsEmpty()/IsFull()：判断队列状态。Clear()：清空队列。Enqueue(T item)：向队列尾部插入元素。Dequeue()：从队列头部取出并删除元素。Peek()：查看队列头部元素但不删除。
namespace 栈与队列
{
public interface IQueue<T>
{
public int Count();
public bool IsEmpty();
public void Clear();
public void Enqueue(T item);
public T Dequeue();
public T Peek();
}
}循环顺序队列的实现原理
顺序队列通常使用数组存储。如果使用简单的线性数组，随着元素的出入队，头部会产生大量空闲空间而无法复用，导致数组溢出，这被称为“假溢出”或“伪满”现象。
为了解决这个问题，我们将数组想象成首尾相接的环状结构。当 rear 指针到达数组末尾时，将其重置为 0。但在循环结构中，仅凭 front == rear 无法区分是队空还是队满。通用的解决方案是牺牲数组的一个存储单元：当 (rear + 1) % size == front 时，判定为队满。
循环顺序队列完整代码
以下是处理了边界跳转（rear = 0）、容量判断及计数逻辑的 CSeqQueue<T> 类实现：
using System;
using System.Text;
namespace 栈与队列
{
/// <summary>
/// 循环顺序队列，解决普通顺序队列的假溢出问题
/// </summary>
public class CSeqQueue<T> : IQueue<T>
{
private int maxsize;
private T[] data;
private int front; // 指向队头元素的前一个位置
private int rear; // 指向队尾元素的位置
public CSeqQueue(int size)
{
data = new T[size];
maxsize = size;
front = rear = -1; // 初始状态均为-1
}
public int Count()
{
if (rear > front)
{
return rear - front;
}
else
{
// 发生回绕时的计算公式
return (rear - front + maxsize) % maxsize;
}
}
public bool IsEmpty() { return front == rear; }
public bool IsFull()
{
if (front != -1) // 经历过出队操作后，必须按循环规则判断
{
return (rear + 1) % maxsize == front;
}
else
{
// 初始状态下，如果rear已满则是真满
return rear == maxsize - 1;
}
}
public void Clear() { front = rear = -1; }
public void Enqueue(T item)
{
if (IsFull())
{
Console.WriteLine("Queue is full");
return;
}
// 关键循环逻辑：到达数组末尾则重置为0
if (rear == maxsize - 1) rear = 0;
else rear++;
data[rear] = item;
}
public T Dequeue()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty");
return default(T);
}
// 关键循环逻辑：front到达末尾重置为0
if (front == maxsize - 1) front = 0;
else front++;
return data[front];
}
public T Peek()
{
if (IsEmpty())
{
Console.WriteLine("Queue is empty!");
return default(T);
}
// 取下一个位置的元素，同样需要模运算防止越界
return data[(front + 1) % maxsize];
}
//... ToString方法用于调试输出...
}
}在此实现中，Enqueue 和 Dequeue 都包含了 if (index == maxsize - 1) index = 0; 这样的逻辑，以确保指针在环形结构中正确流转。
操作示意图解
下图展示了普通顺序队列在经历多次入队出队后的内存分布情况，直观揭示了“伪满”问题的成因：
而通过修改逻辑，将数组视为循环结构后，即便 rear 指到了最末端，也能无缝跳回开头继续利用空闲位置：
链式队列的实现方式
相较于顺序队列需要预留空间和复杂的取模运算，链式队列通过节点引用连接元素，天然具备动态扩容的特性。其核心在于维护两个引用指针：队头的 front 和队尾的 rear。
链表节点定义
每个节点包含数据域和指向下一节点的引用域：
public class Node<T>
{
public T Data { get; set; }
public Node<T> Next { get; set; }
public Node(T data, Node<T> next = null) {
this.Data = data;
this.Next = next;
}
}链式队列核心逻辑
- 入队（Enqueue）：新建节点。若为空队列，头尾指针均指向该新节点；若不为空，让旧
rear.Next指向新节点，然后更新rear为新节点。 - 出队（Dequeue）：保存当前
front节点的数据。将front移至front.Next。特别注意的是，如果移动后front变为null（即队列为空），必须同步将rear也置为null。 - Peek：直接读取
front.Data。
public class LinkQueue<T> : IQueue<T>
{
private Node<T> front;
private Node<T> rear;
private int num;
public LinkQueue() { front = rear = null; num = 0; }
public bool IsEmpty() { return front == null; }
public void Enqueue(T item)
{
var q = new Node<T>(item);
if (rear == null) front = rear = q;
else
{
rear.Next = q;
rear = q;
}
num++;
}
public T Dequeue()
{
if (IsEmpty()) return default(T);
Node<T> p = front;
front = front.Next;
if (front == null) rear = null; // 重要：清空同步
num--;
return p.Data;
}
public T Peek() => IsEmpty() ? default(T) : front.Data;
}以上就是C#数据结构之队列（Quene）实例的详细内容，更多关于C#高级数据结构的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
