目录
一、队列
1、队列概念
队列是一种特殊的线性表，也是一种运算受限的线性表，插入限定在表的某一端进行，删除限定在表的另一端进行。
2、队列的特征
先进先出、后进后出
3、队列存储结构
与栈类似，队列也有两种常用存储结构，即顺序存储结构和链式存储结构。
二、顺序队
1、顺序队定义
以顺序存储方式存储的队列称为顺序队。由一个一维数组和队头指针和队尾指针变量组成，一般用循环队列。
2、循环队列的四要素
（1）队空条件：sq.front==qs.rear.
（2）队满条件：(sq.rear+1)%MaxSize==sq.front.
（3）进队操作：sq.rear循环进1；元素进队。
（4）出队操作：sq.front 循环进1；元素出队.
3、循环队列的基本运算算法
（1）代码展示
#include <stdio.h>
#include<malloc.h>
typedef char ElemType;
#define MaxSize 200
typedef struct
{
ElemType data[MaxSize];
int front,rear; //定义队头队尾指针
}SqQueue;
//初始化
void InitQueue(SqQueue &sq)
{
sq.rear=sq.front=0; //指针初始化
}
//销毁
void DestroyQueue(SqQueue sq)
{
}
//进栈
int EnQueue(SqQueue &sq,ElemType x)
{
if((sq.rear+1)%MaxSize==sq.front) //判断队满情况
return 0;
sq.rear=(sq.rear+1)%MaxSize; //从队尾插入，进1
sq.data[sq.rear]=x;
return 1;
}
//出队
int DeQueue(SqQueue &sq,ElemType &x)
{
if(sq.rear==sq.front) //判断队空
return 0;
sq.front=(sq.front+1)%MaxSize; //队头循环进1
x=sq.data[sq.front];
return 1;
}
int GetHead(SqQueue sq,ElemType &x)
{
if(sq.rear==sq.front) //队空情况
return 0;
x=sq.data[(sq.front+1)%MaxSize];
return 1;
}
//判断队空
int QueueEmpty(SqQueue sq)
{
if(sq.rear==sq.front)
return 1;
else return 0;
}
void main()
{
SqQueue sq;
ElemType e;
printf("初始化队列\n");
InitQueue(sq);
printf("队%s\n",(QueueEmpty(sq)==1 ? "空":"不空"));
printf("a进队\n");
EnQueue(sq,'a');
printf("b进队\n");
EnQueue(sq,'b');
printf("c进队\n");
EnQueue(sq,'c');
printf("d进队\n");
EnQueue(sq,'d');
printf("e进队\n");
EnQueue(sq,'e');
printf("f进队\n");
EnQueue(sq,'f');
printf("队%s\n",(QueueEmpty(sq)==1 ? "空":"不空"));
GetHead(sq,e);
printf("队头元素:%c\n",e);
printf("出队次序:");
while(!QueueEmpty(sq))
{
DeQueue(sq,e);
printf("%c",e);
}
printf("\n");
DestroyQueue(sq);
}
（2）结果演示
三、链队
1、链队定义
采用链式存储的队列称为链队。含有单链表的基本特性。
2、链队四要素
（1）队空条件： st->front ==NULL.
（2）队满：不考虑
（3）进队操作：创建结点p，将其插入到队尾，并由st->rear指向它。
（4）出队操作：删除队头结点。
3、链队基本运算
（1）代码部分
#include <stdio.h>
#include <malloc.h>
#include<string.h>
typedef ElemType;
//数据结点类型声明
typedef struct QNode
{
ElemType data;
struct QNode *next;
}QType;
//链队的数据类型结点声明
typedef struct qptr
{
QType *front; //队头指针
QType *rear; //队尾指针
}LinkQueue; //链队结点类型
//初始化
void InitQueue(LinkQueue *&st)
{
st=(LinkQueue *)malloc(sizeof(LinkQueue));
st->rear=st->front=NULL; //初始化，队头和队尾指针均为空
}
//销毁
void DestroyQueue(LinkQueue *&st)
{
QType *p1=st->front,*p;
if(p1!=NULL) //队不为空时
{
if(p1==st->rear) //只有一个数据结点的情况
free(p1); //释放p1结点
else //有两个或多个数据结点的情况
{
p=p1->next;
while(p!=NULL)
{
free(p1); //释放p1结点
p1=p;
p=p->next;
}
free(p1);
}
}
free(st); //释放链队结点
}
//进队
int EnQueue(LinkQueue *&st,ElemType x)
{
QType *s;
s=(QType *)malloc(sizeof(QType)); //创建新结点s，
s->data=x;
s->next=NULL;
if(st->front==NULL)
st->rear=st->front=s;
else
{
st->rear->next=s;
st->rear=s;
}
return 1;
}
//出队
int DeQueue(LinkQueue *&st,ElemType &x)
{
QType *p;
if(st->front ==NULL) //空队的情况
return 0;
p=st->front;
x=p->data;
if(st->rear==st->front) //取队头元素
{
st->rear=st->front=NULL;
}else
{
st->front=st->front->next;
}
free(p);
return 1;
}
//取队头元素计算
int GetHead(LinkQueue *st,ElemType &x)
{
if(st->front==NULL)
return 0;
x=st->front->data;
return 1;
}
//判断是否队空
int QueueEmpty(LinkQueue *st)
{
if(st->front==NULL)
return 1;
else
return 0;
}
void main()
{
LinkQueue *st;
ElemType e;
printf("初始化队列\n");
InitQueue(st);
printf("队%s\n",(QueueEmpty(st)==1 ? "空":"不空"));
printf("a进队\n");
EnQueue(st,'a');
printf("b进队\n");
EnQueue(st,'b');
printf("c进队\n");
EnQueue(st,'c');
printf("d进队\n");
EnQueue(st,'d');
printf("e进队\n");
EnQueue(st,'e');
printf("f进队\n");
EnQueue(st,'f');
printf("队%s\n",(QueueEmpty(st)==1 ? "空":"不空"));
GetHead(st,e);
printf("队头元素:%c\n",e);
printf("出队次序:");
while(!QueueEmpty(st))
{
DeQueue(st,e);
printf("%c",e);
}
printf("\n");
DestroyQueue(st);
}（3）结果演示
四、总结
顺序队和链队比较，链表可以实时申请空间，不考虑空间利用问题，因此比顺序队有一定的优势。