C++模闆實作隊列（1）

隊列是一種先進先出（FIFO）的資料結構，常見的隊列有鍊式隊列和循環隊列，鍊式隊列結構簡單，比較容易實作，但是效率不如循環隊列；這裡同時使用C++模闆程式設計來實作這兩種隊列。

首先是鍊式隊列，這裡的鍊式隊列采用雙連結清單的結構，一頭一尾分别使用一個指針。如下圖所示：

之是以采用雙連結清單結構是因為，這樣做元素出隊的時候比較好實作，直接根據head->prev就可以找到它的前驅節點，然後删掉原來的節點就可以。

節點定義為下面這樣的資料結構：

template<typename T>
struct Node
{
    T item;
    Node* next;
    Node* prev;
};
           

鍊式隊列類的聲明：

template<typename T>
class LQueue
{
private:
    Node<T>* head;
    Node<T>* rear;
    unsigned int cnt;
public:
    LQueue();//構造函數
    ~LQueue();//析構函數
    void enqueue(T item);//入隊
    void dequeue();//出隊
    unsigned int size(){ return cnt; }//擷取隊列目前元素個數
    bool isempty(){ return cnt ==  ? true : false; }//判斷隊列是否為空
    T getHead();//擷取隊頭的元素
};
           

實作代碼：

template<typename T>
LQueue<T>::LQueue()
{
    cnt = ;
    Node<T>* anode = new Node<T>;
    anode->next = NULL;
    anode->prev = NULL;
    head = anode; 
    rear = anode;
}
template<typename T>
LQueue<T>::~LQueue()
{
    Node<T>* p = head;
    for (int i = ; i < cnt; i++)
    {
        dequeue();
    }
}
template<typename T>
void LQueue<T>::enqueue(T item)
{
    if (cnt == )
    {
        rear->item = item;
        cnt++;
    }
    else
    {
        Node<T>* anode = new Node<T>;
        anode->item = item;
        anode->next = rear;
        rear->prev = anode;
        rear = anode;
        rear->prev = NULL;
        cnt++;
    }
}
template<typename T>
void LQueue<T>::dequeue()
{
    if (isempty())
    {
        cout << "Error: This LQueue is empty" << endl;
        cout << "File Path =" << __FILE__ << endl;
        cout << "Function Name =" << __FUNCTION__ << endl;
        cout << "Line =" << __LINE__ << endl;
    }
    Node<T>* p = head;
    head = p->prev;
    delete p;
    cnt--;
}
template<typename T>
T LQueue<T>::getHead()
{
    return head->item;
}
           

選擇顧客排隊付款作為測試例子；

#include<iostream>
#include<string>
#include"myQueue.h"
using namespace std;
using std::string;
typedef struct
{
    double amount;
    string vipnum;
    double discount;
}Customer_t;

int main()
{
    LQueue<Customer_t> lq;
    Customer_t temp;
    cout<<"lq.size()="<<lq.size()<<endl;
    for (int i = ; i < ; i++)
    {
        cout << "No." << i << endl;
        cout << "vip number:";
        cin >> temp.vipnum;
        cout << "discount:";
        cin >> temp.discount;
        cout << "amount:";
        cin >> temp.amount;
        lq.enqueue(temp);
        cout << "size=" << lq.size() << endl;
    }
    for (int i = ; i < ; i++)
    {
        temp = lq.getHead();
        cout << "No." << i << " customer" << endl;
        cout << "vip number:" << temp.vipnum << endl;
        cout << "discount:" << temp.discount << endl;
        cout << "amount:" << temp.amount << endl;
        lq.dequeue();
        cout << endl;
    }

    system("pause");
    return ;
}