数据结构：顺序队列

顺序队列.c

//
// Created by 方朋 on 16/12/20.
//


#include <stdio.h>
#include <stdlib.h>
#include "global.h"

/*
 * ADT 队列(Queue)
 * Data
 *  同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
 * Operation
 *  InitQueue(*Q)       // 初始化, 建立一个空队列
 *  DestroyQueue(*Q)    // 若Q存在则销毁队列
 *  ClearQueue(*Q)      // 将队列Q清空
 *  QueueEmpty(Q)       // 是否为空
 *  GetHead(Q, *e)      // 若队列存在且非空,用e返回队列Q的队头元素
 *  EnQueue(*Q, e)      // 若队列Q存在,插入新元素e到队列Q中并成为队尾元素
 *  DeQueue(*Q, *e)     // 删除队列Q中队头元素,并用e返回其值
 *  QueueLength(Q)      // 返回队列Q的元素个数
 * endADT
 */

#define MAXSIZE 5

typedef int QElemType;

// 循环队列顺序存储结构
typedef struct
{
    QElemType data[MAXSIZE];
    int front;      // 头指针
    int rear;       // 尾指针,若队列不为空, 指向队尾元素的下一个位置
} SqQueue;

// 初始化一个空队列Q
// front == rear == 0
Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

/* 将Q清为空队列 */
Status ClearQueue(SqQueue *Q)
{
    Q->front=Q->rear=0;
    return OK;
}

// 返回Q的元素个数,也就是队列的当前长度
int QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

// 是否队满
int FullQueue(SqQueue Q)
{
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

// 是否队空
int EmptyQueue(SqQueue Q)
{
    return (Q.rear == Q.front);
}

// push
Status EnQueue(SqQueue *Q, QElemType e)
{
    if (FullQueue(*Q)) return ERROR;        // 队列是否满了
    Q->data[Q->rear] = e;                   // 将元素e赋值给队尾
    Q->rear = (Q->rear + 1) % MAXSIZE;      // rear指针向后移动一位置
    return OK;
}

// pop
Status DeQueue(SqQueue *Q, QElemType *e)
{
    if (EmptyQueue(*Q)) return ERROR;       // 队列是否为空
    *e = Q->data[Q->front];                 // 将队头元素赋值给e
    Q->front = (Q->front + 1) % MAXSIZE;    // 队头向后移动一位置
    return OK;
}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(SqQueue Q, QElemType *e)
{
    if (EmptyQueue(Q)) return ERROR;
    *e = Q.data[Q.front];
    return OK;
}


/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(SqQueue Q)
{
    int i = Q.front;
    while (i != Q.rear)
    {
        printf("%d ", Q.data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
    return OK;
}

int main(int argc, char **argv)
{
    Status j;
    int i = 0, l;
    QElemType d;
    SqQueue Q;

    InitQueue(&Q);
    printf(EmptyQueue(Q) ? "空" : "非空");

    printf("请输入整型队列元素(不超过%d个), -1为提前结束符: ", MAXSIZE - 1);
    do {
        scanf("%d", &d);
        if (d == -1)
            break;
        i++;
        EnQueue(&Q, d);
    } while (i < MAXSIZE - 1);

    printf("现在队列中的元素为: \n");
    QueueTraverse(Q);

    printf("队列长度:%d\n", QueueLength(Q));
    printf(EmptyQueue(Q) ? "空" : "非空");
    printf("连续%d次由队头删除元素,队尾插入元素:\n", MAXSIZE);
    for (int k = 1; k <= MAXSIZE ; ++k) {
        DeQueue(&Q, &d);
        printf("删除的元素是%d\n", d);
        printf("插入的元素:");
        scanf("%d", &d);
        EnQueue(&Q, d);
    }

    printf("现在队列中的元素为: \n");
    QueueTraverse(Q);

    j=GetHead(Q,&d);
    if(j)
        printf("现在队头元素为: %d\n",d);
    ClearQueue(&Q);
    printf("清空队列后, 队列空否？%u(1:空 0:否)\n", EmptyQueue(Q));
}

5个重点：

1. 空：Q->front=Q->rear
2. 初始化: Q->front=Q->rear=0
3. 长度：(Q->rear - Q.front + MAXSIZE) % MAXSIZE
4. 队满：(Q.rear + 1) % MAXSIZE == Q.front
5. 队头队尾向后移动，如果到头则从头开始移动： (Q.front + 1) % MAXSIZE; (Q.rear + 1) % MAXSIZE;