数据结构——队列

目录

前言

一、队列基本概念

二、实现方式

1、顺序表实现

2、链表实现

三、对列基本操作

1、顺序表队列基本操作

2、链表队列基本操作

四、运用场景

完结

前言

队列（Queue）是一种先进先出（First In First Out：FIFO）的线性表。它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。队列的这种特性使得它非常适合用于那些需要按顺序处理元素的场景，如任务调度、缓冲区管理等。

由于队列也是一种特殊的线性表，所以它的实现方式也主要有两种：

1、用顺序表实现，顺序表内容可参考：数据结构——顺序表

2、用链表实现，单向链表内容可参考：数据结构——单向链表

一、队列基本概念

队列是一种特殊的线性表，它只允许在表的一端（队尾）进行插入操作，而在另一端（队头）进行删除操作。这种特性使得队列具有先进先出（First In First Out：FIFO）的特点，即最先进入队列的元素将最先被删除。

进如同排队等候一样，遵循先到先处理的原则，不能插队，也不能乱出队，只能从一端进入等候，从另一端出去处理。

队列的主要操作包括入队（在队尾插入一个元素）、出队（从队头删除一个元素）以及查看队头元素等。

队列的特点：
1、先进先出：元素按照它们被添加到队列中的顺序被移除。

2、有限性：在基于数组的实现中，队列的大小可能受到限制。在基于链表的实现中，队列的大小通常只受内存限制。

3、操作受限：只能在队列的一端添加元素（入队），在另一端移除元素（出队）。

二、实现方式

队列可以通过多种数据结构来实现，但最常见的是使用数组（顺序表）和链表。

1、顺序表实现

使用数组实现队列时，需要维护两个指针：一个指向队头（front），另一个指向队尾（rear）。当进行入队操作时，将新元素放在rear指针指向的位置，并将rear指针后移一位（注意处理数组越界问题，可能需要动态扩容）。出队操作时，返回front指针指向的元素，并将front指针后移一位。

