数据结构之顺序队列(C实现)

一、队列是什么

队列是一种可以实现“先进先出”的存储结构。

队列通常可以分为两种类型：

一、顺序队列，采用顺序存储，当长度确定时使用。顺序队列又有两种情况：

　　①使用数组存储队列的称为静态顺序队列。

　　②使用动态分配的指针的称为动态顺序队列。

二、链式队列，采用链式存储，长度不确定时使用（由链表实现）。

由于链式队列跟链表差不多，所以在这里只针对循环(环形)队列来说明并实践。
循环队列的两个参数：
　　①front,front指向队列的第一个元素。(front==head)
　　②rear,rear指向队列的最后一个有效元素的下一元素。(rear==tail)

队列的两个基本操作：出队和入队。

二、队列的结构

下面是一个循环队列（基于数组实现）的结构图：

三、队列的操作

入队（尾部入队）
　　①将值存入rear所代表的位置。
　　②rear = (rear+1)%数组的长度。
出队（头部出队）
　　front = (front+1)%数组的长度。
队列是否为空
　　front和rear的值相等，则该队列就一定为空。
队列是否已满

在循环队列中,“队满”和“队空”的条件有可能是相同的，都是front ==rear，这种情况下，无法区别是“队满”还是“队空”。

针对这个问题，有3种可能的处理方法：【这里采用了第3种处理方法】

（1）另设一个标志以区别是“队满”还是“队空”。（即入队/出队前检查是否“队满”/“队空”）

（2）设一个计数器，此时甚至还可以省去一个指针。

（3）少用一个元素空间，即约定队头指针在队尾指针的下一位置时就作为“队满”的标志，即“队满”条件为：(pQueue->rear+1)%MAX_SIZE == pQueue->front。

四、队列的一些问题以及解决办法

从上图可以看出，随着入队、出队的进行，会使整个队列整体向后移动，就会出现上图中的现象：队尾指针已经移到了最后，即队尾出现溢出，无法再进行入队操作，然而实际上，此时队列中还有空闲空间，这种现象称为“假溢出”。

解决“假溢出”的三种办法：

方法一：每次删除队头元素后，把整个队列向前移动一个位置，这样可保证队头元素在存储空间的最前面。但每次删除元素时，都要把表中所有元素向前移动，效率太低。
方法二：当队尾指针出现溢出时，判断队头指针位置，如果前部有空闲空间，则把当前队列整体前移到最前方。这种方法移动元素的次数大为减少。
方法三：将队列看成头尾相接的循环结构，当队尾指针到队尾后，再从队头开始向后指，这样就不需要移动队列元素了，显然，第三种方法最经济、应用最多，这种顺序队列被称为“循环队列”或“环形队列”。

采用了这种头尾相接的循环队列后，入队的队尾指针加1操作及出队的队头指针加1操作必须做相应的修改，以确保下标范围为0~Max_Size-1。对指针进行取模运算，就能使指针到达最大下标位置后回到0，符合“循环”队列的特点。

因此入队时队尾指针加1操作改为： pQueue->tail = (pQueue->tail+1) % MAX_SIZE;

入队时队尾指针加1操作改为： pQueue->head = (pQueue->head+1) % MAX_SIZE;

五、动态顺序队列的实现

基于数组的动态顺序循环队列的具体实现：

5.1 MyQueue.h

#ifndef MYQUEUEC_H

#define MYQUEUEC_H

#include <stdio.h>

#include <malloc.h>

/* 队列: 只允许在表的一端(队尾rear)进行插入操作，而在另一端(队头front)进行删除操作的线性表

 * 插入操作简称为入队  删除操作简称为出队   队列具有先进先出的特点

 */

/*=====队列的入队、出队示意图========

 *

 *  出队 ----------------- 入队

 *   <--- a1,a2,a3,...,an <---

 *      -----------------

 *

 *================================*/

typedef enum

{

    OK=, //正确

    ERROR=,   //出错

    TRUE=,  //为真

    FALSE=   //为假

}status;

typedef int ElemType;   //宏定义队列的数据类型

#define MAX_SIZE 20

/*一、使用数组存储队列的称为静态顺序队列

 *二、使用动态分配的指针的称为动态顺序队列*/

// 【这里的是动态顺序队列】

typedef struct

{

    ElemType *pBase;    //数组指针

    ElemType front;      //队头索引

    ElemType rear;       //队尾索引

    int maxSize;    //当前分配的最大容量

}queue;

//创建空队列 queueCapacity-队列容量

status initQueue(queue *PQueue,int queueCapacity);

//销毁队列

void destroyQueue(queue *PQueue);

//清空队列

void clearQueue(queue *PQueue);

//判断队列是否为空

status isEmpityQueue(queue *PQueue);

//判断队列是否为满

status isFullQueue(queue *PQueue);

//获得队列长度

int getQueueLen(queue *PQueue);

//新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素

status enQueue(queue *PQueue,ElemType element);

//新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除]

status deQueue(queue *PQueue,ElemType *pElement);

//遍历队列

void queueTraverse(queue *PQueue);

#endif // MYQUEUEC_H

5.2 MyQueue.c

#include "myqueuec.h"

