單隊列的鍊式表示和實作

隊列是操作受限的線性表，隻允許在隊尾插入元素，在隊頭删除元素，為了便于插入元素，設立隊尾指針。這樣，插入元素的操作與隊列長度無關

隊列的鍊式存儲結構

typedef struct QNode
{
    QElemType data;
    QNode *next;
}*QueuePtr;
struct LinkQueue
{
    QueuePtr front, rear;//隊頭，隊尾指針
};
           

鍊隊列的9個基本操作

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
}

void DestroyQueue(LinkQueue &Q){
    while (Q.front)//Q.front不為空
    {
        Q.rear = Q.front->next;//Q.rear指向Q.front的下一個結點
        free(Q.front);//釋放Q.front所指結點
        Q.front = Q.rear;//Q.front指向Q.front的下一個結點
    }
}

void ClearQueue(LinkQueue &Q){
    DestroyQueue(Q);//銷毀隊列Q
    InitQueue(Q);//重新構造空隊列
}

Status QueueEmpty(LinkQueue Q){
    if (Q.front->next == NULL) return TRUE;
    else return FALSE;
}

int QueueLength(LinkQueue Q){
    int i = ;
    QueuePtr p = Q.front;//p指向頭結點
    while (Q.rear != p)//p所指不是尾結點
    {
        i++;
        p = p->next;//p指向下一個結點
    }
    return i;
}

Status GetHead(LinkQueue Q, QElemType &e){
    if (Q.front == Q.rear) return ERROR;//隊列空
    QueuePtr p = Q.front->next;//p指向隊頭結點
    e = p->data;//将隊頭元素的值賦給e
    return OK;
}

void EnQueue(LinkQueue &Q, QElemType e){//插入元素e為隊列Q的新的隊尾元素
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));//動态生成新結點
    if (!p) exit(OVERFLOW);
    p->data = e;
    p->next = NULL;//新結點的指針域為空
    Q.rear->next = p;//原隊尾結點的指針指向新結點
    Q.rear = p;//尾指針指向新結點
}

Status DeQueue(LinkQueue &Q, QElemType &e){//若隊列Q不空，删除Q的隊頭元素
    QueuePtr p;
    if (Q.front == Q.rear) return ERROR;//隊列空
    p = Q.front->next;//p指向隊頭結點
    e = p->data;//将隊頭元素的值賦給e
    Q.front->next = p->next;//頭結點指向下一個結點
    if (Q.rear == p)//删除的是隊尾結點
        Q.rear = Q.front;//修改隊尾指針指向頭結點（空隊列）
    free(p);//釋放隊頭結點
    return OK;
}

void ListTraverse(LinkQueue Q, void(*visit)(ElemType&)){
    QueuePtr p = Q.front->next;//p指向隊頭結點
    while (p)//p指向結點
    {
        visit(p->data);
        p = p->next;
    }
    printf("\n");
}