队列——一种操作受限的线性表

队列

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队，删除元素称为出队或离队。队列中的元素是先进先出（First In First Out，FIFO）。

队头（Front）：允许删除的一端，又称队首。

队尾（Rear）：允许插入的一端。

		————————————————————
出队列<---- a1 a2 a3 a4 a5 <-----入队列
		————————————————————
		^				^
		|				|
		队头			 队尾

循环队列

用数组实现循环队列

#define MAX_SIZE 6
typedef int ElemType;
typedef struct {
    // 数组 存储MAX_SIZE - 1个元素
    ElemType data[MAX_SIZE];
    // 队列头 队列尾
    int front, rear;
} SqQueue;

请添加图片描述

#include <stdio.h>


#define MAX_SIZE 6
typedef int ElemType;
typedef struct {
    // 数组 存储MAX_SIZE - 1个元素
    ElemType data[MAX_SIZE];
    // 队列头 队列尾
    int front, rear;
} SqQueue;


/*
 * 初始化循环队列
 */
void init_queue(SqQueue &Q) {

    // 初始化循环队列: 让头部和尾部都指向零号
    Q.front = Q.rear = 0;
}


/*
 * 判断循环队列是否为空
 */
bool queue_empty(SqQueue Q) {
    return Q.front == Q.rear;
}


/*
 * 入队
 */
bool enqueue(SqQueue &Q, ElemType data) {
    // 判断队列是否已满
    if ((Q.rear + 1) % MAX_SIZE == Q.front) {
        return false;
    }

    // 放入元素
    Q.data[Q.rear] = data;
    // rear加1
    Q.rear = (Q.rear + 1) % MAX_SIZE;

    return true;
}


/*
 * 出队
 */
bool dequeue(SqQueue &Q, ElemType &elem) {
    // 判断队列是否为空
    if (queue_empty(Q)) {
        return false;
    }

    // 队首元素
    elem = Q.data[Q.front];
    // front加1
    Q.front = (Q.front + 1) % MAX_SIZE;

    return true;
}

int main() {

    SqQueue Q;
    // 一、初始化循环队列
    init_queue(Q);

    // 二、判断循环队列是否为空
    bool ret = queue_empty(Q);
    if (ret) {
        printf("queue is empty\n");
    }

    // 三、入队
    enqueue(Q, 3);
    enqueue(Q, 4);
    ret = enqueue(Q, 5);
    if (ret) {
        printf("enqueue success\n");
    } else {
        printf("enqueue failed\n");
    }

    // 四、出队
    ElemType elem;
    ret = dequeue(Q, elem);
    if (ret) {
        printf("dequeue succes, elem = %d\n", elem);
    } else {
        printf("dequeue failed\n");
    }
    
    enqueue(Q, 6);
    enqueue(Q, 7);
    enqueue(Q, 8);
    ret = enqueue(Q, 9);

    return 0;
}

队列

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

链表尾插法实现入队，链表头删法实现出队。

请添加图片描述

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

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

// 链表 先进先出
typedef struct LinkQueue {
    // 链表头/队头 链表尾/队尾
    LinkNode *front, *rear;
} LinkQueue;


/*
 * 队列的初始化（带头结点的链表实现）
 */
void init_queue(LinkQueue &Q) {
    // 头和尾指向同一个结点
    Q.front = Q.rear = (LinkNode *) malloc(sizeof(LinkNode));
    // 头结点的next指针为NULL
    Q.front->next = NULL;
}


/*
 * 判断队列是否为空
 */
bool queue_empty(LinkQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    }

    return false;
}


/*
 * 入队
 */
void enqueue(LinkQueue &Q, ElemType data) {
    LinkNode *new_node = (LinkNode *) malloc(sizeof(LinkNode));
    new_node->data = data;
    new_node->next = NULL;

    // 尾指针的next指向new_node
    Q.rear->next = new_node;
    // rear指向新的尾部
    Q.rear = new_node;
}


/*
 * 出队
 */
bool dequeue(LinkQueue &Q, ElemType &elem) {
    // 判断队列是否为空
    if (queue_empty(Q)) {
        return false;
    }

    // 第一个结点
    LinkNode *q = Q.front->next;
    elem = q->data;
    Q.front->next = q->next;

    // 链表只剩一个结点时 被删除后 要改变rear
    if (Q.rear == q) {
        Q.rear = Q.front;
    }

    //让第一个结点断链
    free(q);

    return true;
}


int main() {
    // 新建队列
    LinkQueue Q;

    // 一、初始化队列
    init_queue(Q);

    // 二、判断队列是否为空
    bool ret = queue_empty(Q);
    if (ret) {
        printf("queue is empty\n");
    }

    // 三、入队
    enqueue(Q, 3);
    enqueue(Q, 4);
    enqueue(Q, 5);

    // 四、出队
    ElemType elem;
    dequeue(Q, elem);
    dequeue(Q, elem);
    ret = dequeue(Q, elem);
    if (ret) {
        printf("dequeue success element = %d\n", elem);
    } else {
        printf("dequeue failed\n");
    }

    return 0;
}