目录

一、循环顺序队列

1.1 假溢出现象

1.2 循环顺序队列 

1.3 算法实现

1.3.1 初始化队列

1.3.2 入队操作 

1.3.3 出队操作 

1.3.4 读取队头元素 

1.3.5 判空操作

1.3.6 判满操作 

二、链队列

2.1 初始化队列

2.2 入队操作

2.3 出队操作

2.4 读取队头元素

2.5 判空操作

2.6 销毁操作 

三、循环链表队列

1.1 假溢出现象

---

1.2 循环顺序队列 

循环顺序队列：将顺序队列的数组看成一个环状空间，即规定最后一个单元的后继为第一个单元。

虽然不存在物理的循环操作，但是可以通过软件方法实现 —— 使用求模操作。

求模操作：（4+1）mod 5 = 0

---

1.3 算法实现

1.3.1 初始化队列

void InitQueue(QueuePtr Q) {
    Q->front = Q->rear = 0;
}

1.3.2 入队操作 

bool EnterQueue(QueuePtr Q, QueueElementType x) {
    if (IsFull(Q)) return false;

    
    Q->element[Q->rear] = x;
    
    
    Q->rear = (Q->rear + 1) % MAXSIZE;

    return true;
}

1.3.3 出队操作 

bool DeleteQueue(QueuePtr Q, QueueElementType *x) {
    if (IsEmpty(Q)) return false;

    
    *x = Q->element[Q->front];

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

    return true;
}

1.3.4 读取队头元素 

bool GetHead(QueuePtr Q, QueueElementType *x) {
    if (IsEmpty(Q)) return false;
    
    
    *x = Q->element[Q->front];

    return true;
}

1.3.5 判空操作

bool IsEmpty(QueuePtr Q) {
    
    return Q->front == Q->rear;
}

1.3.6 判满操作 

bool IsFull(QueuePtr Q) {
    
    return (Q->rear + 1) % MAXSIZE == Q->front;
}

---

二、链队列

链队列：用链表表示的队列。

typedef struct Node {
    QueueElementType data;     
    struct Node *next;         
} LinkQueueNode, *LinkQueueNodePtr;


typedef struct {
    LinkQueueNode *front;      
    LinkQueueNode *rear;       
} LinkQueue, Queue, *QueuePtr;

---

2.1 初始化队列

void InitQueue(QueuePtr Q) {
    
    Q->front = (LinkQueueNodePtr)malloc(sizeof(LinkQueueNode));
    Q->front->next = NULL;
    
    Q->rear = Q->front;
}

2.2 入队操作

bool EnterQueue(QueuePtr Q, QueueElementType x) {
    
    LinkQueueNode * NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    NewNode->data = x;
    NewNode->next = NULL;

    if (NewNode == NULL)
        return false;

    
    Q->rear->next = NewNode;
    Q->rear = NewNode;
    return true;
}

2.3 出队操作

情况1：队列中有不止一个元素。

情况2：队列中只有一个元素。

bool DeleteQueue(QueuePtr Q, QueueElementType *x) {
    if (IsEmpty(Q)) return false;

    
    LinkQueueNodePtr p = Q->front->next;
    Q->front->next = p->next;

    
    if (Q->rear == p)
        Q->rear = Q->front; 
    
    
    *x = p->data;
    free(p);

    return true;
}

2.4 读取队头元素

bool GetHead(QueuePtr Q, int *x) {
    if (IsEmpty(Q)) return false;
    
    
    *x = Q->front->data;

    return true;
}

2.5 判空操作

bool IsEmpty(QueuePtr Q) {
    
    return Q->front == Q->rear;
}

2.6 销毁操作 

void ClearQueue(QueuePtr Q) {
    LinkQueueNodePtr p = Q->front, q;
    
    
    while (p != NULL) {
        q = p;
        p = p->next;
        free(q);
    }
}

---

三、循环链表队列

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点。

typedef struct _QueueNode {
    ElemType data;
    struct _QueueNode *next;
} LinkQueueNode, *LinkQueue;


bool init_queue(LinkQueue *LQ) {
	*LQ = (LinkQueue)malloc(sizeof(LinkQueueNode));
	if (*LQ == NULL) return false;

    (*LQ)->next = (*LQ);
    return true;
}


bool enter_queue(LinkQueue *LQ, ElemType x) {
    LinkQueue p = (LinkQueue)malloc(sizeof(LinkQueueNode));
    if (p == NULL) return false;
    p->data = x;

    p->next = (*LQ)->next;
    (*LQ)->next = p;
    (*LQ) = p;
    
    return true;
}


bool leave_queue(LinkQueue *LQ, ElemType *x) {
    LinkQueueNode * head = (*LQ)->next, p;
    if ((*LQ) == head) return false;

    p = head->next;
    head->next = p->next;
    
    if (p->next == head)
        (*LQ) = head;
    
    *x = p->data;
    free(p);

    return true;
}