队列简介

数据结构中的队列与日常生活中排队是一致的，最早进入队列的元素最早离开，与栈（先进后出）相反。在队列中允许插入的一端叫做队尾，允许删除的一端叫做队头。

queue.png

在程序设计中最经典的一个队列例子就是操作系统中的作业排队。

链式队列实现

用链表表示的队列简称为链队列

队列节点定义如下：

typedef struct Qnode {
    int data;
    struct Qnode* next;
}Qnode, * QueuePtr;

由首尾指针确定链队列;

typedef struct LinkQueue {
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

为了方便操作我们给链队列添加一个头节点：

head.png

头节点存储无效数据，并指向队头，当队列为空时rear也指向头节点。

队列的主要操作函数

主要操作的函数说明：

void InitQueue(LinkQueue& Q);
//构造一个空队列Q
void DestoryQueue(LinkQueue& Q);
//销毁队列Q
bool EnQueue(LinkQueue& Q, int data);
//插入新元素data到队尾
int DeQueue(LinkQueue& Q);
//删除队头元素，并返回元素值
bool EmptyQueue(LinkQueue Q);
//判断队列是否为空

函数实现

初始化队列：

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

销毁队列：

void DestoryQueue(LinkQueue& Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
}

入队列

bool EnQueue(LinkQueue& Q,int data) {
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(Qnode));
    if (!p) {
        return false;
    }
    p->data = data;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return true;
}

判断空队列

bool EmptyQueue(LinkQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    }
    else {
        return false;
    }
}

出队列：

int DeQueue(LinkQueue& Q) {
    QueuePtr p;
    int result;
    if (EmptyQueue(Q)) {
        return Empty;
    }
    p = Q.front->next;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    result = p->data;
    free(p);
    return result;
}

测试

主函数：

void main() {
    int n,i,data;
    LinkQueue Q;
    InitQueue(Q);
    printf("队列初始化完成\n");
    //DestoryQueue(Q);
    printf("请输入要添加的队列元素数量：\n");
    scanf_s("%d", &n);
    i = 1;
    while (i <= n) {
        printf("请输入第%d个队列元素：\n",i);
        scanf_s("%d", &data);
        EnQueue(Q, data);
        i++;
    }
    printf("队列添加完成\n");
    printf("队列元素：");
    while (EmptyQueue(Q) == false) {
        data = DeQueue(Q);
        printf("%d ", data);
    }
}

result.png