C# 中的循环队列数据结构

• 下载源代码文件 - 8.36 KB
• 下载演示项目 - 5.93 KB

引言

我最近有一个需求，需要使用一个长度有限的队列数据结构，因为内存有限。因此，我倾向于采用循环队列数据结构。当我搜索互联网上的循环队列时，我没有找到很多相关信息，所以我决定写这篇文章。

循环队列遵循队列数据结构的的基本规则。它具有先进先出机制，但其大小受到限制。我们需要跟踪两个术语来理解、实现和使用循环队列：

1. 前部位置（从这里可以出队）
2. 后部位置（队列中最后一个元素的位置）

我使用 ArrayList 数据类型在 C# 中实现了这个功能。

我们公开的两个方法是 Enqueue 和 Dequeue（传统的队列方法）。我还添加了一个 ResetQueue 方法来将队列重置为其初始状态。这种数据结构的主要要求是实现一个受限制数量的占位符，它可以容纳插入到队列中的对象实例。

代码

初始化

在构造函数中，我们的循环队列类将接受一个整数参数来设置其 MaxQueueSize 属性。整个队列实现都基于最大队列大小。在任何典型的应用场景中，这个最大大小都需要根据对象实例将占用多少内存以及可以为我们的队列分配多少内存来选择。最初，FrontPosition 设置为零，RearPosition 设置为 -1。

Enqueue()

如果队列有任何空闲位置，Enqueue 方法将在 RearPosition+1 处向循环队列添加一个元素（对象）。如果没有空闲位置，该方法将返回 false。

public bool Enqueue(object obj)
{
    if((nRearPosition == (nMaxSize-1) && nFrontPosition==0) ||
             ((nRearPosition!=-1)&&(nRearPosition+1)==nFrontPosition))
        return false;
    if(nRearPosition == (nMaxSize -1) && nFrontPosition > 0)
       nRearPosition = -1;
    nRearPosition+=1;
    alstQueueContent[nRearPosition] = obj;
    if((nRearPosition-1) == nFrontPosition && 
               alstQueueContent[nFrontPosition]==null)
       nFrontPosition = nFrontPosition+1;
    return true;
}

Dequeue()

如果队列在 FrontPosition 指向的位置有任何元素，Dequeue 方法将从循环队列中删除该元素（对象）并递增 FrontPosition。当 FrontPosition 等于 MaxSize -1 时，在出队操作之后，FrontPosition 必须设置为 0，而不是递增。

public object Dequeue()
{
    object Output = "Empty" ;
    if(alstQueueContent[nFrontPosition] != null)
    {
        Output = alstQueueContent[nFrontPosition];
        alstQueueContent[nFrontPosition]=null;
        if((nFrontPosition+1)<nMaxSize && 
                alstQueueContent[nFrontPosition+1] !=null)
            nFrontPosition += 1;
        else if(alstQueueContent[0] !=null && (nFrontPosition+1)== nMaxSize)
            nFrontPosition = 0;
    }
    return Output; 
}

完整的实现作为一个可下载的附件提供。