隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其實(shí)就是線性表的單鏈表，只不過它只能尾進(jìn)頭出而已，通常簡(jiǎn)稱為鏈隊(duì)列。為了操作上的方便，將隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn)，隊(duì)尾指針指向終端結(jié)點(diǎn)。

當(dāng)隊(duì)列為空時(shí)，front和rear都指向頭結(jié)點(diǎn)。

鏈隊(duì)列的結(jié)構(gòu)定義如下所示：

typedef  int QElemType; 
//QNode代表隊(duì)列中元素的結(jié)點(diǎn) 
//QueuePtr指針指向當(dāng)前鏈隊(duì)列 
typedef  struct QNode { 
    QElemType data;     
    struct QNode *next; 
}QNode, *QueuePtr; 
//定義鏈隊(duì)列的結(jié)構(gòu) 
//front表示隊(duì)頭指針 
//rear表示隊(duì)尾指針 
typedef  struct{ 
    QueuePtr front, rear; 
}LinkQueue; 

鏈隊(duì)列的初始化：

LinkQueue *InitQueue() 
{ 
    LinkQueue *Q = new LinkQueue; 
    Q->front = Q->rear = new QNode;     
    if (!Q->front)return 0; 
    Q->front->next = NULL;     
    return Q; 
} 

鏈隊(duì)列的入隊(duì)操作：

//鏈隊(duì)列的入隊(duì)操作 
bool EnQueue(LinkQueue *Q, QElemType e) 
{ 
    QueuePtr s = new QNode;     
    if (!s) 
    {         
        cout << "分配失敗" << endl;         
        return false; 
    } 
    s->data = e; 
    s->next = NULL; 
    Q->rear->next = s; 
 
    Q->rear = s;     
    cout << e << endl;     
    return true; 
} 

鏈隊(duì)列的出隊(duì)操作：

[[237267]]

//鏈隊(duì)列的出隊(duì)操作 
bool DeQueue(LinkQueue *Q, QElemType *e) 
{ 
    QueuePtr p;     
    if (Q->front == Q->rear) 
    {         
        cout << "空隊(duì)" << endl;         
        return false; 
    } 
    p = Q->front->next; 
    *e = p->data; 
    Q->front->next = p->next;     
    if (Q->rear == p) 
    { 
        Q->rear = Q->front; 
    }     
    cout << *e << endl;     
    delete p;     
    return true; 
} 

主函數(shù)中測(cè)試代碼如下：

int main() 
{ 
    LinkQueue *lq = InitQueue();     
    cout << "入隊(duì)的元素:" << endl;     
    for (auto i = 0; i < 10; i++) 
    { 
        EnQueue(lq, i); 
    }     
    int temp = 0;     
    //出隊(duì)的元素 
    cout << "出隊(duì)的元素:" << endl;     
    for (auto i = 0; i < 4; i++) 
    { 
        DeQueue(lq, &temp); 
    }     
    return 0; 
} 

輸出如下所示：