顺序队列常规操作

/********************* 顺序队列的常规操作 *************************/

Queue    InitSeQueue();             // 初始化顺序队列
int      QueueFull();               // 判断顺序队列满
int      QueueEmpty();              // 判断顺序队列空
int      QueueLength();             // 求顺序队列长度(元素个数)
int      EnQueue();                 // 入队
int      DeQueue();                 // 出队

/****************************************************************/

定义顺序队列结构体

#include "stdio.h"
#include "malloc.h"

#define TRUE  1
#define FALSE 0
#define MAXSIZE 10      // 队列最大的存储量

typedef int ElemType;


// 定义顺序队列结构体
typedef struct SeQueue{
    ElemType *base; // 队列首地址
    int front;      // 队列头下标
    int rear;       // 队列尾下标
}*Queue;

顺序队列和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个 “指针” front 和 rear 分别指示队列头元素及队列尾元素的位置。

为了在C语言中描述方便起见，初始化建空队列时，令 front = rear = 0;

每当插入新的队尾元素时 “尾指针增1”；每当删除队头元素时 “头指针增1”。

因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

初始化顺序队列

/*
 *  初始化顺序队列
*/
Queue InitSeQueue(){
    Queue q;
    // 分配队列空间
    q -> base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    q -> front = q -> rear = 0; // 开始队列的头尾下标相等
    return q;
}

顺序队列判满

/*  
 *  顺序队列判满
 *  q 顺序队列
*/
int QueueFull(Queue q){
    if(q == NULL){
        return FALSE;
    }
    // 判断队列尾下标是否超过最大容量
    if(q -> rear >= MAXSIZE){
        return TRUE;
    }
    return FALSE;
}

顺序队列判空

/*
 *  顺序队列判空
 *  q 顺序队列
*/
int QueueEmpty(Queue q){
    if(q == NULL){
        return FALSE;
    }
    return q -> front == q -> rear;
}

计算顺序队列的长度

/*
 *  求顺序队列的长度(元素个数)
 *  q 顺序队列
*/
int QueueLength(Queue q){
    if(q == NULL){
        return FALSE;
    }
    return q -> rear - q -> front;
}

顺序队列入队（EnQueue）

/*
 *  入队
 *  q 顺序队列
 *  data 入队元素
*/
int EnQueue(Queue q, ElemType data){
    // 队列判满
    if(QueueFull(q)){
        return FALSE;
    }
    // 把元素插入队尾
    q -> base[q -> rear] = data;    
    q -> rear++;
    return TRUE;
}

顺序队列出队（DeQueue）

/*
 *  出队  
 *  q 顺序队列
 *  *val 用来存出队元素的数据 
*/
int DeQueue(Queue q, ElemType *val){
    // 队列判空
    if(QueueEmpty(q)){
        return FALSE;
    }
    // 把队头元素取出来并利用指针返回去
    *val = q -> base[q -> front];
    q -> front ++;
    return TRUE;
}

顺序队列各操作测试

/*
 * 打印队满、队空、队长状态
 * q 顺序队列
*/
void QueueStatus(Queue q){
    printf("QueueFull():%d\n", QueueFull(q));
    printf("QueueEmpty():%d\n", QueueEmpty(q));
    printf("QueueLength():%d\n\n", QueueLength(q));
}

// 程序主入口
int main(int argc, char const *argv[])
{   
    Queue q = InitSeQueue();
    printf("QueueMaxSize: %d\n\n", MAXSIZE);
    QueueStatus(q); // 打印队满、队空、队长状态

    // 入队
    printf("EnQueue():");
    for(int i = 1; i < MAXSIZE * 2; i+=2){
        printf("%d\t", i);
        EnQueue(q, i);
    }

    printf("\n");
    QueueStatus(q);

    // 出队
    int val;
    printf("DeQueue():");
    while(!QueueEmpty(q)){
        DeQueue(q, &val);
        printf("%d\t", val);
    }
    printf("\n");
    QueueStatus(q);
    
   // 此时队列元素全出队了，测试假溢出
    int num = 20;
    printf("EnQueue(%d): %d\t(0 Failed, 1 Success)\n", num, EnQueue(q, num));

    return 0;
}

