目录
一、队列是什么？
队列是只允许在一端进行的插入操作，而在另一端进行删除操作的线性表
二、循环队列
1.知识点概述
队列的顺序存储形式，可以用一段连续的空间存储数据元素，用两个整型变量记录队头和队尾元素的下标。
2.动态分配
3.初始化
//循环队列的初始化 bool InitQueue(SqQueue &Q)//注意使用引用参数，否则出了函数，其改变无效 { Q.base=new int[Maxsize];//分配空间 if(!Q.base) return false; Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空 return true; }
4.入队
由于对头进行删除，对尾进行增加持续的增加会导致数组的末尾没有空间，但是数组前面由于进行了删除操作会导致，前面有空余的位置，这种现象叫“假溢出”
可以进行以下操作
//循环队列的入队 bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾 { if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满 return false; Q.base[Q.rear]=e; //新元素插入队尾 Q.rear=(Q.rear+1)%Maxsize; //队尾指针加1 return true; }
5.出队
代码如下
//循环队列的出队 bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素，用e返回其值 { if (Q.front==Q.rear) return false; //队空 e=Q.base[Q.front]; //保存队头元素 Q.front=(Q.front+1)%Maxsize; //队头指针加1 return true; }
6. 取对头元素
代码如下
//取循环队列的队头元素 int GetHead(SqQueue Q)//返回Q的队头元素，不修改队头指针 { if (Q.front!=Q.rear) //队列非空 return Q.base[Q.front]; return -1; }
7.取队列长度
代码如下
//循环队列的长度 int QueueLength(SqQueue Q) { return (Q.rear-Q.front+Maxsize)%Maxsize; }
8.总的代码
代码如下
#include <iostream> using namespace std; #define Maxsize 100 typedef struct SqQueue{ int *base; //基地址 int front,rear; //头指针,尾指针 }SqQueue; //循环队列的初始化 bool InitQueue(SqQueue &Q)//注意使用引用参数，否则出了函数，其改变无效 { Q.base=new int[Maxsize];//分配空间 if(!Q.base) return false; Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空 return true; } //循环队列的入队 bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾 { if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满 return false; Q.base[Q.rear]=e; //新元素插入队尾 Q.rear=(Q.rear+1)%Maxsize; //队尾指针加1 return true; } //循环队列的出队 bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素，用e返回其值 { if (Q.front==Q.rear) return false; //队空 e=Q.base[Q.front]; //保存队头元素 Q.front=(Q.front+1)%Maxsize; //队头指针加1 return true; } //取循环队列的队头元素 int GetHead(SqQueue Q)//返回Q的队头元素，不修改队头指针 { if (Q.front!=Q.rear) //队列非空 return Q.base[Q.front]; return -1; } //循环队列的长度 int QueueLength(SqQueue Q) { return (Q.rear-Q.front+Maxsize)%Maxsize; } int main() { SqQueue Q; int n,x; InitQueue(Q);//初始化队列(一定要初始化，否则后面存储出错) cout <<"请输入元素个数n：" <<endl; cin>>n; cout <<"请依次输入n个整型数，依次入队：" <<endl; while(n--) { cin>>x; EnQueue(Q,x);//入队 } cout<<endl; cout <<"队列内元素个数，即长度："<<QueueLength(Q)<<endl; cout <<"队头元素：" <<GetHead(Q)<<endl; cout <<"元素依次出队：" <<endl; while(true)//如果栈不空，则依次出栈 { if(DeQueue(Q,x)) cout<<x<<"\t";//出队元素 else break; } cout <<endl; cout <<"队列内元素个数，即长度："<<QueueLength(Q)<<endl; return 0; }
三 、链式链表
1.链队列的结构
typedef int ElemType; //ElemType 根据实际情况而定，这里假定为int型 typedef struct LinkNode{ //结点结构 ElemType data; struct LinkNode *next; }LinkNode; typedef struct LinkQueue { //队列的链式结构 LinkNode *front, *rear; //对头,对尾指针 }LinkQueue
2.链队列入队
void EnQueue(LinkQueue &Q, ElemType e) { LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode)); s->data = e; s->next = NULL; Q.rear->next = s; //把拥有元素e新结点s赋值给原对尾结点的后继 Q.rear = s; //把当前s结点设为队尾结点，rear指向s }
