数据结构——队列（C代码实现）

今天药忘吃喽~ 2022-12-29 12:59 210阅读 0赞

### 目录 ###

*  普通队列
 *   *  结构定义
     *  结构操作
     *  代码实现
 *  循环队列
 *   *  结构定义
     *  结构操作
     *  代码实现

# 普通队列 #

## 结构定义 ##

队列是一种先进先出`FIFO`的数据结构，即最先进入队列的数据，也是最先退出队列的，就像排队一样，其结构包括：

1.  存储空间`data`。队列是用一段连续存储空间存数据的，所以存储空间可以用动态数组实现。
2.  队列容量`size`。用于记录队列动态数组空间的大小。
3.  队首下标`head`。用于记录队列的首位元素存储在动态数组的哪个下标中。
4.  队尾下标`tail`。根据结构操作代码设计的不同，可以用于记录队列末尾元素存储在动态数组的哪个下标中，或者用于记录队列新加入元素可以存储在动态数组的哪个下标中，在我的代码设计中用到的是第二种情况。

## 结构操作 ##

1.  初始化队列`init()`。用于新建一个队列，并初始化各个参数。
2.  判断队列为空`empty()`。
3.  扩容`expand()`。扩大队列容量。
4.  入队`push()`。用于添加元素进队列的末尾。
5.  出队`pop()`。用于弹出队首元素。
6.  获取队首元素`front()`。
7.  清除队列`clear()`。用于回收使用队列时动态开辟的空间。

## 代码实现 ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Queue {
        
        //定义指针指向动态数组空间
        int *data;
        //定义队列大小、元素数量
        int size;
        //定义队首、队尾
        int head, tail;
    } Queue;
    
    Queue *init(int n) {
        
        //开辟队列空间
        Queue *q = (Queue *)malloc(sizeof(Queue));
        //开辟动态数组空间
        q->data = (int *)malloc(sizeof(int) * n);
        //初始化队列大小
        q->size = n;
        //初始化队首、队尾
        q->head = q->tail = 0;
        return q;
    }
    
    int empty(Queue *q) {
        
        return q->head == q->tail;
    }
    
    int expand(Queue *q) {
        
        //定义需要扩容的大小
        int extr = q->size;
        //定义新指针，用于指向扩容空间
        int *p;
        while (extr) {
        
            p = (int *)realloc(q->data, sizeof(int) * (q->size + extr));
            //p不为空地址，则扩容成功，退出循环
            if (p) break;
            //扩容失败，扩容的大小缩减一半，再尝试扩容
            extr /= 2;
        }
        //p为空地址，完全没有空间可以再扩容了，扩容失败
        if (!p) return 0;
        //扩容成功后，更新队列空间、队列大小
        q->data = p;
        q->size += extr;
        return 1;
    }
    
    int push(Queue *q, int val) {
        
        if (q == NULL) return 0;
        //队列已满，尝试扩容
        if (q->tail == q->size) {
        
            if (!expand(q)) return 0;
        }
        //队尾加入新元素
        q->data[q->tail] = val;
        q->tail += 1;
        return 1;
    }
    
    int pop(Queue *q) {
        
        if (q == NULL) return 0;
        if (empty(q)) return 0;
        //队首下标后移一位，相当于弹出旧队首元素
        q->head += 1;
        return 1;
    }
    
    int front(Queue *q) {
        
        return q->data[q->head];
    }
    
    void clear(Queue *q) {
        
        if (q == NULL) return ;
        free(q->data);
        free(q);
        return ;
    }

--------------------

# 循环队列 #

## 结构定义 ##

>   假设队列空间固定，且不会自动扩容，当`head == size - 1`时，即队首元素存储在数组的最后一位时，队列就不可再新增元素了，不过数组前面其实还有空间可以存储，这就导致了`假溢出`的情况。虽然可以为队列增加自动扩容操作，但是这明显会导致过多的空间浪费，为了解决假溢出最好的办法就是将队列设计成循环队列，即队列空间没有存满的情况下，head和tail能够循环走到数组未存元素的下标。为此，需要新增一个变量`cnt`用于记录当前队列元素个数。

## 结构操作 ##

## 代码实现 ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct Queue {
        
        //定义指针指向动态数组空间
        int *data;
        //定义队列大小、元素数量
        int size, cnt;
        //定义队首、队尾
        int head, tail;
    } Queue;
    
    Queue *init(int n) {
        
        //开辟队列空间
        Queue *q = (Queue *)malloc(sizeof(Queue));
        //开辟动态数组空间
        q->data = (int *)malloc(sizeof(int) * n);
        //初始化队列大小
        q->size = n;
        //初始化队首、队尾
        q->head = q->tail = 0;
        //初始化元素数量
        q->cnt = 0;
        return q;
    }
    
    int empty(Queue *q) {
        
        return q->cnt == 0;
    }
    
    int expand(Queue *q) {
        
        //定义需要扩容的大小
        int extr = q->size;
        //定义新指针，用于指向扩容空间
        int *p;
        while (extr) {
        
            p = (int *)calloc(q->size + extr, sizeof(int));
            //p不为空地址，则扩容成功，退出循环
            if (p) break;
            //扩容失败，扩容的大小缩减一半，再尝试扩容
            extr /= 2;
        }
        //p为空地址，完全没有空间可以再扩容了，扩容失败
        if (!p) return 0;
        //扩容成功后，将旧队列拷贝到新队列中，并更新队列容量、队首、队尾
        for (int i = q->head, j = 0; i < extr; i++, j++) {
        
            p[j] = q->data[i % q->size];
        }
        free(q->data);
        q->data = p;
        q->size += extr;
        q->head = 0;
        q->tail = q->cnt;
        return 1;
    }
    
    int push(Queue *q, int val) {
        
        if (q == NULL) return 0;
        //队列已满，尝试扩容
        if (q->cnt == q->size) {
        
            if (!expand(q)) return 0;
        }
        //队尾加入新元素
        q->data[q->tail] = val;
        q->tail += 1;
        //队尾到达数组边界，循环队尾下标
        if (q->tail == q->size) q->tail = 0;
        q->cnt += 1;
        return 1;
    }
    
    int pop(Queue *q) {
        
        if (q == NULL) return 0;
        if (empty(q)) return 0;
        //队首下标后移一位，相当于弹出旧队首元素
        q->head += 1;
        //队首到达数组边界，循环队首下标
        if (q->head == q->size) q->head = 0;
        q->cnt -= 1;
        return 1;
    }
    
    int front(Queue *q) {
        
        return q->data[q->head];
    }
    
    void clear(Queue *q) {
        
        if (q == NULL) return ;
        free(q->data);
        free(q);
        return ;
    }