循環隊列

簡介

循環隊列就是将隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列結構中，當存儲空間的最後一個位置已被使用而再要進入隊運算時，隻需要存儲空間的第一個位置空閑，便可将元素加入到第一個位置，即将存儲空間的第一個位置作為隊尾。循環隊列可以更簡單防止僞溢出的發生，但隊列大小是固定的。

在循環隊列中，當隊列為空時，有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）線性表。