限定性线性结构 - 队列小结

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的特性：先进先出 FIFO

代码仓库地址

队列模型：

顺序队列结构设计（C语言）：

typedef struct {
    ElemType data[MAXSIZE];
    int front;
    int rear
}SeqQueue;

链式队列结构设计（C语言）：

// 结点结构设计
typedef struct QueueNode {
    ElemType data;
    struct QueueNode *next;
}QueueNode;

// 队列结构设计
typedef struct {
    QueueNode *front;
    QueueNode *rear;
}LinkQueue;

顺序队列

顺序队列中的溢出现象：

“下溢”现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
“真上溢”现象：当队列满时，做进队运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
“假上溢出”现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。

循环队列

所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。

为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。

因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）% MaxSize。队空和队满的情况如图：

顺序存储的循环队列 - 基本操作（C语言）

1. 初始化

Status initQueue(SeqQueue *queue) {
    queue->front = queue->rear = 0;
    return OK;
}

2. 清空

Status clearQueue(SeqQueue *queue) {
    queue->front = queue->rear = 0;
    return OK;
}

3. 判断是否为空

Status isEmptyQueue(SeqQueue queue) {
    if (queue.front == queue.rear) {
        return OK;
    }else return FALSE;
}

4. 队列长度

int lengthOfQueue(SeqQueue queue) {
    return (queue.rear - queue.front) % MAXSIZE;
}

5. 获取队头

int getFrontQueue(SeqQueue queue) {
    return queue.data[queue.front];
}

6. 入队

Status enQueue(SeqQueue *queue, ElemType e) {
    if (queue->front == (queue->rear + 1) % MAXSIZE) {
        printf("队列已满！\n");
        return ERROR;
    }
    
    queue->data[queue->rear] = e;
    queue->rear = (queue->rear++) % MAXSIZE;
    return OK;
}

7. 出队

Status deQueue(SeqQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        printf("队列为空！\n");
        return ERROR;
    }
    *e = queue->data[queue->front];
    queue->front = (queue->front++) % MAXSIZE;
    return OK;
}

8. 遍历

void traverseQueue(SeqQueue queue) {
    int i = queue.front;
    while (i != queue.rear) {
        printf("%d ", queue.data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
}

链式存储的队列 - 基本操作（C语言）

1. 初始化

Status initQueue(LinkQueue *queue) {
    queue->front = queue->rear = malloc(sizeof(QueueNode));
    
    if (queue->front == NULL) {
        return ERROR;
    }
    
    queue->front->next = NULL;
    return OK;
}

2. 销毁

Status destoryQueue(LinkQueue *queue) {
    while (queue->front) {
        queue->rear = queue->front->next;
        free(queue->front);
        queue->front = queue->rear;
    }
    return OK;
}

3. 清空

Status clearQueue(LinkQueue *queue) {
    
    QueueNode *p = queue->front->next;
    queue->rear = queue->front;
    queue->front->next = NULL;
    
    QueueNode *temp;
    while (p) {
        temp = p;
        p = p->next;
        free(temp);
    }
    
    return OK;
}

4. 判断是否为空

Status isEmptyQueue(LinkQueue queue) {
    if (queue.front == queue.rear) {
        return TRUE;
    }
    return FALSE;
}

5. 队列长度

int lengthOfQueue(LinkQueue queue) {
    QueueNode *p = queue.front;
    int i = 0;
    while (p != queue.rear) {
        p = p->next;
        i++;
    }
    return i;
}

6. 获取队头

Status getFront(LinkQueue queue, ElemType *e) {
    if (queue.front == queue.rear) {
        return FALSE;
    }
    
    *e = queue.front->next->data;
    return TRUE;
}

7. 入队

Status enQueue(LinkQueue *queue, ElemType e) {
    if (queue == NULL) {
        return ERROR;
    }
    
    QueueNode *temp = malloc(sizeof(QueueNode));
    if (temp == NULL) {
        return ERROR;
    }
    temp->data = e;
    temp->next = NULL;
    
    queue->rear->next = temp;
    queue->rear = temp;
    
    return OK;
}

8. 出队

Status deQueue(LinkQueue *queue, ElemType *e) {
    
    if (queue->front == queue->rear) {
        printf("空的队列\n");
        return ERROR;
    }
    
    QueueNode *temp = queue->front->next;
    *e = temp->data;
    
    queue->front->next = temp->next;
    
    if (queue->rear == temp) {
        queue->front = queue->rear;
    }
    free(temp);
    return OK;
}

9. 遍历

void traverse(LinkQueue queue) {
    QueueNode * p = queue.front->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

总结

顺序存储的队列会产生”假溢出“现象，循环队列能够避免”假溢出“现象，通常顺序存储结构的队列都是循环队列
链式存储结构的队列就是一个操作受到限制的单链表

所有和时间操作都有队列的影子。比如操作系统执行任务，先进去的先执行。时间是个参数（还有其他参数，优先级等等）等待队列，阻塞队列。