顺序队列（循环队列）

顺序队列的实现方法和顺序表相同，只不过顺序队列比顺序表多了一个表示结构体成员表示队头元素的下标。

结构体

#define N 5
typedef int datatype;
typedef struct
{
    datatype data[N];
    int rear;
    int front;
}sequeue_t;

上述结构体表示该顺序队列能存放N-1个有效元素（留出一个空间来区分队空和队满），rear表示尾元素的下一个位置（存数据端），front表示队头（第一个）有效元素的下标（取数据端）。

创建一个空队列

sequeue_t *CreateEmptySequeue()
{
    sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));
    if (p == NULL)
    {
        perror("create malloc error");
        return NULL;
    }
    p->front = 0;
    p->rear = 0;
    return p;
}

1.开辟一个队列结构体大小的堆区空间
2.此时队列无有效元素，将队头和队尾下标都初始化为0

入队

int InSequeue(sequeue_t *p, datatype data)
{
    if (IsFullSequeue(p))
    {
        perror("full");
        return -1;
    }
    p->data[p->rear] = data;
    p->rear = (p->rear + 1) % N;
    return 0;
}

1.容错判断（判断队列是否为满）
2.将数据插入到队尾处
3.将队尾下标向后移动一位
这里移动队尾下标时，不能像顺序表一样单纯+1，顺序队列也叫循环队列，可以循环插入，当队尾下标为N时，单纯+1会导致越界访问，所以不管是队头和队尾的移动都要先+1，再对N取余，这样当队尾下标为N时，向后移动时会再次循环到对头插入。
判断队列是否为满：

int IsFullSequeue(sequeue_t *p)
{
    return (p->rear + 1) % N == p->front;
}

rear永远是队尾元素的下一位置，当rear的下一位置和队头位置相等时说明队列已满。

出队

datatype OutSequeue(sequeue_t *p)
{
    if (IsEmptySequeue(p))
    {
        perror("empty");
        return -1;
    }
    datatype temp = p->data[p->front];
    p->front = (p->front + 1) % N;
    return temp;
}

1.容错判断（判断队列是否为空）

int IsEmptySequeue(sequeue_t *p)
{
    return p->front == p->rear;
}

2.定义临时变量存储出队数据
3.将队头front向后移动一位
4.返回出队数据

求队列的长度

int LengthSequeue(sequeue_t *p)
{
    return (p->rear - p->front + N) % N;
}

计算队列长度时，要考虑到rear和front的不同位置的所有情况

清空队列

void ClearSequeue(sequeue_t *p)
{
    p->front = p->rear;
}

链式队列

链式队列的实现方法相当于有头链表，只不过多了一个尾指针

结构体

typedef int datatype;
typedef struct node
{
    datatype data;
    struct node *next;
}linkqueue_node_t,*linkqueue_list_t;
typedef struct
{
    linkqueue_list_t front;
    linkqueue_list_t rear;
}linkqueue_t;

链式队列的结构体包括两部分，第一部分是链表的结构体，包括数据域和指针域；第二部分是指针的结构体，成员包括链表结构体类型的头指针和尾指针。

创建空队列

linkqueue_t *CreateEmptyLinkQueue()
{
    linkqueue_t *p = (linkqueue_t *)malloc(sizeof(linkqueue_t));
    if (p == NULL)
    {
        perror("p malloc error");
        return NULL;
    }
    p->front = p->rear = (linkqueue_node_t *)malloc(sizeof(linkqueue_node_t));
    if (p->front == NULL)
    {
        perror("p->front&p->rear malloc error");
        return NULL;
    }
    p->front->next = NULL;
    return p;
}

1.开辟指针结构体大小的空间
2.让头尾指针指向开辟的链表结构体空间的首地址
3.对头节点的指针域初始化（赋值为空）

入队

int InLinkQueue(linkqueue_t *p, datatype data)
{
    linkqueue_node_t *pnew = (linkqueue_node_t *)malloc(sizeof(linkqueue_node_t));
    if (pnew == NULL)
    {
        perror("pnew malloc error");
        return -1;
    }
    pnew->data = data;
    pnew->next = NULL;
    p->rear->next = pnew;
    p->rear = pnew;
    return 0;
}

1.开辟一个链表结构体大小的空间（新节点）
2.将入队数据赋给新节点的数据域
3.将新节点用尾插法插入到队尾
4.移动尾指针指向最后一个节点

判断队列是否为空

int IsEmptyLinkQueue(linkqueue_t *p)
{
    return p->front == p->rear;
}

首尾节点相等时说明队列为空

出队

datatype OutLinkQueue(linkqueue_t *p)
{
    if (IsEmptyLinkQueue(p))
    {
        perror("empty");
        return -1;
    }
    linkqueue_t *pdel = p->front;
    p->front = p->front->next;
    free(pdel);
    return p->front->data;
}

1.容错判断（队列为空返回-1）
2.定义一个临时指针指向头节点
3.将头指针后移一位，并free掉头节点，
4.返回此时头节点的数据，将此时头节点继续当作数据域无效的头节点使用

计算队列长度

int LengthLinkQueue(linkqueue_t *p)
{
    int len = 0;
    linkqueue_node_t *h = p->front;
    while (h->next != NULL)
    {
        h = h->next;
        len++;
    }
    return len;
}

相当于遍历有头链表

清空队列

void ClearLinkQueue(linkqueue_t *p)
{
    while (!IsEmptyLinkQueue(p))
        OutLinkQueue(p);
}

如果队列不为空，就执行出队函数