队列的基本概念详解,循环队列、链式队列的C++详细实现
2023-09-27 14:19:56 时间
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
一、队列是什么?
队列是只允许在一端进行的插入操作,而在另一端进行删除操作的线性表
二、循环队列
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
}
相关文章
- Python中的枚举对象有什么用?怎样用内置函数enumerate()得到枚举对象?Python的for循环和C++的for循环有何区别?Python中for循环的本质是什么?
- 49 C++ - 多态
- C++程序设计课程同步项目——循环结构程序设计项目任务二
- C++程序设计课程同步项目——循环结构程序设计项目任务一
- 大话游戏循环Game Loop——Python&C++
- 循环队列实现(C++) Ring Buffer
- 《C++ 开发从入门到精通》——第1章 说真的,我们还要学习C++吗1.1 C++概述
- 《C++入门经典(第5版•修订版)》——6.1 循环
- 《C++入门经典(第5版•修订版)》——6.3 do-while循环
- 《C++ AMP:用Visual C++加速大规模并行计算》——3.8 在CPU和GPU之间复制数据
- 基于C++数据结构双向循环链表实现的贪吃蛇【100010175】
- C/C++中作用域详解
- C++:类(一)—— 基本概念
- 44、【树和二叉树】Trie(前缀树/搜索树)字符串统计(C/C++版)
- C++实现【通讯录】管理系统
- c++继承总结
- effective c++ 条款7
- C++11 基于范围的for循环
- C++中模块(Dll)对外暴露接口的方式