队列的种类和详解
队列的种类和详解
队列是一种常用的数据结构，是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的分类
根据实现方式，列表可以分为顺序队列和链表队列，
（1）顺序队列：顺序队列是用数组实现的，首指针在出队的时候移动，尾指针在入队的时候移动，需要考虑队列为空和队列为满的两种情况
如下图↓
（2）链式队列：链式队列是用链表实现的，首指针不移动始终指向头节点，尾指针在入队的时候移动，只考虑队列为空的情况（不用考虑满是因为链表长度在程序运行过程中可以不断增加，只要存储空间够malloc就能申请内存空间来存放节点）
如下图↓
队列的先进先出
队列采用FIFO，数据从队列尾输入，从队列头输出，先进去的就先出来，就像水在水管里流一样。
注：链式队列插入节点使用头插法时，最后进来，却最快从队列头输出，这是先进后出，不符合列表的先进先出原则。
顺序队列的循环代码实现
从上图可以看出循环队列的几个要素 :
队空状态 ：qu.rear == qu.front
队满状态 ： (qu.rear + 1) % Maxsize == qu.front
元素的进队操作：qu.rear = (qu.rear + 1) % Maxsize ; qu.data[qu.rear] = x ;l
元素的出队操作：qu.front = (qu.front + 1) % Maxsize ; x = qu.data[qu.front] ;
//顺序队列
#include stdio.h
#include stdlib.h
#define Maxsize 20 //规定了数组元素的个数，队列最大也只能有20个点，无法再变
/*定义队列的结构体*/
typedef struct Squeue{
int data[Maxsize]; //定义一个整形数组data，元素为20个
int front;//以下标的形式，指向队列的头
int rear;//以下标的形式，指向队列的尾
}Squeue;
/*初始化队列*/
void InitQueue(struct Squeue qu)//定义一个新的结构体变量qu，并将其地址作为形参，qu在函数里的变化会传递出来
{
qu.front = qu.rear = 0; //头尾下标相同，即指向同一点，队列为空
}
/*判断队列是否为空*/
int isQueueEmpty(Squeue qu) //定义一个新的结构体变量qu作为形参，函数返回后会自动释放掉qu
{
if(qu.front == qu.rear) //头尾下标相同，即指向同一点，队列为空
{
return 1;
}
else
{
return 0;
}
}
/*元素入队操作 */
int inQueue(Squeue qu,int x) //定义一个新的结构体变量qu，并将其地址作为形参，qu在函数里的变化会传递出来
{
//若队满则无法入队
if((qu.rear + 1) % Maxsize == qu.front)
{
return 0;
}
qu.rear = (qu.rear + 1) % Maxsize;//用取余的方式，实现循环
qu.data[qu.rear] = x;//向数组的尾指向的元素赋入数据
return 1;
}
//元素出队操作
int deQueue(Squeue qu,int x)
{
//若队空则无法出队
if(qu.front == qu.rear)
{
return 0;
}
qu.front = (qu.front + 1) % Maxsize;
x = qu.data[qu.front]; //把队列头的数据传送到x
return 1;
}
int main()
{
Squeue q;
int i , n , x , a;
InitQueue(q);
scanf(%d,n);
for(i = 0;in;i++)
{
scanf(%d,a);
inQueue(q,a);
}
//当队列非空时，输出队列中所有数据
while(!isQueueEmpty(q))
{
deQueue(q,x);
printf(%d ,x);
}
return 0;
}
链表队列的循环代码实现（部分）
typedef struct QNode/* 声明链式队列的结点 */
{
int data;
struct QNode *next;
}Node;
typedef struct QueuePoint/* 声明链式队列的首尾指针 */
{
Node *front;
Node *rear;
int length; /* 记录链式队列长度 */
}Queue;
//函数功能：初始化队列（其实就是搞个头结点放在队列里面）
//单独弄个子函数来初始化队列是为了方便入队的时候判断队列是否为空
Queue init (Queue p)
{
p.front = p.rear = (Node *)malloc(sizeof(Node));
if (p.front == NULLp.rear == NULL)
{
printf(initialization failed);
exit(0);
}
p.front-next = NULL;
return p;
}
//函数功能：新建节点并添加到队列中，记录队列长度
Queue AppendNode (Queue p)
{
int data;
Node *q;
q = (Node *)malloc(sizeof(Node));
if (q == NULL)/* 判断分配内存是否失败 */
{
printf(No enough memory to allocate);
exit(0);
}
p.rear-next = q;/* 最后一个节点的指针指向新建节点*/
p.rear = q;/* 队尾指针指向新建节点*/
printf(Input node datan);
scanf(%d, data);
p.rear-data = data;
p.rear-next = NULL;
p.length++;
return p;
}
总结
顺序队列部分代码非常简单，不过是把数据放在数组中，然后加上先进先出等限制，所谓循环不过因为数组本身的死板，于是加个取余来循环使用
链表队列我就不把循环写出来了，链表本身结构很自由，不像数组一样死板，新增和删掉节点都很容易，要回去了就把指针挪一挪。
以上就是（队列的种类和详解）全部内容，收藏起来下次访问不迷路！