/* 队列: 只允许在表的一端(队尾rear)进行插入操作，而在另一端(队头front)进行删除操作的线性表

 * 插入操作简称为入队  删除操作简称为出队   队列具有先进先出的特点

 */

/*=====队列的入队、出队示意图========

 *

 *  出队 ----------------- 入队

 *   <--- a1,a2,a3,...,an <---

 *      -----------------

 *

 *================================*/

//创建队列 queueCapacity-队列容量

status initQueue(queue *PQueue,int queueCapacity)

{

    //给数组指针分配内存

    PQueue->pBase = (ElemType *)malloc(sizeof(ElemType)*queueCapacity);

    if(!PQueue->pBase)

    {

        printf("给数组指针分配内存失败\n");

        return ERROR;

    }

    PQueue->front = ; //最开始创建时，队头索引为0

    PQueue->rear = ; //最开始创建时，队尾索引为0

    PQueue->maxSize = queueCapacity;

    return OK;

}

//销毁队列

void destroyQueue(queue *PQueue)

{

    free(PQueue);  //释放队列数组指针指向的内存

    PQueue = NULL;    //队列数组指针重新指向NULL,避免成为野指针

}

//清空队列

void clearQueue(queue *PQueue)

{

    PQueue->front = ; //队头索引清0

    PQueue->rear = ; //队尾索引清0

}

//判断队列是否为空

status isEmpityQueue(queue *PQueue)

{

    if( PQueue->front == PQueue->rear )  //队头==队尾，说明为空

        return TRUE;

    return FALSE;

}

/*

 *在循环队列中,“队满”和“队空”的条件有可能是相同的，都是front==rear，

 *这种情况下，无法区别是“队满”还是“队空”。

 *针对这个问题，有3种可能的处理方法：

 *（1）另设一个标志以区别是“队满”还是“队空”。（即入队/出队前检查是否“队满”/“队空”）

 *（2）设一个计数器，此时甚至还可以省去一个指针。

 *（3）少用一个元素空间，即约定队头指针在队尾指针的下一位置时就作为“队满”的标志，

 *即“队满”条件为：(PQueue->rear+1)%MAX_SIZE == PQueue->front。

 *  【这里采用了第3种处理方法】

 */

//判断队列是否为满

status isFullQueue(queue *PQueue)

{

    if( (PQueue->rear+)%PQueue->maxSize == PQueue->front )  //队列满

        return TRUE;

    return FALSE;

}

//获得队列长度

int getQueueLen(queue *PQueue)

{

    //正常情况下，队列长度为队尾队头指针之差，但如果首尾指针跨容量最大值时，要%

    return (PQueue->rear - PQueue->front + PQueue->maxSize)%PQueue->maxSize;

}

//新元素入队 [先进先出原则：在队尾的位置插入] element-要插入元素

status enQueue(queue *PQueue,ElemType element)

{

    if(isFullQueue(PQueue)==TRUE)

    {

        printf("队列已满,不能再插入元素了!\n");

        return FALSE;

    }

    //向队列中添加新元素

    PQueue->pBase[PQueue->rear] = element;

    PQueue->rear = (PQueue->rear+) % PQueue->maxSize; //将rear赋予新的合适的值

    return TRUE;

}

//新元素出队,同时保存出队的元素 [先进先出原则：在队头的位置删除]

status deQueue(queue *PQueue,ElemType *pElement)

{

    //如果队列为空,则返回false

    if(isEmpityQueue(PQueue)==TRUE)

    {

        printf("队列为空，出队失败!\n");

        return FALSE;

    }

    *pElement = PQueue->pBase[PQueue->front];       //先进先出

    PQueue->front = (PQueue->front+) % PQueue->maxSize; //移到下一位置

    return TRUE;

}

//遍历队列

void queueTraverse(queue *PQueue)

{

    int i = PQueue->front;           //从头开始遍历

    printf("遍历队列：\n");

    while(i != PQueue->rear)     //如果没有到达rear位置，就循环

    {

        printf("%d  ", PQueue->pBase[i]);

        i = (i+) % PQueue->maxSize;              //移到下一位置

    }

    printf("\n");

}

5.3 main.c

#include <stdio.h>

#include "myqueuec.h"

int main(void)

{

    int value;          //用于保存出队的元素

    //创建队列对象

    queue *PQueue = (queue *)malloc(sizeof(queue));

    if(!PQueue->pBase)

    {

        printf("给队列对象分配内存失败\n");

        return -;

    }

    //调用初始化队列的函数

    initQueue(PQueue,MAX_SIZE);

    //调用出队函数

    enQueue(PQueue, );

    enQueue(PQueue, );

    enQueue(PQueue, );

    enQueue(PQueue, );

    enQueue(PQueue, );

    enQueue(PQueue, );

    enQueue(PQueue, );

    enQueue(PQueue, );

    //调用遍历队列的函数

    queueTraverse(PQueue);

    //调用出队函数

    if(deQueue(PQueue, &value))

    {

        printf("出队一次，元素为：%d\n", value);

    }

    queueTraverse(PQueue);

    if(deQueue(PQueue, &value))

    {

        printf("出队一次，元素为：%d\n", value);

    }

    queueTraverse(PQueue);

    free(PQueue);

    PQueue = NULL;

    getchar();

    return ;

}

巴特西