链队列及（C++）实现详解

围绕链表构建的动态队列比静态队列更直观。一个动态队列将作为一个空链表开始。在第一次入队操作中，增加了一个结点，并且 front 和 rear 指针均指向它。随着每个新项目被添加到队列中，新的结点被添加到链表的后面，并且 rear 指针被更新以指向新结点。

当有项目要出队时，使 front 指向链表中的下一个结点，然后删除先前 front 所指向的结点。 图 1 显示了一个动态队列的结构。

图 1 实现为链表的动态队列

动态整数队列类 DynIntQueue 的代码清单如下所示：

//DynIntQueue.h
class DynIntQueue
{
    struct QueueNode
    {
        int value;
        QueueNode *next;
        QueueNode(int value1, QueueNode *next1 = nullptr)
        {
            value = value1;
            next = next1;
        }
    };
    // These track the front and rear of the queue
    QueueNode *front;
    QueueNode *rear;
  public:
    // Constructor and Destructor
    DynIntQueue();
    ~DynIntQueue();
    // Member functions
    void enqueue(int);
    void dequeue(int &);
    bool isEmpty() const;
    void clear();
};
//DynIntQueue.cpp
#include <iostream>
#include "DynIntQueue.h"
#include <cstdlib>
using namespace std;
DynIntQueue::DynIntQueue()
{
    front = nullptr;
    rear = nullptr;
}

DynIntQueue::~DynIntQueue()
{
    QueueNode * garbage = front;
    while (garbage != nullptr)
    {
        front = front->next;
        garbage->next = nullptr;
        delete garbage;
        garbage = front;
    }
}
void DynIntQueue::enqueue(int num)
{
    if (isEmpty())
    {
        front = new QueueNode(num);
        rear = front;
    }
    else
    {
        rear->next = new QueueNode(num);
        rear = rear->next;
    }
}
void DynIntQueue::dequeue(int &num)
{
    QueueNode *temp = nullptr;
    if (isEmpty())
    {
        cout << "The queue is empty.\n";
        exit(1);
    }
    else
    {
        num = front->value;
        temp = front;
        front = front->next;
        delete temp;
    }
}
bool DynIntQueue::isEmpty() const
{
    if (front == nullptr)
        return true;
    else
        return false;
}

void DynIntQueue::clear()
{
    int value; // Dummy variable for dequeue
    while (!isEmpty())
        dequeue(value);
}

下面的程序是一个驱动模块程序，它演示了 DynIntQueue 类的使用：

// This program demonstrates the DynIntQueue class
#include <iostream>
#include "DynIntQueue.h"
using namespace std;

int main()
{
    DynIntQueue iQueue;
    cout << "Enqueuing 5 items...\n";
    // Enqueue 5 items
    for (int k = 1; k <= 5; k++)
        iQueue.enqueue(k*k);
    // Deqeue and retrieve all items in the queue
    cout << "The values in the queue were: \n";
    while (!iQueue.isEmpty())
    {
        int value;
        iQueue.dequeue(value);
        cout << value << " ";
    }
    return 0;
}

程序输出结果：