为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

中文名

循环队列

外文名

Circular Queue

领域

数据结构

实现方式

单链表

有关术语

队列

特点

大小固定

简介

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾[1]。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。

基本操作

1

// 队列的顺序存储结构(循环队列)

2

#define MAX_QSIZE 5 // 最大队列长度+1

3

typedef struct {

4

    int *base; // 初始化的动态分配存储空间

5

    int front; // 头指针，若队列不空，指向队列头元素

6

    int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置

7

} SqQueue;

8

　

9

　

10

// 构造一个空队列Q

11

SqQueue* Q_Init() {

12

    SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue));

13

    // 存储分配失败

14

    if (!Q){

15

        exit(OVERFLOW);

16

    }

17

    Q->base = (int *)malloc(MAX_QSIZE * sizeof(int));

18

    // 存储分配失败

19

    if (!Q->base){

20

        exit(OVERFLOW);

21

    }

22

    Q->front = Q->rear = 0;

23

    return Q;

24

}

25

　

26

// 销毁队列Q，Q不再存在

27

void Q_Destroy(SqQueue *Q) {

28

    if (Q->base)

29

        free(Q->base);

30

    Q->base = NULL;

31

    Q->front = Q->rear = 0;

32

    free(Q);

33

}

34

　

35

// 将Q清为空队列

36

void Q_Clear(SqQueue *Q) {

37

    Q->front = Q->rear = 0;

38

}

39

　

40

// 若队列Q为空队列，则返回1；否则返回-1

41

int Q_Empty(SqQueue Q) {

42

    if (Q.front == Q.rear) // 队列空的标志

43

        return 1;

44

    else

45

        return -1;

46

}

47

　

48

// 返回Q的元素个数，即队列的长度

49

int Q_Length(SqQueue Q) {

50

    return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;

51

}

52

　

53

// 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR

54

int Q_GetHead(SqQueue Q, int &e) {

55

    if (Q.front == Q.rear) // 队列空

56

        return -1;

57

    e = Q.base[Q.front];

58

    return 1;

59

}

60

　

61

// 打印队列中的内容

62

void Q_Print(SqQueue Q) {

63

    int p = Q.front;

64

    while (Q.rear != p) {

65

        cout << Q.base[p] << endl;

66

        p = (p + 1) % MAX_QSIZE;

67

    }

68

}

69

　

70

// 插入元素e为Q的新的队尾元素

71

int Q_Put(SqQueue *Q, int e) {

72

    if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满

73

        return -1;

74

    Q->base[Q->rear] = e;

75

    Q->rear = (Q->rear + 1) % MAX_QSIZE;

76

    return 1;

77

}

78

　

79

// 若队列不空，则删除Q的队头元素，用e返回其值，并返回1；否则返回-1

80

int Q_Poll(SqQueue *Q, int &e) {

81

    if (Q->front == Q->rear) // 队列空

82

        return -1;

83

    e = Q->base[Q->front];

84

    Q->front = (Q->front + 1) % MAX_QSIZE;

85

    return 1;

86

}

条件处理

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。

解决这个问题的方法至少有两种：

①另设一布尔变量以区别队列的空和满；

②另一种方式就是数据结构常用的：队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图1所示情况，队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。

类型定义采用环状模型来实现队列,各数据成员的意义如下：

front指定队首位置，删除一个元素就将front顺时针移动一位；

rear指向元素要插入的位置，插入一个元素就将rear顺时针移动一位；

count存放队列中元素的个数，当count等于MaxQSize时，不可再向队列中插入元素。

队列

数据结构分为线性结构和非线性结构，队列和线性表都是线性结构。线性表是由n个数据元素组成的有限序列，该序列有惟一的“第一个”和惟一的“最后一个”数据元素；除了“第一个”和“最后一个”之外，队列中的每个数据元素都只有一个直接前驱和一个直接后继。线性表的插入和删除操作可以在表中任意位置进行。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。