循环队列和链式队列的结构及其基本操作（入队、出队、取队头、查看对内元素）
循环队列
队列：只允许在一端进行插入操作，在另一端进行删除操作；数据存储在一个一维数组中
特点：先进先出（FIFO）结构
队头（front）：删除数据的一端
队尾（rear）：插入数据的一端
顺序队列的缺点：空队时front和rear都指向下标-1处，进队时rear先+1，再放入数据，出队时front先+1，再删数据
队满时一个个删数据，当front和rear都指向最后的位置时，前面的空间空余出来不能再使用。
循环队列的特点：存放数据的数组空间可以反复使用，单需要空出一个空间来区分队头队尾（以下程序中默认front的指向位置不存数据）。
反复使用存储空间的实现操作：front（rear）的操作：front（rear） = （front（rear）+1） % SIZE(存储数据的数组大小)
原因：当front（rear）走到队列最后（数组最大下标=SIZE-1）时，想要返回队列开头（数组最小下标=0）时，利用上述公式 (( SIZE-1) +1) % SIZE == SIZE % SIZE ==0(数组最小下标)。
队满情况：（rear+1）%SIZE ==front
队列长度：（rear-front+SIZE）% SIZE
队列结构和基本操作函数
#include
#define ERROR 0
#define OK 1
#define SIZE 11//队列空间大小
typedef struct queue
{
int data[SIZE];
int front;//队头，删除
int rear;//队尾，新增
}Queue;
//创建
int InitQueue(Queue *q)
{
if(q == NULL)
return ERROR;
//初始化
q->front = 0;
q->rear = 0;
return OK;
}
//新增
int Add(Queue *q, int data)
{
if(q == NULL || q->front == (q->rear + 1)%SIZE)
return ERROR;
q->rear = (q->rear + 1) % SIZE;//最开始空队列状态时，rear == front == 0；数据进队要先将rear往后移一位再存数据
q->data[q->rear] = data;
return OK;
}
//删除
int Delete(Queue *q, int *x)
{
if (q == NULL || q->rear == q->front)
return ERROR;
q->front = (q->front + 1) % SIZE;//front所在的位置不存（不读取）数据，删除数据就让front指向该数据的位置（队列只能从头开始依次删除数据）
*x = q->data[q->front];//main函数中的x获取删除的数据
return OK;
}
//取队头数据
int GetFront(Queue *q, int *x)
{
if (q == NULL)
return ERROR;
int data = (q->front+1) % SIZE;
*x = q->data[data];
return OK;
}
//打印数据
void print(Queue q)
{
if (q.rear == q.front)
{
printf("队列为空\n");
return;
}
int begin = (q.front + 1)%SIZE;//队列开头数据的下标,队头标志front所在位置的数据不读取（不存值）
int beyond = (q.rear + 1)%SIZE;//队列结尾数据的下一个位置的下标
int i;
for (i = begin; i != beyond; i = (i+1)%SIZE)//i从队列开头数据下标开始，依次往后加1，到队里最后时需要返回操
{ //作，一直到beyond的前一个位置
printf("%-4d", q.data[i]);//从队头第一个数据开始一直打印到最后一个数据
}
printf("\n");
}
//队列长度
int Length(Queue q)
{
return (q.rear - q.front + SIZE)%SIZE;
}
主函数，举例实践
int main()
{
Queue q;
InitQueue(&q);
int i;
for (i = 1; i < 11; i++)
{
Add(&q, i);
}
printf("当前队列中数据\n");
print(q);
int front;
printf("队头数据：%d\n", GetFront(&q, &front));
int x;
printf("出队数据\n");
for (i = 1; i < 3; i++)//出队两个
{
Delete(&q, &x);
printf("%-4d", x);
}
printf("\n");
//进队两个
Add(&q, 9);
Add(&q, 10);
printf("当前队列中数据\n");
print(q);
return 0;
}
链式队列
链式队列没有队满情况，可以添加任意个结点，操作特点：尾插头删
#include
#include
#define ERROR 0
#define OK 1
typedef struct node
{
int data;
struct node *next;
}Node;
typedef struct queue
{
Node* front;//队头，删除
Node* rear;//队尾，新增
}Queue;
//创建
Queue* InitQueue()
{
Queue* q = (Queue*)malloc(sizeof(Queue));
if (q == NULL)
return ERROR;
q->front = NULL;
q->rear = NULL;
return q;
}
//新增
int Add(Queue *q, int data)
{
if(q == NULL)
return ERROR;
//创建一个新结点
Node* node = (Node*)malloc(sizeof(Node));
if (NULL == node)
return ERROR;
node->data = data;
node->next = NULL;//尾插
if (q->front == NULL)//队列为空情况,队头队尾指针都指向新结点
{
q->front = node;
q->rear = node;
}
else//队列不空
{
q->rear->next = node;//队尾结点指向新结点
q->rear = node;//队尾指针指向队尾（新建结点插在队尾）
}
return OK;
}
//删除
int Delete(Queue *q, int *x)
{
if (q == NULL || q->front == NULL)
return ERROR;
Node* p = q->front;//保存当前队列的第一个结点地址
*x = p->data;
q->front = p->next;//队头指针指向原先队列的第二个结点（原先第二结点充当新队列的第一结点）
free(p);//释放（删除）原先第一结点的空间
if (q->front == NULL)//如果删除一个结点后，队列为空
q->rear == NULL;//原先队列只有一个结点的情况下，rear指向被删结点的空间，删除结点后需要置空
return OK;
}
//打印数据
void print(Queue *q)
{
if (NULL == q->front)
{
printf("队列为空\n");
return;
}
Node* tmp = q->front;//tmp指向队列第一个结点
while (tmp)
{
printf("%-4d", tmp->data);
tmp = tmp->next;
}
printf("\n");
}
int main()
{
Queue* q = InitQueue();
int i;
for (i = 1; i < 11; i++)
{
Add(q, i);
}
printf("当前队列中数据\n");
print(q);
int x;
printf("出队数据\n");
for (i = 1; i < 11; i++)//出队
{
Delete(q, &x);
printf("%-4d", x);
}
printf("\n");
printf("当前队列中数据\n");
print(q);
return 0;
}