链式队列

队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点。

• 空队列时，front和rear都指向头结点。
• 入队操作时，先将头结点指向新结点，再将队尾指针重新指向新结点。
• 出队操作时，先将头结点指向p的next结点，再判断p结点是不是该队列唯一结点，L->rear= p，若是front和rear都指向头结点，释放p的空间。

结构体

typedef int ElemType;
typedef struct QNode {//链表结点
    ElemType data;
    struct QNode *next;
}QNode, *QueuePtr;
typedef struct {//队列指针，分别指向队首和队尾
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

单链表新建结点

//新建结点
QueuePtr QueueNode(ElemType data) {
    QueuePtr node = (QNode *)malloc(sizeof(QNode));
    node->next = NULL;
    node->data = data;
    return node;
}

初始化队

//初始化队列
void InitLinkQueue(LinkQueue *L) {
    L->front = L->rear = (QNode *)malloc(sizeof(QNode));
    L->front->next = NULL;
}

判空

int EmptyLinkQueue(LinkQueue *L) {
    if (L->front == L->rear) {
        return 1;
    }
    return 0;
}

入队

//入队
int EnterLinkQueue(LinkQueue *L, ElemType data) {
    QueuePtr new = QueueNode(data);
    L->rear->next = new;
    L->rear = new;
    return 1;
}

出队

//出队
int DeleteLinkQueue(LinkQueue *L, ElemType *data) {
    if (L->front == L->rear) {
        printf("空队列...\n");
        return 0;
    }
    QueuePtr p = L->front->next;
    *data = p->data;
    L->front->next = p->next;
    if (p == L->rear) {
        L->front = L->rear;
    }
    free(p);
    return *data;
}

获取队头元素

//获取队头元素
int GetFrontLinkQueue(LinkQueue L, ElemType *data) {
    if (L.front == L.rear) {
        printf("空队列...\n");
        return 0;
    }
    *data = L.front->next->data;
    return *data;
}

销毁队列

//销毁队列
void ClearLinkQueue(LinkQueue *L) {
    while (L->front != NULL) {
        L->rear = L->front->next;
        free(L->front);
        L->front = L->rear;
    }
}

测试

void testLinkQueue() {
    LinkQueue q;
    InitLinkQueue(&q);
    int x;
    EnterLinkQueue(&q, 23);
    EnterLinkQueue(&q, 45);
    EnterLinkQueue(&q, 90);
    GetFrontLinkQueue(q, &x);
    printf("GetFrontLinkQueue---%d\n", x);
    DeleteLinkQueue(&q, &x);
    printf("DeleteLinkQueue----%d\n", x);
}