本文共 1931 字，大约阅读时间需要 6 分钟。

队列的基本概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表

进行插入操作的一端称为队尾（入队列） 进行删除操作的一端称为队头（出队列） 队列具有先进先出(FIFO)的特性

顺序队列

1、队头不动，出队列时队头后的所有元素向前移动

缺陷：操作时如果出队列比较多，要搬移大量元素

2、队头移动，出队列时队头向后移动一个位置

如果再有F、G进行入队操作，就会出现假溢出问题： 缺陷：容易造成队列假溢出

假溢出：顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不

能再进行入队列操作的溢出 真溢出：顺序队列最大存储空间已经存满而又要求进行入队列操作所引起 的溢出

循环队列

解决“假溢出”的办法就是后面满了，从头再开始，将头尾相接的顺序存

储队列称为循环队列 循环队列如何判断队列空和满呢？

• 采用计数器来判断，空时，计数器为0，满时，计数器为maxsize
• 另设一个标志位以匹别队列的空和满
• 少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满

优点：

循环队列的优点是相对于直线队列来讲的，直线队列在元素出队后，头指针向后移动，导致删除元素后的空间无法在利用，即使元素个数小于空间大小，依然无法再进行插入，即所谓的“假上溢”。当变成循环队列之后，删除元素后的空间仍然可以利用，最大限度的利用空间。

缺点：

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是”空”是”满”，也会面临着数组可能会溢出的问题。

链式队列

是一种特殊的链表，只在链表上进行头插和尾删的操作

优先级队列

带有优先级的队列称为优先级队列

队列具有先进先出的特性，即最先进入队列的元素将被最先出队列

有时也需要把进入队列中的元素分优先级(比如线程调度)，出队列时首先

选择优先级最高的元素出队列(优先级高先被服务VIP)，对于优先级相同的 元素则按照先进先出的原则出队列

即优先级队列的出队列操作不是直接将对头元素出队列，而是把队列中优

先级最高的元素出队列

顺序队列上的基本操作

//队列的定义#define MAX_SIZE 8typedef int DataType;typedef struct Queue{    DataType array[MAX_SIZE];    int _front;//队头指针    int _back;//队尾指针    int _count;}Queue;  //初始化队列void QueueInit(Queue* q){    assert(q);    q->_front = q->_back = 0;    q->_count = 0;}//数据进队列void QueuePush(Queue* q, DataType data){    assert(q);    if (q->_count >= MAX_SIZE)    {        printf("队列已满！无法进队！\n");        return;    }    q->array[q->_back++] = data;    if (q->_back == MAX_SIZE)        q->_back = 0;    q->_count++;}//数据出队列void QueuePop(Queue* q){    assert(q);    if (q->_count == 0)    {        printf("队列已空！无法出队！\n");        return;    }    ++(q->_front);    if (q->_front == MAX_SIZE)        q->_front = 0;    q->_count--;}//队列判空int QueueEmpty(Queue* q){    assert(q);    return q->_count == 0;}//求队列长度int QueueSize(Queue* q){    return q->_count;}DataType QueueFront(Queue* q){    return q->array[q->_front];} DataType QueueBack(Queue* q){    if (0!=q->_back)        return q->array[q->_back-1];    return q->array[MAX_SIZE - 1];}