结果如下：

QueueMaxSize: 10

QueueFull():0
QueueEmpty():1
QueueLength():0

EnQueue():1     3       5       7       9       11      13      15      17      19
QueueFull():1
QueueEmpty():0
QueueLength():10

DeQueue():1     3       5       7       9       11      13      15      17      19
QueueFull():1
QueueEmpty():1
QueueLength():0

EnQueue(20): 0  (0 Failed, 1 Success)

QueueFull():1 、EnQueue(20): 0 可以看出顺序队列存在假溢出（实际可用空间并未占满，却不能进行入队操作）

例如：

1️⃣：初始化空队列，q -> front = q -> rear = 0

2️⃣：入队a1、a2、a3，q -> front = 0, q -> rear = 3

3️⃣：出队a1、a2，q -> front = 2, q -> rear = 3

4️⃣：入队a4、a5、a6，q -> front = 2, q -> rear = 6

执行 4️⃣ 操作后队列的"尾指针"已经超出对队列的最大范围了，之后无法再进行入队操作，而队列实际空间并未占满，就造成了假溢出。

用 循环队列 就可以解决假溢出情况。

源代码

源代码已上传到 GitHub Data-Structure-of-C，欢迎大家下载 C语言实现数据结构

✍ 码字不易，记得点赞 👍 收藏 ⭐️

前言

        大家好，越努力，越幸运。本篇文章小猿将跟您分享数据结构队列中的顺序队列，希望对您有所帮助。

一、顺序队列的定义

       首先我们来看看什么是队列？队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。队列的结构图如下所示：

       明白了队列之后，顺序队列就非常简单了，用顺序存储结构表示的队列就简称为顺序队列。和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。为了在C语言中描述方便起见，在此我们约定：初始化建空队列时，令front=rear=0，每当插人新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。了解了顺序队列之后，我们可以发现顺序队列有一个很大的缺点，它会出现虚假的满状态，为了解决这个问题我们可以将其改造成循环队列（循环队列将在下次进行介绍）。

二、顺序队列的结构

结构图

代码描述

//数据类型
#define ElemType int
//队列可容纳的最多元素个数
#define MAXSIZE 8
//队列的管理结构
typedef struct Queue
{
	ElemType *base; //指向队列的存储空间
	int       front; //指向队头
	int       rear;  //指向队尾
}Queue;

三、顺序队列的常用操作

初始化

//初始化顺序队列
void InitQueue(Queue *Q)
{
	//为顺序队列开辟存储空间
	Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	assert(Q->base != NULL);
	//初始化时，队头和队尾都在0位置
	Q->front = Q->rear = 0;
}

入队

//入队操作
void EnQueue(Queue *Q, ElemType x)
{
	//判断队列是否还有存储空间
	if(Q->rear >= MAXSIZE)
		return;
	//如果还有存储空间，将数据入队
	Q->base[Q->rear++] = x;
}

出队

//出队
void DeQueue(Queue *Q)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，进行出队操作
	Q->front++;
}

打印队列数据

//打印顺序队列中的元素
void ShowQueue(Queue *Q)
{
	//遍历队头到队尾中的每个元素，并将其打印输出
	for(int i=Q->front; i<Q->rear; ++i)
	{
		printf("%d ",Q->base[i]);
	}
	printf("\n");
}

获取队头元素

//获取队头元素
void GetHdad(Queue *Q, ElemType *v)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，取出队头元素
	*v = Q->base[Q->front];
}

求队列长度

//获取队列元素个数
int Length(Queue *Q)
{
	//将尾指针位置减去头指针的位置就是队列中元素的个数
	return (Q->rear - Q->front);
}

清空队列

//清空队列
void ClearQueue(Queue *Q)
{
	//将队头指针和队尾指针都重置为0
	Q->front = Q->rear = 0;
}

