循环队列的实现与运算

1.算法一般都可以用哪几种控制结构组合而成？答案：顺序、选择、循环。

2. 在下列选项中，哪个不是一个算法一般应该具有的基本特征？说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。

答案：无穷性。

3. 在计算机中，算法是指什么？答案：解题方案的准确而完整的描述。

4. 算法的时间复杂度是指？答案：算法执行过程中所需要的基本运算次数。

5. 算法的空间复杂度是指？答案：执行过程中所需要的存储空间。

6. 算法分析的目的是？答案：分析算法的效率以求改进。

7. 下列叙述正确的是（C）A．算法的执行效率与数据的存储结构无关B．算法的空间复杂度是指算法程序中指令（或语句）的条数C．算法的有穷性是指算法必须能在执行有限个步骤之后终止D．算法的时间复杂度是指执行算法程序所需要的时间8. 数据结构作为计算机的一门学科，主要研究什么？答案：主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构。

9. 数据结构中与所使用的计算机无关的是数据的（C）A．存储结构B．物理结构C．逻辑结构D．物理和存储结构10. 下列叙述中，错误的是（B）A．数据的存储结构与数据处理的效率密切相关B．数据的存储结构与数据处理的效率无关C．数据的存储结构在计算机中所占的空间不一定是连续的D．一种数据的逻辑结构可以有多种存储结构11. 数据的存储结构是指什么？答案：数据的逻辑结构在计算机中的表示。

12. 数据的逻辑结构是指？答案：反映数据元素之间逻辑关系的数据结构。

13. 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为？答案：线性结构和非线性结构。

14. 下列数据结构具有记忆功能的是（C）A．队列B．循环队列C．栈D．顺序表15. 下列数据结构中，按先进后出原则组织数据的是（B）A．线性链表B．栈C．循环链表D．顺序表16. 递归算法一般需要利用什么实现？答案：队列17. 下列关于栈的叙述中正确的是（D）A．在栈中只能插入数据B．在栈中只能删除数据C．栈是先进先出的线性表D．栈是先进后出的线性表18. 由两个栈共享一个存储空间的好处是？答案：节省存储空间，降低上溢发生的机率。

解忧书店 JieYouBookshop第二章单元测试1、(1分)以下哪种结构是逻辑结构，而与存储和运算无关：Which of the following structure is a logical structure regardless of the storage or algorithm:（There is only one correct answer）A、队列(queue)B、双链表(doubly linked list)C、数组(array)D、顺序表(Sequential list)答案： A2、(1分)计算运行下列程序段后m的值：Calculate the value of m after running the following program segmentn = 9; m = 0;for (i=1;i<=n;i++)for (j = 2*i; j<=n; j++)m=m+1;求m的值答案： 203、(1分)下列说法正确的是：Which options may be correct?（there are more than one correct answers）A、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)是O(h(n))【 if f(n) is O(g(n))，g(n) is O(h(n))，then f(n) is O(h(n))】B、如果函数f(n)是O(g(n))，g(n)是O(h(n))，那么f(n)+g(n)是O(h(n))【if f(n) is O(g(n))，g(n) is O(h(n))，so f(n)+g(n) is O(h(n))】C、如果a>b>1,logan是O(logbn)，但logbn不一定是O(logan)【if a>b>1,logan is O(logbn)，logbn may not be O(logan)】D、函数f(n)是O(g(n))，当常数a足够大时，一定有函数g(n)是O(af(n))【if f(n)是O(g(n))，When constant a is big enough ，there must be g(n) is O(af(n))】答案： A,B4、(1分)由大到小写出以下时间复杂度的序列：答案直接写标号，如：(1)(2)(3)(4)(5) （提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Write the following time complexity in descending sequence:Write down the answer labels such as (1)(2)(3)(4)(5). （Hint：This problem is judged by string matching, Please make sure your answer don't contain any blanks. ）RUX4%GXZNDD{IAQWTCSEEJG.png答案： (5)(1)(2)(4)(3)5、(1分)已知一个数组a的长度为n，求问下面这段代码的时间复杂度:An array of a, its length is known as n. Please answer the time complexity of the following code.（There are more than one answers.）for (i=0,length=1;i<n-1;i++){for (j = i+1;j<n && a[j-1]<=a[j];j++)if(length<j-i+1)length=j-i+1;}Screen Shot 2017-09-05 at 23.31.19.pngA、如图，A选项B、如图，B选项C、如图，C选项D、如图，D选项答案： A,B第三章单元测试1、(1分)下面关于线性表的叙述中，正确的是哪些？Which of the followings about linear list are correct?（There are more than one answers.）Select the answer that matchesA、线性表采用顺序存储，必须占用一片连续的存储单元。

DS博客作业02--栈和队列0.PTA得分截图1.本周学习总结（0-4分）1.1 总结栈和队列内容⼀.栈栈的定义栈是⼀种只能在⼀端进⾏插⼊或删除操作的线性表，俗称：后进先出。

表中允许进⾏插⼊、删除操作的⼀端称为栈顶。

栈的进栈出栈规则：1.栈顶出栈->栈底最后出栈；2.时进时出->元素未完全进栈时，即可出栈。

栈的分类：1.顺序栈利⽤⼀组地址连续的存储单元依次存放⾃栈底到栈顶的数据元素，同时附设指针 top 指⽰栈顶元素在顺序栈中的位置，附设指针 base 指⽰栈底的位置。

同样，应该采⽤可以动态增长存储容量的结构。

如果栈已经空了，再继续出栈操作，则发⽣元素下溢，如果栈满了，再继续⼊栈操作，则发⽣元素上溢。

栈底指针 base 初始为空，说明栈不存在，栈顶指针 top 初始指向 base，则说明栈空，元素⼊栈，则 top++，元素出栈，则 top--，故，栈顶指针指⽰的位置其实是栈顶元素的下⼀位（不是栈顶元素的位置）。

2.链栈其实就是链表的特殊情形，⼀个链表，带头结点，栈顶在表头，插⼊和删除（出栈和⼊栈）都在表头进⾏，也就是头插法建表和头删除元素的算法。

显然，链栈插⼊删除的效率较⾼，且能共享存储空间。

栈的基本运算InitStack(&s)：初始化栈。

构造⼀个空栈s。

DestroyStack(&s)：销毁栈。

释放栈s占⽤的存储空间。

StackEmpty(s)：判断栈是否为空:若栈s为空，则返回真；否则返回假。

Push(&S，e)：进栈。

将元素e插⼊到栈s中作为栈顶元素。

Pop(&s，&e)：出栈。

从栈s中退出栈顶元素，并将其值赋给e。

GetTop(s，&e)：取栈顶元素。

返回当前的栈顶元素，并将其值赋给e。

顺序栈的功能操作代码实现1.图像表⽰2.结构体定义typedef struct{ ElemType data[MaxSize]；int top； //栈顶指针} Stack；typedef Stack *SqStack;3.基本运算<1>初始化栈initStack(&s)void InitStack(SqStack &s){ s=new Stack;s->top=-1;}<2>销毁栈ClearStack(&s)void DestroyStack(SqStack &s){ delete s;}<3>判断栈是否为空StackEmpty(s) bool StackEmpty(SqStack s){ return(s->top==-1);}<4>进栈Push(&s,e)bool Push(SqStack &s,ElemType e){ if (s->top==MaxSize-1)return false;s->top++; //栈顶指针增1s->data[s->top]=e;return true;}<5>出栈Pop(&s,&e)bool Pop(SqStack &s,ElemType &e){if (s->top==-1) //栈为空的情况，栈下溢出 return false;e=s->data[s->top];//取栈顶指针元素s->top--; //栈顶指针减1return true;}<6>取栈顶元素GetTop(s)bool GetTop(SqStack *s,ElemType &e) { if (s->top==-1) //栈为空的情况return false;e=s->data[s->top];return true;}4.顺序栈的四要素栈空条件：top=-1栈满条件：top=MaxSize-1进栈e操作：top++; st->data[top]=e 退栈操作：e=st->data[top]; top--;链栈的功能操作代码实现1.图像表⽰2.结构体定义typedef int ElemType;typedef struct linknode{ ElemType data; //数据域struct linknode *next; //指针域} LiNode,*LiStack3.基本运算<1>初始化栈initStack(&s)void InitStack(LiStack &s){ s=new LiNode;s->next=NULL;}<2>销毁栈ClearStack(&s)void DestroyStack(LiStack &s){　LiStack p;while (s!=NULL){ p=s;s=s->next;free(p);}}<3>判断栈是否为空StackEmpty(s)bool StackEmpty(LiStack s){return(s->next==NULL);}<4>进栈Push(&s,e)void Push(LiStack &s,ElemType e){ LiStack p;p=new LiNode;p->data=e; //新建元素e对应的节点*pp->next=s->next; //插⼊*p节点作为开始节点s->next=p;}<5>出栈Pop(&s,&e)bool Pop(LiStack &s,ElemType &e){ LiStack p;if (s->next==NULL) //栈空的情况return false;p=s->next; //p指向开始节点e=p->data;s->next=p->next; //删除*p节点free(p); //释放*p节点return true;}<6>取栈顶元素GetTop(s,e)bool GetTop(LiStack s,ElemType &e){ if (s->next==NULL) //栈空的情况return false;e=s->next->data;return true;}4.链栈的四要素栈空条件：s->next=NULL栈满条件：不考虑进栈e操作：结点插⼊到头结点后，链表头插法退栈操作：取出头结点之后结点的元素并删除之对于栈的C++模板类：stack#include<stack>1.stack<int> s:初始化栈，参数表⽰元素类型2.s.push(t):⼊栈元素t3.s.top()：返回栈顶元素4.s.pop()：出栈操作只是删除栈顶元素，并不返回该元素。

实现循环队列的入队出队等基本操作循环队列是一种特殊的队列数据结构，通过循环利用数组空间来实现入队和出队操作。

它的特点是队头和队尾可以在数组上循环移动，从而充分利用数组空间，提高队列的效率。

下面将详细介绍循环队列的实现。

1.定义循环队列的数据结构循环队列的数据结构由以下几个成员组成：-一个固定大小的数组，用于存储队列元素。

- 一个队头指针front，指向队列的第一个元素。

- 一个队尾指针rear，指向队列的最后一个元素的下一个位置。

2.初始化循环队列首先，我们需要在内存中分配一个固定大小的数组，并初始化队头和队尾指针为0。

```pythondef __init__(self, k: int):self.queue = [0] * kself.front = self.rear = 0```3.入队操作入队操作会在队尾插入一个新元素，并将队尾指针后移一位。

如果队列已满，则入队操作会失败。

```pythondef enqueue(self, value: int) -> bool:if self.isFull(:return Falseself.queue[self.rear] = valueself.rear = (self.rear + 1) % len(self.queue)return True```4.出队操作出队操作会删除队头元素，并将队头指针后移一位。

如果队列为空，则出队操作会失败。

```pythondef dequeue(self) -> bool:if self.isEmpty(:return Falseself.front = (self.front + 1) % len(self.queue)return True```5.判空操作判空操作会检查队头和队尾指针是否相等，如果相等则说明队列为空。

```pythondef isEmpty(self) -> bool:return self.front == self.rear```6.判满操作判满操作会检查队尾指针的下一位是否等于队头指针，如果相等则说明队列已满。

循环队列实现杨辉三⾓形的打印知识温习循环队列：即将顺序队列的数组看成是⼀个环状的空间，规定最后⼀个单元的后继为第⼀个单元。

运⽤循环队列可以有效的解决链队列的“假溢出”现象。

假溢出其实是指在链队列中，当rear==MAXSIZE时就认为队满。

然⽽由于元素的出队，使得数组前⾯出现⼀些空单元，⽽元素⼜只能在队尾⼊队，如果此时已经到数组的尾部，就认为队列已满，但其实还存在上述那些空单元未使⽤，队列并未真正满。

这种现象即为“假溢出”现象。

真正的队满条件应该是rear-front==MAXSIZE。

在循环队列中，我们通过数学中的求模运算来改变头指针和尾指针的位置。

进队操作时，队尾指针的变化是：rear=（rear+1）mod MAXSIZE；⽽出队操作时，队头指针的变化是：front=（front+1）mod MAXSIE。

杨辉三⾓形11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1从上图中可以看出，杨辉三⾓形的特点：每⾏的第⼀个元素和最后⼀个元素都为1，其他位置上的元素总是等于上⼀⾏与之相邻的两个元素之和。

故第i⾏的元素要由第i-1⾏的元素来⽣成。

可以利⽤循环队列实现杨辉三⾓形的打印过程：在循环队列中依次存放第i-1⾏上的元素，然后逐个出队并打印，同时⽣成第i⾏元素并⼊队。

下⾯⽤第6⾏元素⽣成第7⾏元素为例⼦来说明打印过程：①第7⾏的第⼀个元素1⼊队。

element[Q->rear] = 1;Q->rear = (Q->rear + 1)% MAXSIZE;②循环做以下操作，⽣成第7⾏的中间5个元素并⼊队。

element[Q->rear] = element[Q->front] + element[(Q->front+1)%MAXSIZE];Q->rear = (Q->rear + 1)%MAXSIZE;Q->front = (Q->front + 1)%MAXSIZE;③第6⾏的最后⼀个元素1⼊队。

实验二栈与队列操作实验题目实验二栈与队列操作实验目的：(1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。

(2)了解复杂问题的递归算法设计。

本次实验中，下列实验项目选做一。

1、顺序栈的基本操作[问题描述]设计算法，实现顺序栈的各种基本操作[基本要求]（1）初始化栈s。

（2）从键盘输入10个字符以$结束，建立顺序栈。

（3）从键盘输入1个元素，执行入栈操作。

（4）将栈顶元素出栈。

（5）判断栈是否为空。

（6）输出从栈顶到栈底元素。

要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

2、链栈的基本操作[问题描述]设计算法，实现链栈的各种基本操作[基本要求]（1）初始化栈s。

（2）从键盘输入10个字符以$结束，建立带头结点的链栈。

（3）从键盘输入1个元素，执行入栈操作。

（4）完成出栈操作。

（5）判断栈是否为空。

（6）输出从栈顶到栈底元素。

（7）输出链栈的长度。

要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

3、循环队列的基本操作[问题描述]设计算法，实现循环顺序队列的建立、入队、出队等操作。

[基本要求]（1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。

（2）从键盘输入1个元素，执行入队操作，并显示结果。

（3）将队头元素出队，并显示结果。

（4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。

4、只用尾指针表示的循环链表队列的综合操作[问题描述]假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。

[基本要求及提示]（1）首先定义链表结点类型。

（2）编写带头结点的循环链表的初始化函数，只用尾指针表示。

（3）编写入队函数、出队函数。

（4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。

循环队列push_back实现原理循环队列是一种经典的数据结构，它可以实现高效的队列操作。

在循环队列中，我们可以使用push_back操作来向队列尾部插入新的元素。

本文将介绍循环队列的原理，并详细解释push_back操作的实现过程。

一、循环队列的概念和原理循环队列是一种环形的数据结构，它的底层是一个数组。

循环队列的特点是，当队列的尾部指针指向数组的最后一个位置时，如果队列仍有空闲空间，那么新的元素将被插入到数组的第一个位置，形成一个循环。

这样一来，我们就可以循环利用数组的空间，避免了数组中元素的搬移操作。

循环队列通常由两个指针来表示，一个是队头指针front，一个是队尾指针rear。

初始时，它们都指向数组的第一个位置。

队列中的元素从队头指针的位置开始，依次向后排列，直到队尾指针的位置。

当队列为空时，front和rear指针相等，当队列满时，rear指针指向的位置是front指针的前一个位置。

二、push_back操作的实现过程push_back操作是向循环队列的尾部插入新的元素。

它的具体实现过程如下：1. 首先，判断队列是否已满。

如果队列已满，即rear指针的下一个位置是front指针的位置，表示队列已满，无法插入新的元素。

在这种情况下，我们可以选择两种处理方式：一种是抛出异常，通知调用者队列已满；另一种是自动扩容，重新分配更大的数组空间。

这里我们选择抛出异常的方式。

2. 如果队列未满，将新的元素插入到rear指针的位置，并将rear 指针后移一位。

具体操作如下：（1）将新的元素赋值给rear指针指向的位置：queue[rear] = element；（2）将rear指针后移一位：rear = (rear + 1) % queueSize；这里使用取模运算来实现循环。

3. 返回插入成功的提示信息。

三、总结本文介绍了循环队列的概念和原理，并详细解释了push_back操作的实现过程。

循环队列通过循环利用数组的空间，实现了高效的队列操作。

循环队列中元素个数的计算1 循环队列的概念循环队列是一种特殊的队列，它的存储结构是通过数组实现的。

与普通队列不同的是，循环队列的队尾指针可以在数组末尾与队头指针相连，形成环的结构。

循环队列的出队操作和普通队列类似，都是从队头取出元素。

但是入队操作稍有不同，由于队尾指针是可循环的，所以当队列已满时，可以将队尾指针指向数组开头，从而使队列形成循环。

2 循环队列中元素个数的计算方法循环队列中元素个数的计算方法比较简单，只需要用队尾指针减去队头指针即可。

但是需要注意的是，当队尾指针小于队头指针时，需要加上数组长度才能得到正确结果。

如图所示，假设循环队列的长度为n，队头指针为front，队尾指针为rear，队列中元素个数为size。

则元素个数的计算方法如下：```size = (rear - front + n) % n```其中，`%` 是取模运算符，前面做完减法之后再加上n，就相当于在队尾指针小于队头指针时，将它们调整到正确的位置。

计算出元素个数后，可以用它来判断队列是否已满或已空。

3 如何利用元素个数优化循环队列的实现通过元素个数的计算方法，可以知道当前队列中的元素个数，进而判断队列是否已满或已空。

为了使循环队列的实现更加高效，可以在队列的结构体中加入一个存储元素个数的字段，每次入队或出队时更新它的值即可。

以入队操作为例，具体实现方法如下：```bool enqueue(CircularQueue *queue, int element) {if (isFull(queue)) {return false;}queue->data[queue->rear] = element;queue->rear = (queue->rear + 1) % queue->capacity; // 更新队尾指针queue->size++; // 更新元素个数return true;}```出队操作的实现也类似，只需要把队尾指针和元素个数都减1即可。

实现循环队列上各种基本运算的算法循环队列是一种特殊的队列，它的底层实现是通过数组来存储数据，并通过两个指针(front指针和rear指针)来确定队头和队尾的位置。

循环队列的特点是：队满和队空的判定条件相同，即队头指针与队尾指针相邻时，队列为满；队头指针与队尾指针相等时，队列为空。

循环队列的基本运算包括：初始化队列、入队操作、出队操作、获取队头元素、获取队列长度、判定队空和队满。

1. 初始化队列初始化循环队列需要创建一个指定大小的数组，并将前后指针(front和rear)都指向数组的起始位置。

代码如下：```pythondef init_queue(size):return [None] * size, 0, 0```2. 入队操作入队操作主要涉及向队尾添加元素，并同时更新rear指针。

如果队列已满，则无法添加元素。

代码如下：```pythondef enqueue(queue, item):size, front, rear = queueif (rear + 1) % size == front:print("Queue is full")queue[rear] = itemqueue[2] = (rear + 1) % size```3. 出队操作出队操作主要涉及从队头移除元素，并同时更新front指针。

如果队列为空，则无法进行出队操作。

代码如下：```pythondef dequeue(queue):size, front, rear = queueif front == rear:print("Queue is empty")else:item = queue[front]queue[front] = Nonequeue[1] = (front + 1) % sizereturn item```4. 获取队头元素获取队头元素操作是指返回队列中第一个元素的值，但不移除元素。

算法与数据结构C语⾔版课后习题答案（机械⼯业出版社）第3,4章习题参考答案第3章栈和队列⼀、基础知识题3.1有五个数依次进栈：1，2，3，4，5。

在各种出栈的序列中，以3，4先出的序列有哪⼏个。

（３在４之前出栈）。

【解答】34215 ，34251，345213.2铁路进⾏列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6，那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到(即写出"进栈"或"出栈"的序列)。

【解答】输⼊序列为123456，不能得出435612和154623。

不能得到435612的理由是，输出序列最后两元素是12，前⾯4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。

不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。

得到325641的过程如下：1 2 3顺序⼊栈，32出栈，得到部分输出序列32；然后45⼊栈，5出栈，部分输出序列变为325；接着6⼊栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。

得到135426的过程如下：1⼊栈并出栈，得到部分输出序列1；然后2和3⼊栈，3出栈，部分输出序列变为13；接着4和5⼊栈，5，4和2依次出栈，部分输出序列变为13542；最后6⼊栈并退栈，得最终结果135426。

3.3若⽤⼀个⼤⼩为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除⼀个元素，再加⼊两个元素后，rear和front的值分别为多少？【解答】2和43.4设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，⼀个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量⾄少应该是多少？【解答】43.5循环队列的优点是什么，如何判断“空”和“满”。

3.2 队列【要点提示】1.概念：队列是一种 的线性表，允许插入的一端称为队首，允许删除的一端称为 。

：在队列中插入一个元素。

：从队列中删除一个元素。

2.基本操作1）以数组实现的队列①如上图，可以设置一个头指针head 记录队首元素所在的位置，尾指针tail 记录队尾元素的下一个位置（注意不是队尾元素所在位置）。

【案例1】有4个字母“A ”“B ”“C ”“D ”按顺序入队、出队时，可以创建一个队列que ，长度为5。

head=0 tail=0que=[“”]*5【案例2】出队。

排在队首的元素依次出队，head 指针变量依次加1，直至head 值等于tail 值时，队列为空。

【思考】该队列规模为4，随着数据一个个出队，tail 已经到达索引4位置，head 递增，此时若想再入队新数据，则超出队列规模，但数组前几个已出队的位置数据已为空，这种称为假溢现象。

如何解决这个问题？que[tail] =“A ” tail+=1que[tail] =“B ” tail+=1que[tail] =“A ” tail+=1que[tail] =“B” tail+=1que[tail] =“C” tail+=1que[tail] =“D” tail+=1for i in range(4):_______________ _______________简化while ____________：print(__________) _______________2）以链表实现的队列①队列的链式存储称为。

3.循环队列若一个普通队列和一个循环队列的最大容量都为n，head指向队首元素，tail指向队尾元素的下一位置。

则关于这两种队列中数据元素的个数以及判断队列为空的条件如下：项目普通队列循环队列队列中数据元素个数tailhead (tailhead+n)%n（同样适用于普通队列）队列为空的条件tail==head4.常见队列问题的Python实现项目普通方法列表自带方法queue模块（已导入模块）建队q=[0]*nhead=0tail=0q=[] q=queue. Queue(n)判断队列是否为空head==tail len(q)=0 q.empty()入队q[tail]=“A”tail=+=1q.append(“A”) q.put(“A”)出队head+=1 a.pop(0) q.get()返回队列元素个数tailhead len(q) q.qsize()队列应用1：字符串加密给定一个字符串S1,S2,…..Sn，按如下过程加密：取出第一个字符S1，将第二个字符S2放到字符串的末尾Sn后面，得到字符串S3…..Sn,S2；接着把S3取出，S4放到字符串的末尾S2后面，直到最后一个字母Sn 被取出。

循环队列的基本操作一、实验目的1. 理解并掌握队列的逻辑结构和顺序存储结构，了解循环队列的特点；2. 掌握循环队列中基本操作的相关算法；3. 编程实现相关算法；4. 学会利用循环队列解决实际问题。

二、实验条件Visual C++。

三、实验原理及相关知识1. 循环队列存储结构描述#define MAXSIZE 100 //最大队列长度typedef struct{QElemType *base; //存储空间基址int front; //头指针int rear; //尾指针}SqQueue;2. 基本操作的算法描述设下标为index，队列长度为m，则下一个下标的累进循环计算公式为：index_next = ( index+1 ) % m。

实验中涉及的三个关键操作时循环队列中求队列长度、入队和出队操作。

(1) 求长度所谓求队列长度，即技术队列中元素的个数。

算法思想：根据循环队列的结构特征，可以用公式（Q.rear-Q.front+ MAXSIZE）%MAXSIZE 直接计算出队列的长度。

算法描述Status QueueLength(SqQueue Q){return ( ( Q.rear-Q.front+ MAXSIZE) %MAXSIZE);}//QueueLength(2) 入队入队运算实际上相当于顺序表中的插入运算，所不同的是这里只能在队尾插入元素。

算法思想：①将元素e插入循环队列中队尾元素的下一个存储空间②修改队尾指针，根据循环累计公式计算出其新位置算法描述Status EnQueue(SqQueue &Q, QElemType e){if ( ( Q.rear + 1 ) % MAXSIZE == Q.front )return ERROR; //队列满Q.base[Q.rear] = e;Q.rear = ( Q.rear + 1 ) % MAXSIZE;return OK;}// EnQueue(3) 出队出队运算实际上相当于顺序表中的删除运算，所不同的是这里只能在队头删除元素。