数据结构——队列

一、队列概念

队列时一种特殊的线性表，只允许在表的前端进行删除操作，而在表的后端进行插入操作，队列具有先进先出的特点。

队列的操作很简单，主要有以下几种常见的操作：

1. 初始化队列：创建一个队列

2. 进队列：将一个元素添加到队尾

3. 出队列：将队头元素取出，同时删除该元素，使下一个元素成为对头

4. 获取队列第一元素：将队头元素取出，不删除该元素

5. 获取队列长度：根据队头和队尾计算出队列中元素的数量

二、顺序队列实现

将队列用顺序存储方式保存时，在内存中申请一片区域用来保存元素，当第一个元素A进入队列时，因是空列队，因此元素A将排在队头，接着B、C、D顺次进入队列，就得到如图所示的队列。其中head指向队头，以指示队头元素出队操作，tail指向队尾，以指示新增元素进入队列。

如下图所示：

执行一次出队操作，元素A将出队，这时第2个元素B将成为队头，head指针将指向该元素如果要将元素E入队，则是将其放入tail指针指向元素的后一个位置（如下图为5的单元），并使tail指针指向序号为5的单元。

（1）定义顺序队列的结构

#define QUEUEMAX 15

typedef struct{
    DATA data[QUEUEMAX];
    int head;
    int tail;
} SeqQueue;

（2）初始化队列

SeqQueue *SeqQueueInit()
{
    SeqQueue *q;
    if (q=(SeqQueue *)malloc(sizeof(SeqQueue))) {
        q->head = 0;
        q->tail = 0;
        return q;
    }

    return NULL;
}

（3）释放队列

void SeqQueueFree(SeqQueue *q)
{
    if (q)
        free(q);
}

（4）获取队列状态

/*
*判断队列是否为空
*/

int SeqQueueIsEmpty(SeqQueue *q)
{
    return (q->head == q->tail);
}

/*
*判断队列是否已满
*/
int SeqQueueIsFull(SeqQueue *q)
{
    return (q->tail == QUEUEMAX);
}

/*
*获取队列的长度
*/
int SeqQueueLen(SeqQueue *q)
{
    return (q->tail - q->head);
}

（5）入队操作

int SeqQueueIn(SeqQueue *q, DATA data)
{
    if (SeqQueueIsFull(q)) {
        printf("队列已满!\n");
        return 0;
    }

    q->data[q->tail++] = data;
    return 1;
}

（6）出队操作

DATA *SeqQueueOut(SeqQueue *q)
{
    if (SeqQueueIsEmpty(q)) {
        printf("队列已空!\n");
        return NULL;
    }

    return &(q->data[q->head++]);
}

（7）获取队头元素

DATA *SeqQueuePeek(SeqQueue *q)
{
    if (SeqQueueIsEmpty(q)) {
        printf("队列已空!\n");
        return NULL;
    }

    return &(q->data[q->head]);
}

三、循环队列

由于每次出队后，队头的指针都向后移动，这时候就会出现一个问题，就是假溢出。如下图所示：

tail已指向队尾，这时进行入队操作时，虽然前面还有空位置，但仍然显示队列已满。为了解决这个问题，就提出了循环队列。

循环队列就是将队列的首尾相连构成一个环形区域，当在第n个位置进行元素的入队操作后，下一个地址就翻转为1

循环队列结构图：

在循环队列中，主要需要计算队尾tail和队头head的序号

以入队操作为例：

1. 将队尾序号加1,即tail=tail+1

2. 若tail=n+1，则tail=1, 其实前2步，可以使用表达式tail=（tail+1）%n

3. 若head=tail，即队尾和队头重合了，表示队列已满提示队列溢出

4. 若未溢出，将元素入队即可

（1）定义循环队列的结构

#define QUEUEMAX 15

typedef struct{
    DATA data[QUEUEMAX];
    int head;
    int tail;
} CycQueue;

（2）初始化队列

CycQueue *CycQueueInit()
{
    CycQueue *q;
    if (q=(CycQueue *)malloc(sizeof(CycQueue))) {
        q->head = 0;
        q->tail = 0;
        return q;
    }

    return NULL;
}

（3）释放队列

void CycQueueFree(CycQueue *q)
{
    if (q)
        free(q);
}

（4）获取队列状态

/*
*判断队列是否为空
*/

int CycQueueIsEmpty(CycQueue *q)
{
    return (q->head == q->tail);
}


/*
*判断队列是否已满
*/
int CycQueueIsFull(CycQueue *q)
{
    return ((q->tail+1)%QUEUEMAX == q->head);
}


/*
*获取队列的长度
*/
int CycQueueLen(CycQueue *q)
{
    int n;
    n = q->tail - q->head;
    if (n < 0) {
        n = QUEUEMAX + n;
    }
    return n;
}

（5）入队操作

int CycQueueIn(CycQueue *q, DATA data)
{
    if (CycQueueIsFull(q)) {
        printf("队列已满!\n");
        return 0;
    }
    q->tail = (q->tail+1)%QUEUEMAX;
    q->data[q->tail] = data;
    return 1;
}

（6）出队操作

DATA *CycQueueOut(CycQueue *q)
{
    int head;

    if (CycQueueIsEmpty(q)) {
        printf("队列已空!\n");
        return NULL;
    }

    head = q->head;
    q->head = (q->head +1)%QUEUEMAX;
    return &(q->data[head]);
}

（7）获取队头元素

DATA *CycQueuePeek(CycQueue *q)
{
    if (CycQueueIsEmpty(q)) {
        printf("队列已空!\n");
        return NULL;
    }
    return &(q->data[q->head]);
}