65.9K
CodeProject 正在变化。 阅读更多。
Home

优化的队列

Javed Akhtar Ansari
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.80/5 (5投票s)

2010年5月11日

CPOL

4分钟阅读

viewsIcon

29977

downloadIcon

369

优化的队列

QueueDemo

CircularQueue.PNG

引言

本文演示并创建了一个优化的队列数据结构，即循环队列。队列是最重要的数据结构之一。我们看到队列最常见的应用场景是打印。我们只能从队首插入元素，而只能从队尾移除元素。循环队列是线性队列的优化版本，因为它在弹出操作后会重新利用分配的空间。STL 也有一个名为 queue 的容器。我们在这里理解的定义和术语也适用于 STL queue 容器。

队列可以是通过数组或链表来实现。但链表本身是一个很大的数据结构，可以作为另一个详细讨论的话题，所以我们在这里将使用数组来演示队列。

其他细节

我还将在本文中解释一些 C++ 的其他特性，例如模板和流。
模板用于创建不指定确切数据类型的通用数据类型的类和库。当编译器在代码中看到其用法时，它会创建一个数据类型的版本。我们将使用模板创建一个 CCircularQueue 类。关于模板的一个重要注意事项是，它必须仅定义在 .h 文件中，以便所有代码都能传播到 #includes 该 .h 文件的所有文件中。这是编译器所必需的，因为它需要随时获取所有模板代码来生成特定数据类型的版本。

CCircularQueue 类的详细信息

以下是我们队列类提供的结构和函数

template <typename T>
class CCircularQueue 
{
private:
    int m_iCapacity;
    int m_iSize;
    T * m_arrContainer;
    int m_iRear, m_iFront;
    void Resize();    //Doubles the internal array
public:
    CCircularQueue();
    ~CCircularQueue();
    /****  Functions  *****/
    void Push(const T& elem);  //Adds an element in the queue
    T& Pop();     		//Removes an element from the queue and returns a reference. 
			//Does not destroy the element 
    bool IsEmpty();    	//Checks if the queue is empty
    void Clear();    	//Clears the whole queue. Does not destroy the objects
    int Size();     	//Returns the size
    void Print(ostream & os);  //Print the queue on to a console
};

m_arrContainer 是一个指向通用数据类型 T 的指针，用于创建动态数组。在构造函数中

template <typename T> CCircularQueue<T>::CCircularQueue():m_iCapacity(100)
, m_iSize(0)
, m_iRear(-1)
, m_iFront(-1)
{
    m_arrContainer = new T[m_iCapacity];
}

m_iRear 和 m_iFront 最初指向空（-1），但当我们插入第一个元素时，两者都指向它，即 0th 位置。当我们继续插入时，m_iRear 将继续指向 0th 位置，而 m_iFront 将继续增加其位置。弹出元素时情况相反。m_iFront 将继续指向同一个元素，但 m_iRear 将继续增加其位置。

队列的初始容量为 100，但在运行时如果需要更多空间，它会自动增长到前一个大小的两倍。您可以使用这两个函数随时获取队列的实际大小和容量

template <typename T> int CCircularQueue<T>::Size()
{
    return m_iSize;
}
template <typename T> int CCircularQueue<T>::Capacity()
{
    return m_iCapacity;
}

所有这些中最重要的是 Push() 函数，其定义如下

template <typename T> void CCircularQueue<T>::Push(const T& elem)
{
    //Case 1: queue is empty
    if(m_iRear == -1) 
    {
        m_arrContainer[++m_iRear] = elem;
        m_iFront = m_iRear; 
        m_iSize++; 
    }
    //Case 2: Still there is space available at the end
    else if((m_iFront < m_iCapacity-1) && (m_iFront+1 != m_iRear) )
    {
        m_arrContainer[++m_iFront] = elem;
        m_iSize++; 
    }
    //Case 3: We reached to end but space available at other end. 
    //Take advantage of circular queue
    else if(m_iFront == m_iCapacity-1 && m_iRear != 0) 
    {
        m_iFront = 0;
        m_arrContainer[m_iFront] = elem;
        m_iSize++; 
    } 
    //Case 4: No space available
    else
    {
        Resize();
        Push(elem);
    }
}

