数据结构与算法 — 队列

队列是一种特殊的线性表，只能在头尾两端进行操作。

• 队尾（rear）：只能从队尾添加元素，一般叫做enQueue，入队
• 对头（front）：只能从队头移除元素，一般叫做deQueue, 出队
• 先进先出的原则，First in first out， FIFO

队列的顺序存储

结构设计

typedef struct {
    QElemType data[QUEUE_INIT_SIZE];
    int front;
    int rear;
}SqQueue;

队列的创建

Status InitQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

获取对头元素

Status GetHead(SqQueue Q, QElemType *e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    *e = Q.data[Q.front];
    return OK;
}

入队

Status EnQueue(SqQueue *Q, QElemType e) {
    if ((Q->rear + 1) % QUEUE_INIT_SIZE == Q->front) {
        return ERROR;
    }
    
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % QUEUE_INIT_SIZE;
    return OK;
}

出队

Status DeQueue(SqQueue *Q, QElemType *e) {
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % QUEUE_INIT_SIZE;
    return OK;
}

队列的清空

Status ClearQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

队列判断是否为空

Status QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

队列的长度

int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + QUEUE_INIT_SIZE) % QUEUE_INIT_SIZE;
}

---

队列的链式存储

结构设计

typedef struct QueueNode {
    QElemType data;
    struct QueueNode *next;
}QueueNode, *QueueNodePtr;

typedef struct {
    QueueNodePtr front;
    QueueNodePtr rear;
}LinkQueue;

队列的创建

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

获取对头元素

Status GetHead(LinkQueue Q, QElemType *e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    
    *e = Q.front->next->data;
    return OK;
}

入队

Status EnQueue(LinkQueue *Q, QElemType e) {
    QueueNodePtr temp = (QueueNodePtr)malloc(sizeof(QueueNode));
    if (temp == NULL) {
        return ERROR;
    }
    temp->data = e;
    temp->next = NULL;
    Q->rear->next = temp;
    Q->rear = temp;
    return OK;
}

出队

Status DeQueue(LinkQueue *Q, QElemType *e) {
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    QueueNodePtr p;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) {
        Q->rear = Q->front;
    }
    
    free(p);
    return OK;
}

队列的销毁

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

队列的清除

Status ClearQueue(LinkQueue *Q) {
    QueueNodePtr p, q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    return OK;
}

队列判断是否为空

Status QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

队列的长度

int QueueLength(LinkQueue Q) {
    int i = 0;
    QueueNodePtr p = Q.front;
    while (Q.rear != p) {
        i++;
        p = p->next;
    }
    return i;
}