C++队列的链式存储代码实现

队列的链式存储代码实现

队列初始化、判断是否为空、入队尾插法、出队头部删除

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode {
    ElemType data;
    struct LinkNode* next;
} LinkNode;

typedef struct {
    LinkNode *front, *rear;
} LinkQueue; // 先进先出

// 队列的初始化，使用的是带头节点的链表来实现的
void initQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL; // 头指针指向
}

// 是否为空 
bool isEmpty(LinkQueue Q){
	return (Q.front->next == NULL);
}

// 入队，尾插法
void enQueue(LinkQueue &Q, ElemType e) {
    LinkNode* p = (LinkNode*)malloc(sizeof(LinkNode));
    p->data = e;
    p->next = NULL;   // next指向NULL
    Q.rear->next = p; // 尾指针的 next指向p，因为要从尾部入队
    Q.rear = p;       // rear要指向新的尾部
}
// 出队,头部删除方法
bool deQueue(LinkQueue &Q, ElemType &e) {
    // 判断队列为空
    if (Q.front == Q.rear) {
        return false;
    }
    LinkNode *p = Q.front->next;
    e = p->data;
    Q.front->next=p->next;//断链
    if(Q.rear==p){//删除的是最后一个元素
        Q.rear=Q.front;//队列置为空
    }
    free(p);
    return true;
}

// 头部删除，尾部入队
int main() {
    LinkQueue Q;
    bool ret;
    // 初始化队列
    initQueue(Q);
    // 判断队列是否为空
    ret = isEmpty(Q);
    if(ret){
        printf("队列为空\n");
    }else {
        printf("队列不为空\n");
    }
    // 入队，尾插法
    enQueue(Q, 2);
    enQueue(Q, 3);
    enQueue(Q, 4);
    enQueue(Q, 5);
    enQueue(Q, 6);
    // 出队
    ElemType e;
    ret = deQueue(Q,e);
    if (ret) {
       printf("出队元素：%d\n",e);
    }else{
       printf("出队失败");
    }
    return 0;
}