队列原理以及实现

队列模型

入队

在表的末尾插入一个元素，模型语言就是，队列大小+1，队尾指针+1

出队

在表的开头删除一个元素，模型语言就是，队列大小-1，队头指针+1

整个模型满足先入先出

数组实现

在嵌入式设计中，使用一个队列通常需要事先分配一个空间而不是动态分配一个空间，是因为嵌入式芯片的堆区很小（当然也可以自己扩大），所以使用数组来实现队列在嵌入式应用中比较适合。

队头队尾指针在碰到数组边界时候，需要循环初始位置。使用循环数组来进行实现，入队出队时指针对最大队列进行取模就可以完成。

队列的数据结构

typedef struct {
    ElementType *data;
    unsigned int front;  // 队头位置
    unsigned int rear;   // 队尾位置
    unsigned int size;   // 队列大小
} Queue;

需要实现以下几个函数

bool CreateQueue(Queue *queue,ElementType *buffer);
bool isFull(Queue *queue);
bool isEmpty(Queue *queue);
void Enqueue(Queue *queue,ElementType element);
void Dequeue(Queue *queue);
void MakeEmpty(Queue *queue);
ElementType FrontAndDequeue(Queue *queue);
ElementType Front(Queue *queue);
void printfQueue(Queue *queue);

函数实现

/**
 * @brief 创建一个队列，需要从外部传入空间
 */
bool CreateQueue(Queue *queue,ElementType *buffer) 
{
    if (queue != NULL && buffer != NULL)
    {
        queue->front = 0;           // 队头指针
        queue->rear = 0;            // 队尾指针
        queue->size = 0;            // 队列大小
        queue->data = buffer;       // 缓冲区
        return true;
        /* code */
    }
    else
        return false;
}

/**
 * @brief 判断队列是否为满
 */ 
bool isFull(Queue *queue)
{
    return (queue->size == MAXSIZE);
}

/**
 * @brief 判断队列是否为空
 */ 
bool isEmpty(Queue *queue)
{
    return (queue->size == 0);
}

/**
 * @brief 入队操作
 */
bool Enqueue(Queue *queue,ElementType element)
{
    if(isFull(queue))
    {
        printf("Full queue");
        return false;                           // 队列已经满了
    }
    queue->data[queue->rear++] = element;       // 队尾加入元素
    queue->size++;                              // 大小加1
    queue->rear %= MAXSIZE;                     // 队尾指针循环判定
    
    return true;
}

/**
 * @brief 出队操作
 */ 
void Dequeue(Queue *queue)
{
    queue->size--;                          // 大小减1
    queue->front++;                         // 队头指针加1
    queue->front %= MAXSIZE;                // 队头指针循环   
}

/**
 * @brief 队列清空
 */ 
void MakeEmpty(Queue *queue)
{
    queue->size = 0;
    queue->front = 0;
    queue->rear = 0;
}

/**
 * @brief 取队头元素
 */ 
ElementType Front(Queue *queue)
{
    return queue->data[queue->front];
}

/**
 * @brief 取队头元素并且出队
 */ 
ElementType FrontAndDequeue(Queue *queue)
{
    unsigned int index = queue->front;
    
    Dequeue(queue);

    return queue->data[index];
}

/**
 * @brief 打印队列
 */ 
void printfQueue(Queue *queue)
{
    int index = queue->front;

    if (isEmpty(queue))
    {
        printf("queue is empty!!!\n");
        return;
        /* code */
    }
    
    for (int i = 0; i < queue->size; i++)
    {
        printf("%d ",queue->data[index++]);
        /* code */
    }
    printf("\n");
}

主函数测试

int main(int argc, char const *argv[])
{
    ElementType buffer[MAXSIZE];

    Queue queue;
    CreateQueue(&queue, buffer);

    for (size_t i = 0; i < MAXSIZE; i++)
    {
        Enqueue(&queue, i);
        /* code */
    }

    printfQueue(&queue);

    for (size_t i = 0; i < MAXSIZE/2; i++)
    {
        if (! isEmpty(&queue))
        {
            Dequeue(&queue);
        }else{
            printf("Queue Empty");
        }
    }

    printfQueue(&queue);

    for (size_t i = 0; i < MAXSIZE/2; i++)
    {
        if (! isEmpty(&queue))
        {
            Dequeue(&queue);
        }else{
            printf("Queue Empty");
        }
    }
    printfQueue(&queue);

    for (size_t i = 0; i < MAXSIZE; i++)
    {
        Enqueue(&queue, i);
        /* code */
    }

    printfQueue(&queue);

    MakeEmpty(&queue);

    printfQueue(&queue);

    return 0;
}