销毁队列

//销毁队列
void DestroyQueue(Queue *Q)
{
	//释放队列的存储空间
	free(Q->base);
	//将队列空间的位置指针置空
	Q->base = NULL;
}

结语

        对顺序队列的介绍就到这里啦，希望这篇文章能给予你一些帮助，感谢各位人才的：点赞、收藏和评论，我们下次见。

附录

以下提供顺序队列的测试代码

SeqQueue.h

#ifndef __SEQQUEUE_H__
#define __SEQQUEUE_H__

#include<stdio.h>
#include<malloc.h>
#include<assert.h>

//数据类型
#define ElemType int
//队列可容纳的最多元素个数
#define MAXSIZE 8
//队列的管理结构
typedef struct Queue
{
	ElemType *base; //指向队列的存储空间
	int       front; //指向队头
	int       rear;  //指向队尾
}Queue;

void InitQueue(Queue *Q);
void EnQueue(Queue *Q, ElemType x);
void ShowQueue(Queue *Q);
void DeQueue(Queue *Q);

void GetHdad(Queue *Q, ElemType *v);
int Length(Queue *Q);
void ClearQueue(Queue *Q);
void DestroyQueue(Queue *Q);


#endif //__SEQQUEUE_H__

SeqQueue.cpp

#include"SeqQueue.h"

//初始化顺序队列
void InitQueue(Queue *Q)
{
	//为顺序队列开辟存储空间
	Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	assert(Q->base != NULL);
	//初始化时，队头和队尾都在0位置
	Q->front = Q->rear = 0;
}

//入队操作
void EnQueue(Queue *Q, ElemType x)
{
	//判断队列是否还有存储空间
	if(Q->rear >= MAXSIZE)
		return;
	//如果还有存储空间，将数据入队
	Q->base[Q->rear++] = x;
}

//打印顺序队列中的元素
void ShowQueue(Queue *Q)
{
	//遍历队头到队尾中的每个元素，并将其打印输出
	for(int i=Q->front; i<Q->rear; ++i)
	{
		printf("%d ",Q->base[i]);
	}
	printf("\n");
}

//出队
void DeQueue(Queue *Q)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，进行出队操作
	Q->front++;
}

//获取队头元素
void GetHdad(Queue *Q, ElemType *v)
{
	//判断队列中的元素是否为空
	if(Q->front == Q->rear)
		return;
	//如果队列中的元素不为空，取出队头元素
	*v = Q->base[Q->front];
}

//获取队列元素个数
int Length(Queue *Q)
{
	//将尾指针位置减去头指针的位置就是队列中元素的个数
	return (Q->rear - Q->front);
}

//清空队列
void ClearQueue(Queue *Q)
{
	//将队头指针和队尾指针都重置为0
	Q->front = Q->rear = 0;
}

//销毁队列
void DestroyQueue(Queue *Q)
{
	//释放队列的存储空间
	free(Q->base);
	//将队列空间的位置指针置空
	Q->base = NULL;
}

Main.cpp

#include"SeqQueue.h"

void main()
{
	Queue Q;
	InitQueue(&Q);

	for(int i=1; i<=8; ++i)
	{
		EnQueue(&Q, i);
	}
	ShowQueue(&Q);
	DeQueue(&Q);
	EnQueue(&Q,10);
	ShowQueue(&Q);
}

        队列是另一种限定性的线性表，他只允许在表的一端插入元素，而在表的另一端删除元素，具有“先进先出”的特点。在队列中，允许插入的一端称为队尾，允许删除的一端称为队首。

        与线性表相似，队列也有两种存储结构：顺序队列和链式队列。

