队列的基本概念详解，循环队列、链式队列的C++详细实现
【摘要】 提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档目录一、队列是什么？二、循环队列1.知识点概述 2.动态分配 3.初始化4.入队 5.出队 6. 取对头元素7.取队列长度 8.总的代码三 、链式链表 1.链队列的结构 2.链队列入队 一、队列是什么？ 队列是只允许在一端进行的插入操作，而在另一端进行删除操作的线性表编辑二、循环队列1.知识点概述队列的顺序存储形式，可以用...
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
一、队列是什么？
队列是只允许在一端进行的插入操作，而在另一端进行删除操作的线性表
二、循环队列
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
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）