目录

一、队列

1、队列概念

2、队列的特征

3、队列存储结构

二、顺序队

1、顺序队定义

2、循环队列的四要素

3、循环队列的基本运算算法

（1）代码展示

（2）结果演示

三、链队

1、链队定义

2、链队四要素

3、链队基本运算

（1）代码部分

（3）结果演示

四、总结

一、队列

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 #includetypedef char ElemType;#define MaxSize 200typedef 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;    //从队尾插入，进1sq.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;   //队头循环进1x=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 #include #includetypedef 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;elsereturn 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）结果演示

四、总结

顺序队和链队比较，链表可以实时申请空间，不考虑空间利用问题，因此比顺序队有一定的优势。
 

丽江小吃城