一，顺序队列

        顺序队列使用顺序表来实现的，即队列中的元素均存放在一片连续的内存空间中。通过该片内存的地址对队列中元素进行访问。之前是用数组来实现顺序表的。通过数组名访问数组元素。数组的长度必须提前设定，一旦超过设定的大小，则无法再向其中添加元素。

        这里采用与顺序栈类似的方法，通过设定初始值来动态申请内存，当内存不够用时，修改初始值来再次申请更大的内存达到扩容的目的。所以可以通过动态申请的内存地址来访问队列中的元素。

        因此，以下实现的是可以扩容的顺序队列。

1. 顺序队列的结构

        要实现扩容的顺序队列，

（1）首先要动态申请一片连续的内存。该内存需要一个指针data指向，通过该指针来访问该内存。

（2）而该内存的大小需提前设定，用capacity进行表示

（3）另外，还需要知道队列中实际元素的个数size

        因为队列具有“先进先出”的特点，只能在一端（队尾）进，另一端（队头）出。所以可能造成下面的情况：

        此时，需要时刻知道队列两端所在的位置，但又不能像顺序栈一样用size来表示队尾结点所在位置。所以还需要两个变量：（4）head表示队首结点所在的下标

（5）tail表示队尾结点的下个位置所在的下标（这样入队时直接在tail处设置元素即可）。

        所以，队列中所有元素的下标所在范围为：[head,tail)，如下图：

代码如下：

typedef char SeqQueueType;
                                                                                                                                                      
//顺序队列的结构
typedef struct SeqQueue
{
    SeqQueueType* data;//指向顺序队列的指针
    int size;//顺序队列的实际长度
    int capacity;//顺序队列的有效长度
    int head;//顺序队列的头节点所在的下标
    int tail;//顺序队列尾节点下个元素所在的下标,即[head,tail)
}SeqQueue;

2. 顺序队列的初始化

        在对队列初始化时，首先要设定队列有效长度的初始值，再根据该初始值来动态申请内存，并由data指向。因为此时队列中并没有元素，所以，实际长度size，head和tail均置为0即可。

代码如下：

//初始化顺序队列
void SeqQueueInit(SeqQueue* queue)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }

    queue->size = 0;//初始时队列为空
    queue->capacity =1000;//设置有效长度为1000
    queue->data = (SeqQueueType*)malloc(queue->capacity*sizeof(SeqQueueType));//动态申请内存,由data指向
    queue->head = 0;//初始时，队列为空                                                                                                                
    queue->tail = 0; 
}   

3. 顺序队列入队操作

        因为是从队尾进行入队的，所以只需将下标tail处的值设置为指定值，然后tail加1，size加1即可。但是在入队之前要考虑以下几点：

（1）如果队列中的元素个数已经到达动态申请内存的上限值，此时就需要扩容来申请更大的内存。在扩容时：

        1）首先要重新设定更大的有效长度，根据新设置的有效长度来动态申请更大的内存空间

        2）其次，要将原内存中的数据拷贝到新申请的内存中。在拷贝时，要考虑以下几点：

                i）如果head小于tail的值，则从下标为head开始到下标为tail结束，依次将各节点的信息拷贝到新内存中，如图：

                ii）如果head大于等于tail的值，则需要先从head开始到原capacity将各节点拷贝到新内存对应的下标处，再将从下标为0开始到tail的各节点拷贝到新内存已有结点之后。拷贝结束后需要修改新内存中的tail值。如下图：

        3）拷贝完之后，要释放原来的内存，以免造成内存泄漏。并使队列中的指针data指向新申请的内存

（2）如果原队列中的元素为以下情况：

        此时，已经无法从队尾入队，但是队列并没有满。所以需要将tail的值改为0。这样便可以继续入队。

（3）在进行（1）（2）之后或者没有出现（1）（2）的情况，就可以使新元素直接直接放置在下标为tail处，然后tail加1，size加1即可。

        根据上述分析，编写代码如下：