我将在下面演示每种情况。

情况 1：队列为空。
此时 front 和 rear 都指向 -1。所以只需插入元素，然后将两个指针都移动到指向第一个元素。

情况 2：队尾仍有可用空间。
这是一个正常情况，前面有可用空间。由于循环性质，该条件确保下一个元素不会被 rear 指向。

情况 3：我们已到达队尾，但队首还有可用空间。利用循环队列的优势。

下图展示了这一点

                                                         Push 前

CircularQueue_BeforePush.PNG

 

                                                            Push 后

CircularQueue_AfterPush.PNG

这种情况实际上演示了循环队列。如果我们 Pop 掉一个元素，它将从队列的开头被移除，因此 rear 指针将向前移动相应的位置，使这些空间可用于其他 Push 操作。

情况 4：没有可用空间。
在所有其他情况下，队列已满。在这里，我们将数组容器的大小调整为前一个大小的两倍，然后递归地再次调用 Push 函数来插入元素。
resize 函数定义如下

template <typename T> void CCircularQueue<T>::Resize()
{
    T * arrTemp = new T[2*m_iCapacity];
    int j = -1;
    for(int i = m_iRear; i <= m_iFront ; i++ )
    {
       arrTemp[++j] = m_arrContainer[i];
    }
    if(m_iFront < m_iRear)
    {
       for(int i = m_iRear;  i < m_iCapacity; i++)
       {
          arrTemp[++j] = m_arrContainer[i];
       }
       for(int i = 0; i<= m_iFront; i++)
       {
          arrTemp[++j] = m_arrContainer[i];
       }
    }
    delete [] m_arrContainer;
    m_arrContainer = arrTemp;
    m_iRear = 0;
    m_iFront = j;
    m_iCapacity*=2;
}

总而言之，它所做的是重新分配一个两倍大小的新数组，将所有元素从 rear 复制到 front 到新数组，销毁原始数组，并将 m_arrContainer 指向新数组。
Pop() 函数定义如下

template <typename T> T& CCircularQueue<T>::Pop()
{
    if(m_iRear == -1)
    throw new CGenericException("The queue is already empty\n");
    T &elem = m_arrContainer[m_iRear];
    if(m_iRear == m_iFront)  //The queue is empty now
    m_iRear = m_iFront = -1;
    else if(m_iRear == m_iCapacity -1)
    m_iRear = 0;
    else 
    m_iRear++;
    m_iSize--;
    return elem;
}

请注意，它实际上并没有销毁元素，而是简单地返回对元素的引用。用户应在堆上分配内存后删除内存。这是所有 STL 库的标准做法。

如果我们尝试从空队列弹出，该函数将抛出异常。CGenericException 类是用户定义的，仅用于显示信息。
还有其他函数，它们是不言自明的。

  • bool IsEmpty()：检查队列是否为空。
  • int Size()：返回队列的大小。
  • int Capacity()：返回队列的当前容量。
  • void Print(ostream & os)：将元素打印到提供的流中。
    如果要将输出打印到控制台，如提供的示例所示，则像这样传递 cout 流
    CCircularQueue<int> cqInt;
cqInt.Push(5);
cqInt.Print(cout)

    如果要将此写入文件，则像这样传递文件流

    ofstream os("c:\\test.txt", ios::out /*| ios::app*/);
cqInt.Print(os);
os.close();

本文到此结束。您可以下载源代码并深入研究。您也可以通过仅包含源文件在您的项目中使�?这个类。

历史

  • 首次创建于 2010 年 5 月 11 日
© . All rights reserved.