typedef int datatype;
#define N 128typedef struct {datatype data[N];  //数组int front;         //队头指针int rear;          //队尾指针
//    int size;          //当前队列中的元素数量
}sequeue;
//创建队列（这里使用动态分配内存的方式进行创建），并初始化
sequeue * queue_create() 
{sequeue *sq;if ((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL) {printf("malloc failed\n");return NULL;}memset(sq->data, 0, sizeof(sq->data));sq->front = 0;sq->rear = 0;
//    sq->size = 0;return sq;
}

由于数组实现的队列，其大小固定，存在不易扩充、利用率低等弊端。如下，随着对尾指针和对头指针的向前移动，前面的内存就使用不到了（图中颜色标记处）。当然可以通过对数组进行整体移动等方法解决，但是但数据量大时，会耗费大量的时间，且比较麻烦。

因此，在实际运用当中，通常采用环形队列，即当队尾或者对头指针超出数组末尾时，在队列前面部分还有空间的情况下，将队尾或对头指针循环移到数组首部继续对队列操作，如此便可以是=实现循环利用的目的，如下：

具体操作实现见第三节内容。

2、链表实现

链表实现的队列则更加灵活，不需要担心空间限制和元素移动的问题。在链表中，每个节点都包含数据域和指向下一个节点的指针。入队操作就是创建一个新节点，将其数据域设置为新元素的值，并将其插入到队尾节点的后面，同时更新队尾指针。出队操作则是删除队头节点，并更新队头指针。

创建数据类型
typedef int datatype;
typedef struct node {datatype data;struct node *next;
}listnode , *linklist;typedef struct {linklist front;//对头节点指针linklist rear; //对尾节点指针
}linkqueue;//创建链表，并初始化
linkqueue * queue_create() 
{linkqueue *lq;//创建队列，其中包含对头节点指针和队尾节点指针if ((lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL) {printf("malloc linkqueue failed\n");return NULL;}//初始时，头尾节点指针都指向同一个链表节点，即为空队列lq->front = lq->rear = (linklist)malloc(sizeof(listnode));if (lq->front == NULL) {printf("malloc node failed\n");return NULL;}//赋初值，由于lq->front = lq->rear，所以对头队尾赋值一样lq->front->data = 0;lq->front->next = NULL;return lq;
}

由于链表的灵活性，所以不存在使用不到的空间，入队需要时就向堆内存空间申请，出队不需要时就释放该部分空间即可，只是数据量大时，就需要结合堆空间考虑了。

具体操作实现见第三节内容。

三、对列基本操作

入队（Enqueue）：在队列的尾部添加一个元素。注意队列已满的情况。

出队（Dequeue）：移除队列头部的元素，并返回该元素。注意队列为空的情况。

查看队首：返回队列头部的元素，但不从队列中移除它。注意队列为空的情况。

判断队列是否为空：检查队列是否为空。如果队列中没有元素，则返回true（1）；否则返回false（0）。

判断队列是否已满：检查队列是否已满。这通常对于固定大小的队列（如数组实现的队列）是重要的。如果队列已满，则返回true（1）；否则返回false（0）。注意，动态增长的队列（如链表实现的队列）通常不会达到“满”的状态，因此一般没有该操作。

获取队列的大小：返回队列中元素的数量。

1、顺序表队列基本操作

这里以常用的数组环形队列为例：其中取余N就是为了能够循环操作。由于是数组实现的队列，长度有限，所以需要判断队列是否已满，当对尾指针的位置加1等于对头指针时，则说明队列已满。而队列为空时，则是对头指针等于队尾指针。

//入队操作，需要传入队列指针和入队的数据
int enqueue(sequeue *sq, datatype data) 
{if (sq == NULL) {printf("sq is NULL\n");return -1;}//如果队尾指针加一等于对头指针则判定为满队if ((sq->rear + 1) % N == sq->front) {printf("sequeue is full\n");return -1;}//正常入队sq->data[sq->rear] = data;sq->rear = (sq->rear + 1) % N;return  0;
}
//出队操作，返回出队数据
datatype dequeue(sequeue *sq) 
{datatype ret;ret = sq->data[sq->front];sq->front = (sq->front + 1) % N;return ret;
}
//判断队列是否为空，1为空
int queue_empty(sequeue *sq) 
{if (sq == NULL) {printf("sq is NULL\n");return -1;}
//当队尾指针等于队尾指针时，认为队列为空return (sq->front == sq->rear ? 1 : 0);
}//判断队列是否为满队，1为满队
int queue_full(sequeue *sq) 
{if (sq == NULL){printf("sq is NULL\n");return -1;}if ((sq->rear + 1) % N == sq->front) return 1;else return 0;
}
//清空当前队列，即对头等于队尾等于零即可
int queue_clear(sequeue *sq) 
{if (sq == NULL) {printf("sq is NULL\n");return -1;}sq->front = sq->rear = 0;return 0;
}
//释放队列内存
sequeue * queue_free(sequeue *sq) 
{if (sq == NULL) {printf("sq is NULL\n");return NULL;}free(sq);sq = NULL;return NULL;
}

2、链表队列基本操作

链表队列操作则不需要判断队列是否已满，灵活处理。

//入队操作，需要传入队列指针和待入队数据
int enqueue(linkqueue *lq, datatype data) 
{linklist p;if (lq == NULL) {printf("lq is NULL\n");return -1;}//创建新节点，用于存放入队数据if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {printf("malloc node failed\n");return -1;}p->data = data;//放入数据p->next = NULL;//先将新节点放入链表的尾部lq->rear->next = p;//再把当前队列的队尾指针指向链表尾部的位置lq->rear = p;return 0;
}
//出对操作，删除当前队列的对头节点，
//并将队列的对头指针指向下一个节点，同时返回该节点的数据
datatype dequeue(linkqueue *lq) 
{linklist p;if (lq == NULL) {printf("lq is NULL\n");return -1;}//将当前队列的对头指针存在临时变量中p = lq->front;//然后将当前队列的对头指针指向下一个lq->front = p->next;//最后释放掉当前头节点的内存free(p);p = NULL;return (lq->front->data);
}
//判断队列是否为空，1为空
int queue_empty(linkqueue *lq) 
{if (lq == NULL) {printf("lq is NULL\n");return -1;}return (lq->front == lq->rear ? 1 : 0);//对头指针等于队尾指针时，为空队列
}
//清空队列，需要遍历释放链表的各个节点的内存
int queue_clear(linkqueue *lq) 
{linklist p;if (lq == NULL) {printf("lq is NULL\n");return -1;}//依次释放对头数据，直到对头指针等于队尾指针时停下//其实就是遍历出队，将队列中所有的数据都出队完就可以了while (lq->front->next) {p = lq->front;lq->front = p->next;//printf("clear free:%d\n", p->data);free(p);p = NULL;}return 0;
}
//释放队列内存，遍历释放所有节点内存
linkqueue * queue_free(linkqueue *lq) 
{linklist p;if (lq == NULL) {printf("lq is NULL\n");return NULL;}//比清空队列多了一步，将对头队尾相等时的节点也释放了while (lq->front) {p = lq->front;lq->front = p->next;//printf("free:%d\n", p->data);free(p);}free(lq);lq = NULL;return NULL;
}