数据结构之队列

队列

队列：受限制的线性表，先进先出

队列可以用顺序存储，也可以用链式存储，顺序存储一般指数组，链式就是链表

用数组存储有很多缺点：
1、出队入队都要移动整个队列
2、如果不移动整个队列，只移动队首指针，就会造成盲区
3、如果不想出现盲区，需要使队列变为环形队列，复杂化了（可以尝试一下）

暂时使用链式存储来实现队列

C
.h

#ifndef Queue_h
#define Queue_h

#include <stdio.h>
#include <stdbool.h>

typedef int Item;

//队列的容量
#define MAXQUEUE 10

//结点定义
typedef struct node{
    Item item;
    struct node *next;
}Node;

//queue的定义
typedef struct queue{
    Node *front;//队首指针
    Node *rear;//队尾指针
    int items;//当前队中个数
}Queue;

//初始化
void InitializeQueue(Queue *pq);

//判断队满
bool QueueIsFull(const Queue *pq);

//判断队空
bool QueueIsEmpty(const Queue *pq);

//判断队中的个数
int QueueItemCount(const Queue *pq);

//入队
bool EnQueue(Item item,Queue *pq);

//出队
bool DeQueue(Item *item,Queue *pq);

//置空队列
void EmptyTheQueue(Queue *pq);

#endif /* Queue_h */

.c

#include "Queue.h"
#include <stdlib.h>

//初始化
void InitializeQueue(Queue *pq){
    pq->front = NULL;
    pq->rear = NULL;
    pq->items = 0;
}
//判断队满
bool QueueIsFull(const Queue *pq){
    return pq->items == MAXQUEUE;
}

//判断队空
bool QueueIsEmpty(const Queue *pq){
    return pq->items == 0;
}

//判断队中的个数
int QueueItemCount(const Queue *pq){
    return pq->items;
}

//入队
bool EnQueue(Item item,Queue *pq){
    Node *node = (Node *)malloc(sizeof(Node));
    if (QueueIsFull(pq) || node == NULL) {
        return false;
    }
    node->item = item;
    node->next = NULL;
    if (QueueIsEmpty(pq)) {
        pq->front = node;
    }else{
        pq->rear->next = node;
    }
    pq->rear = node;
    pq->items++;
    return true;
}

//出队
bool DeQueue(Item *item,Queue *pq){
    if (QueueIsEmpty(pq)) {
        return false;
    }
    item = &(pq->front->item);
    Node *waitFreeNode = pq->front;
    pq->front = waitFreeNode->next;
    free(waitFreeNode);
    pq->items--;
    if(QueueIsEmpty(pq)){
        
    }
    return true;
}

//置空队列
void EmptyTheQueue(Queue *pq){
    while (!QueueIsEmpty(pq)) {
        DeQueue(NULL, pq);
    }
}