数据结构之队列
1.什么是数据结构？
计算机中存储、组织数据的方式。如下内存图中，每一个数据在存储时，决定了数据的顺序和位置关系便是数据结构。
常用的数据结构有：数组、队列、栈、堆、树等。本篇文章整理队列。
2.什么是队列？
队列是一种特殊的线性表，特殊之处在于它只能在表的前端取出数据，在表的后端插入数据，进行插入操作的一端称为队尾，进行删除操作的一段称为队头。队列中没有数据时称为空队列。
在队列中插入一个元素称为入队，删除一个元素叫做出队，因为队列只允许在一端插入，另一端删除，所以在删除数据时，最先删除的数据是最先进入队列的数据，以下图为例。
数据的存入顺序为：1、2、3
取出数据的顺序为：1、2、3
所以队列又称为先进先出（first in first out）。
3.队列的实现
线性表有顺序存储和链式存储，队列作为一种特殊的线性表，也同样存在两种存储方式。本文讲解顺序存储。
顺序队列
用数组存储队列。即利用一组地址连续的存储单元依次存放队列中的元素。为了避免当只有一个元素时，队头和队尾重合使得处理变得麻烦，所以引入两个指针（头尾指针）。
Front指针指向队头元素，rear指针指向队尾元素的下一个位置。初始化时的头尾指针，初始值均为0。入队时尾指针
rear加1,出队时头指针front加1，头尾指针相等时队列为空。
顺序队列实现代码如下：
#include <stdio.h>
#define MAX_SIZE 5//数组最多存放的元素个数
enum Bool{FALSE,TRUE};
struct queue
{
int container[MAX_SIZE];//存放元素的数组
int size;//记录数组中元素个数
int rear;//尾指针
int front;//头指针
};
//判断队列是否溢出 溢出返回TRUE,否则返回FALSE
enum Bool is_full( struct queue *self )
{
if(self -> size == MAX_SIZE)
{
return TRUE;
}
return FALSE;
}
//入队 向队列插入一个元素data
void is_push( struct queue *self, int data )
{
if( self -> full(self))//失败返回-1
{
printf("que is full\n");
return -1 ;
}
self -> container[self -> rear] = data;//从队尾插入数据
int ret = self -> rear;//记录本次插入数据的下标
self-> size++;
self -> rear = (self -> rear+1) % max_size;//rear指向往后移一个位置
return ret;//插入成功返回下标
}
//出队 从队列中取出一个元素
int is_pop( struct queue *self )
{
if(self -> empty(self))
{
printf("que is empty\n");
return -1;
}
int data = self -> conttainer[self -> front];
self -> size--;
self -> front = (self -> front+1) % MAX_SIZE;
return data;
}
//队列为空返回TRUE,否则返回false
enum Bool is_empty( struct queue *self )
{
if(self -> size == 0)
{
return TRUE;
}
return FALSE;
}
//初始化一个队列
void init_que( struct queue *self )
{
self -> size = 0;
self -> rear = 0;
self -> front = 0;
}
int main()
{
struct queue que;
init_que(&que);//初始化队列
int size = que.size;
int i = 0;
for(i = 0; i < size; i++)
{
printf(“%d\n,is_que_push(i,&que));//顺序插入数据，成功返回数据在数组中的下标，失败返回-1
}
for(i = 0; i < size; i++)
{
printf("%d\n",is_que_pop(&que));//顺序取出数据，成功返回取出数据，失败返回-1
}
return 0;
}
~
顺序队列使用数组实现的，首指针在出队的时候移动，尾指针在入队的时候移动，需要考虑队列为空和队列为满的两种情况。
