提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
目录
队列是只允许在一端进行的插入操作,而在另一端进行删除操作的线性表
队列的顺序存储形式,可以用一段连续的空间存储数据元素,用两个整型变量记录队头和队尾元素的下标。
//循环队列的初始化
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;
}
代码如下
#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;
}
typedef int ElemType; //ElemType 根据实际情况而定,这里假定为int型
typedef struct LinkNode{ //结点结构
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct LinkQueue { //队列的链式结构
LinkNode *front, *rear; //对头,对尾指针
}LinkQueue
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
}