队列

队列存储结构特点

（1）队列中的数据元素遵循“先进先出”的原则
（2）在队尾添加元素，在队头删除元素。

队列的相关概念：

（1）队头与队尾： 允许元素插入的一端称为队尾，允许元素删除的一端称为队头；
（2）入队：队列的插入操作；
（3）出队：队列的删除操作。

队列的操作：

（1）入队： 通常命名为push()
（2）出队： 通常命名为pop()
（3）求队列中元素个数
（4）判断队列是否为空
（5）获取队首元素

队列的分类：

（1）基于数组的循环队列（循环队列）
（2）基于链表的队列（链队列）

数组实现

#include <stdio.h>
#include <string.h>#define QUE_SIZE 10  //最大队列长度+1 ,实际长度为9typedef struct QueueInfo
{int front; //队头int tail;//队尾int queueArr[QUE_SIZE];}QUEUE;//判断队列是否为满int QueueIsFull(QUEUE *queue)
{if ((queue->tail+2)% QUE_SIZE == queue->front) //队列满的条件{printf("queue is full\n");return -1;}else //队列不为满return 0;}//判断队列是否为空int QueueIsEmpty(QUEUE *queue)
{if ((queue->tail + 1) % QUE_SIZE == queue->front) //为空的条件{printf("queue is empty\n");return -1;}elsereturn 0;
}//入队int QueueInsert(QUEUE *queue, int value)
{if (QueueIsFull(queue)) //如果尾部入队失败，即队列已满return -1;queue->tail = (queue->tail+1)%QUE_SIZE;//更新队尾元素queue->queueArr[queue->tail] = value; //插入新的队尾元素printf("insert %d  to %d\n",value,queue->tail);	return 0;
}//出队int QueueDelete(QUEUE * queue, int *value)
{if (QueueIsEmpty(queue))return -1;*value = queue->queueArr[queue->front];//删除头存放在value中printf("delete value from front %d  is %d\n",queue->front,*value);queue->front = (queue->front + 1)%QUE_SIZE;//更新头指针		return 0;
}int main(int argc, char const *argv[])
{int value = 0;int i = 0;int j = 0;QUEUE queue;memset(&queue,0,sizeof(queue));queue.front = 1;queue.tail = 0;//假设入队位12个数据，则只有前10个在队内，剩下3个入队失败for (i = 0; i < 12; i ++)QueueInsert(&queue,i);for (i = 0; i < 12; i++) //出队数据，最后3个出队失败QueueDelete(&queue,&i);return 0;
}

链表实现

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{int data;struct Node *next;
}Qnode;
typedef struct 
{Qnode *front;//指向链表头结点 Qnode *rear;//指向链表尾结点 
}Q;int deleteQ(Q *q)//删除结点并返回删除结点的值 
{Qnode *temp;int term;if(q->front == NULL){printf("队列空！\n");return 0;}temp = q->front;//保留头结点 if(q->front == q->rear)//若队列只有一个元素 q->front = q->rear = NULL;//将头结点尾结点都设为空 elseq->front = q->front->next;//否则改变头结点term = temp->data; free(temp);//释放头结点 return term;//返回头结点的值 
}void AddQ(Q *q,int num)//增添结点 
{Qnode *p = (Qnode *)malloc(sizeof(Qnode));p->data = num;Qnode *temp = q->rear;if(temp != NULL)//判断队列是否为空 {temp->next = p;q->rear = p;p->next = NULL;}else{q->front =  p;//若队列为空，将首尾均指向新增结点 q->rear = p;p->next = NULL;}
} 
int main()
{Q *q =(Q *) malloc(sizeof(Q));q->front = q->rear = NULL; for(int i = 0;i < 2;i++){AddQ(q,i);}for(int i = 0;i<2;i++){int n = deleteQ(q);printf("%d\t",n);}free(q);return 0;
}