C語言中文網 目錄
首頁 > 編程筆記 > C++筆記 閱讀:278

鏈隊列及(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;
}
程序輸出結果:

Enqueuing 5 items...
The values in the queue were:
1 4 9 16 25

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo