循环队列算法ppt

① 数据结构与算法06——队列之循环队列

与栈不同，他就是现实中排队一样，讲究先来后到，即 先进先出 。

打个比方，你告诉朋友我们做地铁去西湖，你输入 " s-u-b ", 如果按照栈 先入后出后入先出 的方式，朋友会收到 b-u-s , what？有地铁，我们干嘛做两个小时的汽车？？？ 队列就可以让朋友按你输入的顺序依次收到 s-u-b 。

简单的看一下队列，是线性结构，想到什么？非常熟悉的 线性表 ，有两种存储结构， 顺序存储和链式存储 。
我们今天先讲一讲队列的顺序存储结构—— 循环队列

但是，，，如果如下图，出队到只剩最后一个元素，front和rear又都指向了一个同元素，而且仅在队尾，又要认为队列为空？不可能啊，明明最后一块存储单元还有一个元素，而且却不能继续入队新元素，超出了存储范围，如果要继续利用前面出队的空余空间，又该怎么用？

如果 我们把队列设计成下面这样：

哈哈，循环了。队尾rear指向下一个位置，而不是当前的队尾元素。

这就是循环队列的工作流程

将上面的过程做一下整理：

指定队列最大存储5个单元，方便观看

② 求循环队列的元素个数算法，已知front 和 rear，还有容量数，怎么求队列中的循环元素个数

如果是用数组实现的 用队尾减队头再模数组长度；如果是链表 就要有个计数变量了。

front为对头指针，rear为对尾指针，n为队列最大元素个数。队列元素个数=(rear-front+1+n)%n %是求余数。

循环队列的元素个数计算公式：

如果rear<front结果是rear-front+maxsize；

如果rear>front结果是rear-front；

为了用一个表达式同时表达两者，用(rear-front+maxsize)%maxsize；

假设maxsize=10；

rear=1 front=9，那么结果是2；

rear=9 front=1，那么结果是8。

(2)循环队列算法ppt扩展阅读

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。

解决这个问题的方法至少有两种：

① 另设一布尔变量以区别队列的空和满；

②另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。

队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。

③ 在循环队列中怎样实现入队和出队操作 数据结构 C语言

入队操作
功能：将元素 x 插入到Q的队尾。
算法：Status EnQueue(SqQueue &Q, QElemType e) {
if ((Q.rear+1) % MaxQsize == Q.front) return ERROR; // 队列满
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1) % MaxQsize;
return OK;
}
出队操作
功能：删除Q的队头元素，并返回其值。
算法： Status DeQueue(SqQueue &Q, QElemType &e) {
if (Q.front == Q. rear) return ERROR; // 队列空
e = Q.base[Q.front];
Q.front=(Q.front+1) % MaxQsize;
return OK;
}

④ 数据结构—队列

队列 (queue)是一种先进先出的线性表。它只允许在表的一端进行插入，在另一端进行删除，这如同我们日常生活中的排列是一致的，最早入队的元素最早离开。

队尾 (rear)是队列中允许插入的一端， 队头 (front)是队列中允许删除的一端。

队列如同栈一样，也同样有两种存储表示，分别是顺序表示和链式表示。

和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到对列尾的元素之外，需要设置两个指针front和rear分别指示队列头元素和尾元素的位置。

队列的顺序存储结构表示如下：

为方便C语言描述起见，约定：初始化建空队列时，front=rear=0,每当插入新元素至队尾时，“尾指针增一”，每当删除头元素时，“头指针增一”。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队尾元素的下一个位置。

循环对列 是将顺序队列变成一个环状的空间，用这种方法可以解决队列“假溢出”问题。

“假溢出” 是指队列实际可用空间没有占满，但是不能向队列中添加新的队尾元素，否则会出现溢出的现象的情况。

在循环队列中，头尾指针以及队列元素之间的关系不发生改变，只是在循环队列中头尾指针“依次循环增一”的操作可用模运算实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

循环队列的基本操作算法描述：

链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，一个链队显然需要两个分别指示对头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。为了操作方便，同线性表的单链表一样，为链队添加头结点，并规定头指针始终指向头结点。

链队列存储结构表示如下：

链队操作即为单链表插入和删除操作的特殊情况，只是需要进一步修改尾指针或头指针。

链队列的基本操作算法描述：

⑤ 队列的队列的基本运算

（1）初始化队列：Init_Queue(q) ，初始条件：队q 不存在。操作结果：构造了一个空队；
（2）入队操作： In_Queue(q,x),初始条件： 队q 存在。操作结果： 对已存在的队列q，插入一个元素x 到队尾，队发生变化；
（3）出队操作： Out_Queue(q,x)，初始条件: 队q 存在且非空，操作结果： 删除队首元素，并返回其值，队发生变化；
（4）读队头元素：Front_Queue(q,x)，初始条件: 队q 存在且非空，操作结果： 读队头元素，并返回其值，队不变；
（5）判队空操作：Empty_Queue(q)，初始条件： 队q 存在，操作结果： 若q 为空队则返回为1，否则返回为0。 操作 类型 作用 返回值 例子 length(s) 函数 求字符串s的长度 整型 s:='123456789';
l:=length(s);{l的值为9} （s,w,k) 函数 复制s中从w开始的k位 字符串 s:='123456789';
s1:=(s,3,5);{s1的值是'34567'} val(s,k,code) 过程 将字符串s转为数值，存在k中；code是错误代码 var s:string;k,code:integer;
begin
s:='1234';
val(s,k,code);
write(k);{k=1234} str(i,s) 过程 将数值i转为字符串s i:=1234;
str(i,s);
write(s);{s='1234'} Delete(s,w,k) 过程 在s中删除从第w位开始的k个字符 s := 'Honest Abe Lincoln';
Delete(s,8,4);
Writeln(s); { 'Honest Lincoln' } Insert(s1, S, w) 过程 将s1插到s中第w位 S := 'Honest Lincoln';
Insert('Abe ', S, 8); { 'Honest Abe Lincoln' } Pos(c, S) 函数 求字符c在s中的位置 整型 S := ' 123.5';
i :=Pos(' ', S);{i的值为1} + 运算符 将两个字符串连接起来 s1:='1234';
s2:='5678';
s:=s1+s2;{'12345678'} 在STL中，对队列的使用很是较完美
下面给出循环队列的运算算法:
(1)将循环队列置为空
//将队列初始化
SeQueue::SeQueue()
{ front=0;
rear=0;
cout<<init!<<endl;
}
(2)判断循环队列是否为空
int SeQueue::Empty()
{ if(rear==front) return(1);
else return(0);
}
(3)在循环队列中插入新的元素x
void SeQueue::AddQ(ElemType x)
{ if((rear+1) % MAXSIZE==front) cout<< QUEUE IS FULL! <<endl;
else{ rear=(rear+1) % MAXSIZE;
elem[rear]=x;
cout<< OK!;
}
}
(4)删除队列中队首元素
ElemType SeQueue::DelQ()
{ if(front==rear)
{ cout<< QUEUE IS EMPTY! <<endl; return -1;}
else{ front=(front+1) % MAXSIZE;
return(elem[front]);
}
}
(5)取队列中的队首元素
ElemType SeQueue::Front()
{ ElemType x;
if(front== rear)
cout<<QUEUE IS EMPTY <<endl;
else x= elem[(front+1)%MAXSIZE];
return (x);
}

⑥ 循环队列中入队与出队算法

如果循环队列每个元素有两个指针，一个指向其前面的元素pPre，一个指向后面的元素pNext，出对和入队就是修改一下指针啊。
比如指向要出队的元素的指针是 pDel,那么出队就应该是：
pDel->pPre->pNext = pDel->pNext;
pDel->pNext->pPre = pDel->pPre;

如果循环队列每个元素只有一个指向其后元素的指针pNext，那么需要遍历整个队列，找到要出队元素的前一个元素，然后就和上面的算法差不多了。

如果经常要进行出队操作，在设计数据结构的时候还是建议每个元素使用两个指针。