//入队,queue为顺序队列的指针
void SeqQueuePush(SeqQueue* queue,SeqQueueType value)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }

    //原内存已满，需要扩容
    if(queue->size >= queue->capacity)
    {
        //扩容函数
        Expanding(queue);
    }
    //如果尾节点为数组最后一个元素，但是数组前面还有空余的地方
    if(queue->tail == queue->capacity)
    {
        queue->tail = 0;
        queue->data[queue->tail++] = value;
        queue->size++;
        return;
    }
    //尾节点不为数组最后一个节点且数组还有空余的地方
    queue->data[queue->tail++] = value;
    queue->size++;
    return;                                                                                                                           
}

//扩容函数
void Expanding(SeqQueue* queue)
{
    if(queue == NULL)
    {                                                                                                                                 
        //非法输入
        return;
    }
    //重新设置新内存的有效长度
    queue->capacity = 2*(queue->capacity) + 1;
    //重新申请新的内存
    SeqQueueType* new_data = (SeqQueueType*)malloc(queue->capacity*sizeof(SeqQueueType));
    
    //将原内存中的数据复制到新内存中
    
    //如果尾节点在头节点之后
    int i;
    if(queue->head < queue->tail) //注意没有"="
    {
        i = queue->head;
        for(;i < queue->tail;++i)//按对应下标复制即可
        {
            new_data[i] = queue->data[i];
        }
    }
    else//如果尾节点在头节点之前
    {
        i = queue->head;
        //先拷贝队首到原capacity的数据
        for(;i < queue->size;++i)//此时size等于原capacity
        {
            new_data[i] = queue->data[i];
   }

        //在拷贝0到队尾的数据
        i = 0;
        for(;i < queue->tail;++i)
        {
            new_data[queue->size + i] = queue->data[i];
        }

        queue->tail = queue->head + queue->size;//修改扩容后的tail值
    }
    //释放原内存
    free(queue->data);
    //将队列结构中的data指针指向新内存
    queue->data = new_data;
    return;
}

4. 顺序队列的出队操作

        顺序队列是从队头出队的：

（1）首先考虑队列是否为空，为空则出队失败。（为空的条件是队列长度为0）

（2）然后需要考虑以下情形：

         此时，出队的元素为capacity-1处的元素，而出队后需要将head设置为0，同时是使size减1。

（3）如果不满足（1）（2）只需将head加1，size减1即可（此时原head处的值为无效元素）。

代码如下：

//出队
void SeqQueuePop(SeqQueue* queue)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }
    if(queue->size == 0)
    {
        //空队列
        return;
    }

    //如果出队元素为最大数组下标处的元素
    if(queue->head == queue->capacity - 1)
    {
        queue->head = 0;
        queue->size--;
    }
    else//如果不是最大数组下标处的元素
    {
        queue->head++;
        queue->size--;
    }                                                                                                                                 
    return;
}

5. 取队首元素

（1）如果队列为空，则操作失败

（2）不为空，只需将队首下标head处的数据保存下来即可

代码如下：

//取队首元素:-1出错返回，0成功返回
int SeqQueueTop(SeqQueue* queue,SeqQueueType* value)
{
    if(queue == NULL || value == NULL)
    {
        //非法输入
        return -1;
    }

    if(queue->size == 0)
    {
        //空队列
        return -1;
    }
    //取队首元素                                                                                                                      
    *value = queue->data[queue->head];
    return 0;
}

6. 销毁队列

        队列初始化前只有一个队列结构体，而没有动态申请的内存和其中的元素。所以只需释放动态申请的内存，将队列长度置为0即可恢复到初始化前的状态。

//销毁队列
void SeqQueueDestory(SeqQueue* queue)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }
    free(queue->data);
    queue->size = 0;
    queue->capacity = 0;
    queue->head = 0;
    queue->tail = 0;
    return;
}

二，链式队列

        链式队列采用单链表来实现的。通过在链表的一端（队尾）添加结点来实现入队，在链表的另一端（队头）释放节点来实现出队。

1. 链式队列的结构

        链表是由一个个的结点组成，所以链式队列的结点结构与单链表的结点结构相同。包含一个数据域data和指针域next。

typedef char LinkQueueType;

//定义链式队列的节点结构
typedef struct LinkQueueNode
{
    LinkQueueType data;//节点的数据域
    struct LinkQueueNode* next;//指向下一个节点的指针
}LinkQueueNode;

        因为出，入队列需要从两端进行操作，所以在对该链式队列设置两个指针变量，head指向队列的队头结点，tail指向队列的队尾结点，将这两个指针封装在结构体中作为链式队列结构的成员。

//定义链式队列
typedef struct LinkQueue
{
    LinkQueueNode* head;//指向链式队列的头节点
    LinkQueueNode* tail;//指向链式队列的尾指针
}LinkQueue;

        这里的两个指针其实和单链表中的head指针作用类似，单链表只从一端开始进行操作，所以只需维护一个头指针来表示单链表。而队列出队，入队要从两端操作，所以为方便起见，需维护两个指针来共同表示链式队列。

2. 链式队列的初始化

        初始时队列中并没有结点，所以将队首指针和队尾指针均置空即可。

//初始化链式队列
void LinkQueueInit(LinkQueue* queue)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }
    queue->head = NULL;
    queue->tail = NULL;
}

3. 链式队列入队操作

        队列是从队尾进行入队，所以

（1）首先要创建一个新节点

（2）如果原队列为空，则使队头指针和队尾指针均指向新结点即可

（3）如果原队列不为空，则使队尾指针的next域指向新节点，然后队尾指针后移即可。

代码如下：

//尾插入队列
void LinkQueuePush(LinkQueue* queue,LinkQueueType value)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }
    //创建一个新节点
    LinkQueueNode* new_node = CreateNode(value);
    //对新节点进行尾插
    if(queue->head == NULL)//如果原队列为空
    {
        queue->head = queue->tail = new_node;
    }
    else//如果原队列不为空                                                                                                            
    {
        queue->tail->next = new_node;
        queue->tail = queue->tail->next;
    }
    return;

}

4. 链式队列的出队操作

        队列是从队头进行出队的，所以

（1）首先要考虑队列是否为空，为空则出队失败

（2）不为空，先使队头指针指向队头结点的下一个节点作为新的队首结点，然后释放原队首节点即可。

代码如下：

//头删出队列
void LinkQueuePop(LinkQueue* queue)
{
    if(queue == NULL)
    {
        //非法输入
        return;
    }
    if(queue->head == NULL)
    {
        //空队列
        return;
    }
    //头删
    LinkQueueNode* to_delete = queue->head;//保存要销毁的队首节点
    queue->head = to_delete->next;//使队头指针指向要销毁节点的下一个节点
    DestoryNode(to_delete);//销毁原队首节点                                                                                           
    return;
}

5. 取队首元素

（1）如果队列为空，则操作失败

（2）如果不为空，只需将队头指针所指向的结点数据域保存下来即可。

代码如下：

//取队首元素:出错返回-1，成功返回0
int LinkQueueTop(LinkQueue queue,LinkQueueType* value)
{
    if(value == NULL)
    {
        //非法输入
        return -1;
    }
    if(queue.head == NULL)
    {
        //空队列
        return -1;
    }

    *value = queue.head->data;//保存队首元素                                                                                                        
    return 0;
}

6. 销毁链式队列

        队列在初始化前只有两个指针，所以销毁后也要恢复到初始化前的状态。

（1）遍历链表将各节点依次销毁

（2）使队首，队尾指针置空，以防变为野指针

代码如下：

//销毁队列                                                                                                                            
void LinkQueueDestory(LinkQueue* queue)
{
    if(queue == NULL)
    {   
        //非法输入
        return;
    }   

    //从队头开始遍历队列
    LinkQueueNode* to_delete = queue->head;
    while(to_delete != NULL)
    {   
        LinkQueueNode* next_node = to_delete->next;//保存要销毁节点的下一个节点
        free(to_delete);//销毁节点
        to_delete = next_node;
    }   
    //使队首指针，队尾指针置空
    queue->head = NULL;
    queue->tail = NULL;
    return;
}