顺序队列的基本操作

queue的用法和样例队列（Queue）是计算机科学中常用的数据结构，具有先进先出（FIFO）的特性。

队列常用于需要按照顺序处理的场景，例如任务调度、广度优先搜索、缓冲等。

队列的基本操作：1.入队（Enqueue）：将元素添加到队列的尾部。

2.出队（Dequeue）：从队列的头部移除并返回元素。

3.查看头部元素（Front）：查看队列的头部元素，但不移除。

4.判空（isEmpty）：检查队列是否为空。

5.获取队列大小（Size）：获取队列中元素的个数。

队列的实现方式：1.数组实现：使用数组来存储队列元素，通过两个指针分别记录队列头和尾的位置。

但在动态队列中，可能需要考虑数组大小的调整。

public class ArrayQueue<T>{private static final int DEFAULT_CAPACITY =10;private Object[]array;private int front,rear,size;public ArrayQueue(){array =new Object[DEFAULT_CAPACITY];front =rear =size =0;}public void enqueue(T item){if(size ==array.length){resize();}array[rear++]=item;size++;}public T dequeue(){if(isEmpty()){throw new NoSuchElementException("Queue is empty ");}T item =(T)array[front++];size--;return item;}public T front(){if(isEmpty()){throw new NoSuchElementException("Queue is empty ");}return(T)array[front];}public boolean isEmpty(){return size ==0;}public int size(){return size;}private void resize(){int newSize =array.length*2;array =Arrays.copyOf(array,newSize);}}2.链表实现：使用链表来实现队列，每个节点包含一个元素和指向下一个节点的引用。

数据结构简答题和论述题1、试描述数据结构和抽象数据类型的概念与程序设计语⾔中数据类型概念的区别。

【解答】数据结构是指相互之间存在⼀定关系的数据元素的集合。

⽽抽象数据类型是指⼀个数据结构以及定义在该结构上的⼀组操作。

程序设计语⾔中的数据类型是⼀个值的集合和定义在这个值集上⼀组操作的总称。

抽象数据类型可以看成是对数据类型的⼀种抽象。

串:是零个或多个字符组成的有限序列。

串是⼀种特殊的线性表，它的每个结点仅由⼀个字符组成。

空串 :长度为零的串，它不包含任何字符。

空⽩串 :仅由⼀个或多个空格组成的串⼦串 :串中任意个连续字符组成的⼦序列称为该串的⼦串。

串变量和串常量通常在程序中使⽤的串可分为：串变量和串常量。

（1）串变量 ：串变量和其它类型的变量⼀样，其取值是可以改变的。

（2）串常量 ：串常量和整常数、实常数⼀样，在程序中只能被引⽤但不能改变其值。

即只能读不能写。

（1）树形图表⽰： 树形图表⽰是树结构的主要表⽰⽅法。

（2）树的其他表⽰法① 嵌套集合表⽰法：是⽤集合的包含关系来描述树结构。

② 凹⼊表表⽰法：类似于书的⽬录③ ⼴义表表⽰法：⽤⼴义表的形式表⽰的。

上图 (a)树的⼴义表表⽰法如下：（A（B（E，F（I，J））， C，D（G，H）））1．中序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)访问根结点； (3)遍历右⼦树。

2．先序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1) 访问根结点； (2) 遍历左⼦树； (3) 遍历右⼦树。

3．后序遍历得递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)遍历右⼦树； (3)访问根结点。

2、链表具有的特点是B 插⼊、删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正⽐顺序队列（1）队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

（2） 顺序队列的表⽰①和顺序表⼀样顺序队列⽤⼀个向量空间存放当前队列中的元素。

顺序队列基本操作顺序队列是一种基于数组实现的线性数据结构，它具有先进先出（FIFO）的特性。

在顺序队列中，元素的插入和删除操作都是在队尾进行的。

一、初始化队列初始化队列是指创建一个空的顺序队列，准备接收元素。

顺序队列的初始化操作通常包括两个步骤：分配内存空间和初始化队列指针。

在分配内存空间时，需要根据队列的最大容量来确定所需的数组大小。

例如，如果队列的最大容量为n，那么需要分配n个元素大小的连续内存空间。

初始化队列指针时，需要将队头和队尾指针都指向队列的起始位置。

这样，队列就可以开始接收元素了。

二、判断队列是否为空判断队列是否为空是指检查队列中是否还有元素。

如果队列为空，则表示队列中没有任何元素；如果队列不为空，则表示队列中至少有一个元素。

判断队列是否为空的方法是比较队头和队尾指针的值。

如果它们相等，则表示队列为空；如果它们不相等，则表示队列不为空。

三、判断队列是否已满判断队列是否已满是指检查队列中是否还有剩余空间可以接收元素。

如果队列已满，则表示队列中的元素数量已经达到了队列的最大容量；如果队列未满，则表示队列中还有剩余空间可以继续接收元素。

判断队列是否已满的方法是比较队尾指针的值和队列的最大容量。

如果它们相等，则表示队列已满；如果它们不相等，则表示队列未满。

四、入队操作入队操作是指向队列中插入一个元素。

在顺序队列中，入队操作通常是将新元素插入到队尾。

入队操作的步骤如下：1. 判断队列是否已满，如果已满则无法插入新元素；2. 将新元素赋值给队尾指针所指向的位置；3. 队尾指针加一，指向下一个位置。

五、出队操作出队操作是指从队列中删除一个元素。

在顺序队列中，出队操作通常是删除队头元素。

出队操作的步骤如下：1. 判断队列是否为空，如果为空则无法删除元素；2. 将队头指针所指向的元素删除；3. 队头指针加一，指向下一个位置。

六、获取队头元素获取队头元素是指获取队列中的第一个元素，但不删除它。

在顺序队列中，获取队头元素通常是返回队头指针所指向的元素。

一、实验目的1. 理解顺序循环队列的概念和原理。

2. 掌握顺序循环队列的初始化、入队、出队等基本操作。

3. 通过编程实现顺序循环队列，并验证其功能。

二、实验原理顺序循环队列是一种利用一维数组实现队列的存储结构。

它将一维数组看作是首尾相连的循环结构，队列的头部和尾部在数组的两端。

顺序循环队列的特点是：队列满时，头指针和尾指针相差一个数组的长度；队列空时，头指针和尾指针相等。

顺序循环队列的基本操作如下：1. 初始化：创建一个顺序循环队列，并设置头指针和尾指针。

2. 入队：将元素插入队列尾部。

3. 出队：从队列头部删除元素。

4. 判断队列是否为空或满。

三、实验内容1. 创建顺序循环队列类。

2. 实现顺序循环队列的初始化、入队、出队等基本操作。

3. 编写测试代码，验证顺序循环队列的功能。

四、实验步骤1. 创建顺序循环队列类，定义队列长度、头指针、尾指针等属性。

2. 实现顺序循环队列的初始化方法，初始化头指针和尾指针。

3. 实现顺序循环队列的入队方法，判断队列是否已满，如果未满，将元素插入队列尾部，并更新尾指针；如果已满，则提示队列已满。

4. 实现顺序循环队列的出队方法，判断队列是否为空，如果为空，则提示队列已空；如果未空，则从队列头部删除元素，并更新头指针。

5. 编写测试代码，创建顺序循环队列实例，执行入队和出队操作，验证顺序循环队列的功能。

五、实验结果与分析1. 初始化顺序循环队列```pythonclass CircularQueue:def __init__(self, size):self.queue = [None] sizeself.head = 0self.tail = 0self.count = 0self.maxsize = size```2. 入队操作```pythondef enqueue(self, item):if self.count == self.maxsize:print("Queue is full")else:self.queue[self.tail] = itemself.tail = (self.tail + 1) % self.maxsizeself.count += 1```3. 出队操作```pythondef dequeue(self):if self.count == 0:print("Queue is empty")else:item = self.queue[self.head]self.queue[self.head] = Noneself.head = (self.head + 1) % self.maxsize self.count -= 1return item```4. 测试代码```pythondef test_circular_queue():queue = CircularQueue(5)print("Enqueue 1 to 5:")for i in range(1, 6):queue.enqueue(i)print(queue.queue)print("Dequeue 1 to 5:")for _ in range(5):print(queue.dequeue())print(queue.queue)test_circular_queue()```实验结果分析：通过测试代码，我们可以看到顺序循环队列在初始化、入队和出队操作时都能正确执行。

Data structures
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(1) 栈的静态分配顺序存储结构描述 ② top为整数且指向栈顶元素 当top为整数且指向栈顶元素时，栈空、入栈、栈满 及出栈的情况如图3.2所示。初始化条件为 S.top=-1。
(a) 栈空S.top==-1 (b) 元素入栈S.stack[++S.top]=e (c) 栈满S.top>=StackSize-1 (d) 元素出栈e=S.stack[S.top--]
/*栈顶指针，可以指向栈顶
元素的下一个位置或者指向栈顶元素*/
int StackSize; /*当前分配的栈可使用的以 元素为单位的最大存储容量*/
}SqStack;
/*顺序栈*/
Data structures
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(2) 栈的动态分配顺序存储结构描述 ① top为指针且指向栈顶元素的下一个位置 当top为指针且指向栈顶元素的下一个位置时，栈空 、入栈、栈满及出栈的情况如图3.3所示。初始化条 件为S.top=S.base。
…，n-1，n≥0} 数据关系：R={< ai-1，ai>| ai-1，ai∈D，i=1，2
，…，n-1 } 约定an-1端为栈顶，a0端为栈底 基本操作：
(1) 初始化操作：InitStack(&S) 需要条件：栈S没有被创建过 操作结果：构建一个空的栈S (2) 销毁栈：DestroyStack(&S) 需要条件：栈S已经被创建 操作结果：清空栈S的所有值，释放栈S占用的内存空间
return 1;
}
Data structures
栈

一、实验目的1. 理解顺序队列的概念和特点。

2. 掌握顺序队列的创建、插入、删除、遍历等基本操作。

3. 熟悉顺序队列在实际问题中的应用。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 编译器：Visual Studio 2019三、实验内容1. 顺序队列的定义及特点2. 顺序队列的创建3. 顺序队列的插入操作4. 顺序队列的删除操作5. 顺序队列的遍历操作6. 顺序队列的应用四、实验步骤1. 顺序队列的定义及特点顺序队列是一种基于数组的线性数据结构，它具有以下特点：（1）顺序存储：队列元素按照一定的顺序存储在一段连续的内存空间中。

（2）动态扩展：当队列满时，可以动态地增加队列的存储空间。

（3）操作简单：插入和删除操作只需改变队列的头指针和尾指针。

2. 顺序队列的创建首先，定义一个顺序队列的结构体，包括队列的最大容量、队列的当前长度、队列的元素数组等。

然后，实现队列的创建函数，初始化队列的各个属性。

```cpp#include <iostream>using namespace std;#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int front;int rear;} SeqQueue;void InitQueue(SeqQueue &Q) {Q.front = 0;Q.rear = 0;}```3. 顺序队列的插入操作实现队列的插入函数，判断队列是否已满，如果未满，则将新元素插入到队列的尾部。

```cppbool EnQueue(SeqQueue &Q, int x) {if ((Q.rear + 1) % MAX_SIZE == Q.front) {return false; // 队列已满}Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MAX_SIZE;return true;}```4. 顺序队列的删除操作实现队列的删除函数，判断队列是否为空，如果非空，则删除队列的头部元素。

顺序队列的基本操作顺序队列是一种基于数组实现的队列，它具有先进先出的特性。

在顺序队列中，元素的插入和删除操作都是在队尾进行的，而队头则用于读取元素。

本文将介绍顺序队列的基本操作，包括初始化、入队、出队、获取队头元素、获取队列长度以及判断队列是否为空等。

一、初始化在使用顺序队列前，需要先进行初始化操作。

初始化操作主要是为顺序队列分配内存空间，并将其相关属性（如头指针和尾指针）设置为初始值。

以下是顺序队列初始化的代码实现：```#define MAXSIZE 100 // 定义最大容量typedef struct {int data[MAXSIZE]; // 存储数据元素int front; // 头指针int rear; // 尾指针} SqQueue;void InitQueue(SqQueue *Q) {Q->front = Q->rear = 0; // 初始化头指针和尾指针为0}```二、入队入队是将一个元素插入到顺序队列的末尾。

在进行入队操作时，需要先判断当前是否已经达到了最大容量。

如果没有达到最大容量，则将新元素插入到尾部，并更新尾指针；否则，表示当前已经满员，无法再插入新元素。

以下是顺序队列入队的代码实现：```void EnQueue(SqQueue *Q, int x) {if ((Q->rear + 1) % MAXSIZE == Q->front) { // 判断队列是否已满printf("Queue is full.\n");return;}Q->data[Q->rear] = x; // 将新元素插入到尾部Q->rear = (Q->rear + 1) % MAXSIZE; // 更新尾指针}```三、出队出队是将顺序队列中的一个元素删除，并返回该元素的值。

在进行出队操作时，需要先判断当前是否为空队列。

如果不为空，则将头部元素删除，并更新头指针；否则，表示当前已经为空，无法进行出队操作。

数据结构与算法复习题数据结构与算法复习题一、基本概念1、数据结构的定义和分类1.1 定义和作用1.2 分类1.3 逻辑结构和物理结构2、算法的定义和特性2.1 定义和作用2.2 特性2.3 时间复杂度和空间复杂度二、线性表1、顺序表1.1 定义和实现方式1.2 基本操作：插入、删除、查找1.3 顺序表的优缺点及适用场景2、链表2.1 定义和实现方式：单链表、双向链表、循环链表2.2 基本操作：插入、删除、查找2.3 链表的优缺点及适用场景3、栈和队列3.1 栈的定义和实现方式3.2 栈的基本操作：入栈、出栈、获取栈顶元素3.3 栈的应用场景3.4 队列的定义和实现方式：顺序队列、链式队列、循环队列3.5 队列的基本操作：入队、出队、获取队头元素3.6 队列的应用场景三、树与二叉树1、树的定义和基本术语1.1 树的定义和特性1.2 树的基本术语：根节点、父节点、子节点、叶子节点1.3 树的表示方法：双亲表示法、孩子表示法、孩子兄弟表示法2、二叉树的定义和性质2.1 二叉树的定义和性质2.2 二叉树的基本术语：根节点、左子树、右子树、叶子节点、深度、高度2.3 二叉树的遍历方式：前序遍历、中序遍历、后序遍历、层序遍历3、二叉搜索树3.1 定义和性质3.2 插入操作3.3 删除操作3.4 查找操作4、平衡二叉树4.1 定义和性质4.2 平衡因子和平衡操作4.3 AVL树和红黑树四、图1、图的定义和基本术语1.1 图的定义和性质1.2 图的基本术语：顶点、边、度、路径、连通图、强连通图2、图的存储结构2.1 邻接矩阵2.2 邻接表2.3 其他存储结构：十字链表、邻接多重表3、图的遍历算法3.1 深度优先搜索（DFS）3.2 广度优先搜索（BFS）4、最短路径算法4.1 Dijkstra算法4.2 Floyd-Warshall算法附件：附件1：数据结构复习总结表格附件2：算法复习题答案解析法律名词及注释：1、数据结构：指的是数据对象及其关系、操作和实现的逻辑结构和存储结构。

队列的基本操作应⽤---舞伴问题（数据结构实验项⽬三）课程名称：数据结构实验⽬的：1．掌握队列的定义及实现；2．掌握利⽤队列的基本操作。

实验要求：1、使⽤链式结构完成队列的各种基本操作；2、补充完善教材81页的舞伴问题。

实验项⽬名称：队列的基本操作应⽤实验过程：1、先建⽴⼀个舞者队列，依次往队列中添加⼈员信息（8个⼈，5男3⼥）；2、分别创建男⼥队列；3、从舞者队列中依次将队⾸元素出队并判断其性别并添加⾄男队（5⼈）或⼥队（3⼈）；4、分别从男队和⼥队出队队⾸元素并配对输出；（男队⼥队分别3⼈）5、将未完成的⼀队队⾸元素输出（男队的队⾸成员名称）。

实验报告中给出算法3.23的代码实验结果：输⼊：8⼈信息（A,B,C,D,E,F,G,H）输出：The dancepartners:A---BC---DE---FG is waiting for a partner.实验分析：1.队列的操作特点；2.列举调试运⾏过程中出现的错误并分析原因。

要求：(1) 程序要添加适当的注释，程序的书写要采⽤缩进格式。

(2) 程序要具在⼀定的健壮性，即当输⼊数据⾮法时，程序也能适当地做出反应。

(3) 程序要做到界⾯友好，在程序运⾏时⽤户可以根据相应的提⽰信息进⾏操作。

(4) 上传源程序到课堂派。

顺序表的源程序保存为dancepartner.cpp。

程序代码：#include<stdio.h>#define MAXQSIZE 100#define QueueSize 20#define OK 1#define ERROR 0#define OVERFLOW 0#include <cstdlib>#include<iostream>using namespace std;typedef char QElemType;typedef int Status;//typedef char SElemType;typedef struct{char name[QueueSize];char sex;}person;typedef struct{person *dancer;person *base; //存储空间的基地址int front; //头指针int rear; //尾指针}SqQueue;Status InitQueue(SqQueue &Q){//构造⼀个空队列QQ.base=new person[MAXQSIZE]; //为队列分配⼀个最⼤容量为MAXQSIZE的数组空间if(!Q.base) exit(OVERFLOW); //存储分配失败Q.front=Q.rear=0; //头指针和尾指针为零，队列为空return OK;}Status EnQueue(SqQueue &Q,person e){//插⼊元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front) //尾指针在循环意义上加1后等于头指针，表明队满return ERROR;Q.base[Q.rear]=e; //新元素插⼊队尾Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1return OK;}int QueueEmpty(SqQueue &Q){if (Q.front==Q.rear) return OK;else return ERROR;}Status DeQueue(SqQueue &Q,person &e){//删除Q的队头元素，⽤e返回其值if(Q.front==Q.rear) return ERROR; //队空e=Q.base[Q.front]; //保存队头元素Q.front=(Q.front+1)%MAXQSIZE; //队头指针加1return OK;}person GetHead(SqQueue Q){//返回Q的队列元素，不修改队头指针if(Q.front!=Q.rear) //队列⾮空return Q.base[Q.front]; //返回队头元素的值，队头指针不变}void DancePartner(person dancer[],int num){//结构数组dancer中存放跳舞的男⼥，num是跳舞的⼈数person p;int i;SqQueue Mdancers,Fdancers;InitQueue(Mdancers); //男⼠队列初始化InitQueue(Fdancers); //⼥⼠队列初始化for (i=0;i<num;i++) //根据性别依次将跳舞的⼈插⼊相应队列{p=dancer[i];if (p.sex=='F') EnQueue(Fdancers,p); //插⼊男队else EnQueue(Mdancers,p); //插⼊⼥队}cout<<"The dancing partner are:\n";while(!QueueEmpty(Fdancers)&&!QueueEmpty(Mdancers)){//依次输出男⼥舞伴的姓名DeQueue(Fdancers,p); //⼥⼠出队cout<<<<""; //输出出队⼥⼠姓名DeQueue(Mdancers,p); //男⼠出队cout<<<<endl; //输出出队男⼠姓名}if (!QueueEmpty(Fdancers)) //⼥⼠队⾮空，输出队头⼥⼠的姓名{p=GetHead(Fdancers); // 取⼥队的头cout<<<<" is waiting for a partner."<<endl;}else if (!QueueEmpty(Mdancers)) //男⼠队⾮空，输出男⼠队头的姓名 {p=GetHead(Mdancers); // 取男队的头cout<<<<" is waiting for a partner."<<endl;}}int main(){int i,j;person dancer[QueueSize];cout<<"请输⼊跳舞的⼈数：";cin>>j;while(j<=0){cout<<"输⼊错误，请重新输⼊跳舞的⼈数：";cin>>j;}for(i=1;i<=j;i++){cout<<"请输⼊第"<<i<<"舞者的名字:"<<endl;cin>>dancer[i-1].name;cout<<"请输⼊第"<<i<<"个⼈的性别(F/M):"<<endl;cin>>dancer[i-1].sex;while(dancer[i-1].sex!='F'&&dancer[i-1].sex!='M'){cout<<"*******输⼊错误，请重新输⼊：\n";cout<<dancer[i-1].sex;cout<<"请输⼊第"<<i<<"个⼈的性别(F/M):"<<endl;cin>>dancer[i-1].sex;break;}}DancePartner(dancer,j);}。

a0
a1
a2
…
…
an-1
front
元素移动方向
rear
图7.15队列
图中队列的队尾(rear) 随着元素的不断加入，而不断向后移； 而队头(front)随元素的出队，也不断后移，即位置在变。
7.3.2 队列
顺序队列的缺点：
由图可见：空队 时指针（下标） front和rear在 一起都指向队前 方，当有元素进 队，则rear后 移；有元素出队， 则front后移， 最后分配给队的 前端不再被利用。
加标志，能否实现？
Question：循环队列的队满/队空如何区分？ （1）浪费一个空位置，空队时rear=front；满队时 必须空一个位置； （2）加标志来表示队空/队满，进队出队都要判 断，使用上更不方便。
顺序表循环队列类的设计
class CycleQueue {
不用空位置，用标志需要有
int rear,front;
//进队，rear++
DataType DeQue();
//出队，front++
DataType GetFront();
//取队头数据，front不变
void MakeEmpty不(){用fro空nt=位rea置r=，0;e不lem用e标nts志[fr。on当t]=NULL; }//队置空
（初始态） };
istack.PrintStack();
for(i=0;i<10;i++) b[i]=istack.Pop();
if(istack.IsEmpty()) cout<<"栈空"<<endl;
for(i=0;i<10;i++) cout<<b[i]<<'\t'; //注意先进后出

队列是一种常见的数据结构，它遵循先进先出（FIFO）的操作规则。

在日常生活和计算机科学中都有着广泛的应用。

本文将详细介绍队列的定义、特性、基本操作以及如何使用队列解决实际问题。

一、队列的定义与特性1.1 定义：队列是一种线性数据结构，其特点是在队列的一端进行插入操作，称为入队（enqueue），在队列的另一端进行删除操作，称为出队（dequeue）。

队列通常用于存储按顺序排列的数据，如任务调度、消息队列等场景。

1.2 特性：队列的特性主要包括FIFO的操作规则、队头和队尾的概念以及队列的大小限制。

二、队列的基本操作2.1 入队操作：将元素添加至队列的末尾，同时更新队尾指针。

2.2 出队操作：从队列的头部删除元素，同时更新队头指针。

2.3 获取队头元素：返回队列头部的元素，但不删除该元素。

2.4 判空操作：检查队列是否为空，若为空则返回True，否则返回False。

2.5 获取队列大小：返回队列中元素的个数。

2.6 清空队列：删除队列中的所有元素。

三、队列的应用场景3.1 任务调度：在操作系统中，队列常用于实现任务调度，按照FIFO 的规则依次执行任务。

3.2 网络通信：消息队列是分布式系统中常用的通信方式，通过队列将消息从发送端传递至接收端。

3.3 数据缓存：队列可以被用来缓存数据，有效控制数据的读写速度，避免数据传输过程中的延迟。

四、队列的实现方式4.1 数组实现：使用数组实现队列时，需定义队列的大小，并通过数组的下标实现队列的操作。

4.2 链表实现：使用链表实现队列时，通过节点之间的引用实现队列的操作，灵活性更高。

五、解决实际问题的案例分析5.1 超市排队问题：假设超市有多个收银台，顾客按照到达的顺序进行排队。

此时可以使用队列数据结构来模拟超市的排队过程，保证顾客按照FIFO的规则进行结账。

5.2 网络消息传递：在分布式系统中，服务之间需要进行消息传递。

通过队列数据结构，可以实现消息的异步传递，保证消息的顺序性和可靠性。

循环队列的基本运算
（5）元素出队：
procedure delqueue(var Q:queue;var X:elemtype); begin if qempty(Q) then writeln(‘Underflow’) else begin Q.front:=(Q.front+1) mod maxsize; X:=Q.data[Q.front]; end; end;
最后根据队列sq中的存储信息和指针位 置，即可链接成从迷宫入口到出口的最短路 径。就上例而言，sq队列的最后情况为：
当rear指针指示的数据元素已到达出口 （6，8）时，根据rear所据元素的前趋序号 即可获得所要的走迷宫的最短路径（回溯）。
例题4：产生数（2002年NOIP普及组第3题） 给出一个整数n（n<2000）和k个变换规则（k≤15） 规则：① 1个数字可以变换成另1个数字； ② 规则中，右边的数字不能为零。 例如：n=234，k=2规则为 2 → 5 3 → 6 上面的整数234经过变换后可能产生出的整数为 （包括原数） 234 534 264 564 共4种不同的产生数 求经过任意次的变换（0次或多次），能产生出多 少个不同的整数。 仅要求输出不同整数个数。
（2）队列可以理解为一个数组，数组元素是如下记录： RECORD C10,C7,C3, pre: integer; END; 数组下标为容器状态号。下面是倒油过程的队列：
当倒油产生出第19个容器状态时已达到了题解的 目的。这时只要根据pre中的状态号17可以回溯到第 17个容器状态的pre值为15，依次可再获得13，11， 9，7，5，2，1容器状态号，从而即可得到本题的倒 油过程（共倒9次），而且是最少的倒油次数。
（1）从一个容器的状态（三个容器中油的 容量）看，虽然有可能经过上述六种倒油的 方法产生六种容器状态，但实际上这六种新 产生的容器状态，许多是已经出现过的状态。 例如初始状态（10,0,0）表示 C10=10， C7=0，C3=0，经过上述六种倒油方法只能产 生出两种新的容器状态（3,7,0），表示C10 向C7倒油的结果和（7,0,3），表示C10向C3 倒油的结果。如果再增加应该表示新容器状 态是由什么状态产生的指示pre，那么用这 三个容器倒油的过程就可以用队列的方法来 实现了。

数据结构
网络课程
常州信息职业技术学院
算
教学目标
任 务 5
法 演
1、知识目标
示
1）掌握队列的定义及基本运算；
上 一
2）掌握循环队列、链队列基本运算的实现算
页 法。
进 下 2、能力目标
位
一 页
1）具有恰当的选择队列作为数据的逻辑结构、
循环队列、链队列作为数据的存储结构的能
制 返 力；
转 回 2）具有应用队列解决实际问题的能力。
位
一 页
义下的加1操作可以描述为：
①利用选择结构
循环队列示意图
制 返 if(i+1==QueueSize)//i为front或rear
回 i=0;
转
else
换
VC++
i++; ②利用模运算
i=(i+1)%QueueSize;//i为front或rear
9
算 3、循环队列边界条件的处理方法
任
法 演
循环队列中，由于入队时尾指针向前追赶头指
示队列满。 我们将使用此方法。
10
算 4、循环队列的描述
任 务 5
进 位 制 转
法 演 示
上 一 页
下 一 页
返 回
#tt5yyd、ppe④v{将}⑤D{下}eefDiii循DitQQoddCnnniaiQQQfeni尾的faeettt(ti--am入出d环(eQa---trff>>frctQ{a>>>QTarep指头EocsQfcuTp{队队o队cdrTauyrt=huouneepurynouoraeyp针 指aeQnuuuQa;utptneut②i{}③i{列uperus};tncnnraetue-tn;ue(=ee加针stD[E=ttt>D“eFrr/t-的eQ(;d(c判判/QQt(eemSd-队“auQ+eu队eaQi加1;tt-a队tirQeuum基luut+>paz-队队qtla⑥D{}空-(eerr中>a(Tte;r1u>C[p满nnyQuue[本①v{airQrye空满f;}1”Q取f(ieaeeet/元orQQ/up)r(Q/a/0u”trEFa/o)QQ/运i-计eeu尾]队T置头0--de{r)队>n)um素QQ=(;r{>>+;uu)yup)Ctlfn算I数x指;+e列lcc1eep--per队指u/头n(个/i>>;/oxooueuQS)1tetCr/定iy%器s定nxifcuuQ针tee元)i空针元/t-QQ(ir数(z%otiE/nn(r>“oC*u义Q]t新e0定uQ义tt定uu(素;m队定nd素QeQ]==0)等inuee;rtuua;队元/==p)/义,t=队ueu}uQ义个/空t义e/eD;=队t于auQ0队ee}eQuyu列素0[*Fae(;u列数”e(uQe-C;列tSQQe列rQ>aeu/元插o*S-ii/最/加Tu)u)rezr)/>队nQ元i;元/e队Q)eeyez/素入tf/*ae大队)Su1;(/pre列u素Qr计xC素o空ei;e=类e队/zi容nS满)i/tu无0xe个r数循定(t下i/Qe型];;尾0)z/量上;循元e)数器*环u义溢;时Q}e溢环素减u置意)队e意为10义*满Q义空下)

工作（学习）日志日期时间：2012年11月5日20:37:54主题：队列的基本操作操作命令选择型的测试程序内容：#include<stdio.h>#include<stdlib.h>#include"lc.h"#define ElemType int#define MAXSIZE 50typedef struct squeue//用数组表示一定容量的队列，队首与队尾确定之后（中间的任何一个元素是联系着的，能够访问到），则一定容量的队列也就确定了{ElemType data[MAXSIZE];int rear; //指向队尾元素的下一个位置int front; //指向队手元素}SqQueue;//链式队列存储类型的定义（有时候复杂的数据类型可能会出现结构套结构，或者其他数据类型的情况）//队列的本质，即由多个结点链接而成，每个节点是一个结点结构体，由首尾指针指示队首与队尾的位置。

队首与队尾的指针确定之后（中间的不用管，因为他们有指针相连由结点的指针域确定）一定容量的队列也就确定了typedef struct lqueue_node{ElemType data;struct lqueue_node *next;//这样只含这样两种数据类型的结构体，只是形成的链表结点，只是这样的对链表结点的指针域赋值即在逻辑上形成了一条链表，并没有其他类型的数据结构。

只是为其他类型的数据结构提高了一种链式存储结构，比如前面的栈，一条链表所含的数据元素的操作足以满足栈的所有操作}LinkNode;typedef struct lqueue//要是一条链表所含的数据元素的操作无法达到要求，比如说队列的队首，队尾指针无法再链表中体现？？？？？？？？？？？？不明白了到这里{LinkNode *rear,*front;//由两个指针域组成}LinkQueue;/*******************第一部分：（循环）顺序队列的基本操作*************//*********************队列的初始化***********************/SqQueue *Init_SqQueue(){SqQueue *S;S=(SqQueue *)malloc(sizeof(SqQueue));S->front =0;S->rear=0;return S;}/*********************done****************************//*********************（循环）队列的判空***********************/Status Empty_SqQueue(SqQueue *S){if(S->rear==S->front)//这里的fear=front,为空的唯一条件，区别于队满{printf("\n队列空\n");return TRUE;}else{printf("队列不空");return FALSE;}}/*********************done****************************//*********************元素的入队列***********************/Status En_SqQueue(SqQueue *S,ElemType x){//入队列首先盘队列是否满了if((S->rear+1)%MAXSIZE==S->front) return ERROR;//牺牲一个内存单元来使队满的条件为(rear+1)%MAXSIZE和front相同,这样就可以和对空的条件rear=front S->data[S->rear]=x;//有了这一个队尾指针进1的方法，rear的值只能在0----MAXSIZE-1之间了，不会出现>=maxsize的情况，所以当rear值达到maxsize-1时，加一自动会跳到0的位置S->rear=(S->rear+1)%MAXSIZE; //有了这一个队尾指针进1的方法，fear的值只能在0----MAXSIZE-1之间了，不会出现>=maxsize的情况return OK;}/*********************done****************************//*********************元素的出队列***********************/Status De_SqQueue(SqQueue *S){if(S->rear ==S->front) return ERROR;S->front=(S->front+1)%MAXSIZE;return OK;}/*********************done****************************//*********************打印队列元素********************/void Print_SqQueue(SqQueue *S){int n;printf("\n当前队列：<队首");for(n=S->front;n<S->rear;n++)printf(" %d",S->data[n]);printf(" 队尾>");}/*********************done****************************//*********第二部分：（循环）链式队列的基本操作*****************//*********************队列的初始化**************************/ LinkQueue *Init_LinkQueue(){LinkQueue *L;L=(LinkQueue*)malloc(sizeof(LinkQueue));//新队列L->front=L->rear=(LinkNode*)malloc(sizeof(LinkNode));//头节点L->front->next=NULL;return L;}/***********************done***************************//***********************入队列***************************/ Status En_LinkQueue(LinkQueue *L,ElemType x){LinkNode *newnode;newnode=(LinkNode*)malloc(sizeof(LinkNode));newnode->data=x;newnode->next=NULL;L->rear->next=newnode;//构链链表L->rear=newnode;//指明队尾位置return OK;}/***********************done***************************//***********************队首删除元素***************************/Status De_LinkQueue(LinkQueue *L){LinkNode *p;p=L->front->next;L->front->next=p->next;//构链free(p);return OK;}/***********************done***************************//***********************队列判空***************************/ Status Empty_LinkQueue(LinkQueue *L){if(L->front==L->rear){printf("\n队列空\n");return TRUE;}else{printf("\n队列不空\n");return FALSE;}}/***********************打印队列***************************/ void Print_LinkQueue(LinkQueue *L){LinkNode *p;p=L->front->next;printf("\n当前队列内容：<队首");while(p){printf(" %d",p->data);p=p->next;}printf(" 队尾>");}/***********************done***************************//*************显示菜单********************************/ void Show_menu(){printf("\n ※顺序队列操作| ※链队列操作\n");printf(" 1)队列初始化| 5)队列初始化\n");printf(" 2)队列判空| 6)队列判空\n");printf(" 3)入队列| 7)入队列\n");printf(" 4)出队列| 8)出队列\n");printf(" 9)退出程序\n");printf("请输入要进行的操作:");}/*********************done****************************/void main(){/*该部分为测试单个程序所用SqQueue *s;ElemType r1,r2,r3;//初始化s=Init_SqQueue();//判空？Empty_SqQueue(s);//入队列printf("\n请输入你要入队列的值：");scanf("%d",&r1);En_SqQueue(s,r1);Print_SqQueue(s);printf("\n请输入你要入队列的值：");scanf("%d",&r2);En_SqQueue(s,r2);Print_SqQueue(s);printf("\n请输入你要入队列的值：");scanf("%d",&r3);En_SqQueue(s,r3);Print_SqQueue(s);//出队列printf("\n\n出队列操作\n");Print_SqQueue(s);Empty_SqQueue(s);printf("\n第一次出队列结果\n"); De_SqQueue(s);Print_SqQueue(s);Empty_SqQueue(s);printf("\n第二次出队列结果\n"); De_SqQueue(s);Print_SqQueue(s);Empty_SqQueue(s);printf("\n第三次出队列结果\n"); De_SqQueue(s);Print_SqQueue(s);Empty_SqQueue(s);LinkQueue *q;q=Init_LinkQueue();En_LinkQueue(q,1);Print_LinkQueue(q);De_LinkQueue(q);Print_LinkQueue(q);*///正式程序：LinkQueue *q;ElemType R;SqQueue *s;ElemType r;int choice;int en1=0,en2=0;//de初始化标志符号while(1){Show_menu();scanf("%d",&choice);if(choice==9) break;switch(choice){case 1:s=Init_SqQueue();printf("\n初始化完毕\n");Print_SqQueue(s);break;//switch case 语句中case 后面有多个语句时可以不用{}括起来case 2:s=Init_SqQueue();Empty_SqQueue(s);break;//switch case 语句中case 后面有多个语句时可以不用{}括起来case 3:if(!en1) s=Init_SqQueue();//只在第一次进行入队列操作的时候执行初始化程序*******很重要的一个方法，标志法，开始设置一个初值，然后在程序中改变该值，然后检查其的变化while(1){printf("\n请输入要入栈的值：(输入0结束)");scanf("%d",&r);if(r){En_SqQueue(s,r);en1++;//供下面检测是否已经进行入队列操作Print_SqQueue(s);}elsebreak;}break;//switch case 语句中case 后面有多个语句时可以不用{}括起来case 4:if(!en1){s=Init_SqQueue();Print_SqQueue(s);En_SqQueue(s,100);En_SqQueue(s,200);En_SqQueue(s,300);En_SqQueue(s,400);En_SqQueue(s,500);En_SqQueue(s,600);Print_SqQueue(s);}De_SqQueue(s);Empty_SqQueue(s);Print_SqQueue(s);en1++;break;//switch case 语句中case 后面有多个语句时可以不用{}括起来case 5:q=Init_LinkQueue();printf("\n初始化完毕\n");Print_LinkQueue(q);break;//switch case 语句中case 后面有多个语句时可以不用{}括起来case 6:q=Init_LinkQueue();Empty_LinkQueue(q);break;//switch case 语句中case 后面有多个语句时可以不用{}括起来case 7:if(!en2) q=Init_LinkQueue();while(1){printf("\n请输入要入队列的值：(输入0结束)");scanf("%d",&R);if(R){En_LinkQueue(q,R);Print_LinkQueue(q);en2++;}elsebreak;}break;//switch case 语句中case 后面有多个语句时可以不用{}括起来case 8:if(!en2){q=Init_LinkQueue();Print_LinkQueue(q);En_LinkQueue(q,100);En_LinkQueue(q,200);En_LinkQueue(q,300);En_LinkQueue(q,400);En_LinkQueue(q,500);En_LinkQueue(q,600);En_LinkQueue(q,700);Print_LinkQueue(q);}De_LinkQueue(q);Empty_LinkQueue(q);Print_LinkQueue(q);en2++;break;//switch case 语句中case 后面有多个语句时可以不用{}括起来}}printf("\n程序已退出\n");}心得：。

}
if(StackTop(myStack,&x)==0)
{
printf("error!\n");
return;
}
else
printf("The element of local top is :%d\n",x);
printf("The sequence of outing elements is:\n");
(*head)->next = NULL;
}/*判非空操作：*/
int StackNotEmpty(LSNode *head) /*判堆栈是否非空，非空返回1；空返回0*/
{
if(head->next == NULL) return 0; else return 1;
}/*入栈操作：*/
int StackPush(LSNode *head, DataType x) /*把数据元素x插入链式堆栈head的栈顶作为新的栈顶*/ { LSNode *p; if((p = (LSNode *)malloc(sizeof(LSNode))) == NULL) { printf("内存空间不足无法插入! \n"); return 0; } p->data = x; p->next = head->next; /*新结点链入栈顶*/ head->next = p; /*新结点成为新的栈顶*/ return 1; } /*出栈操作：*/
依次把5个元素入栈然后出栈并在屏幕上显示出栈的数据元对顺序循环队列常规的方法是使用队尾指针和队头指针队尾指针用于指示当前的队尾位置下标队头指针用于指示当前的队头位置下标
《数据结构》课程实验实训报告

队列基本操作实验报告一、实验目的本次实验的主要目的是通过编写队列的基本操作，掌握队列数据结构的基本原理及其应用。

二、实验内容1. 队列的定义和基本操作队列是一种先进先出（FIFO）的线性数据结构，它只允许在队尾插入元素，在队头删除元素。

队列的基本操作包括：入队（enqueue）、出队（dequeue）、获取队头元素（getFront）、获取队列长度（getSize）等。

2. 队列的顺序存储结构顺序存储结构是指用数组来存储队列中的元素，其中需要维护两个指针：front指向队头元素，rear指向下一个待插入位置。

当rear等于数组长度时，需要进行循环，即将rear置为0。

3. 队列的链式存储结构链式存储结构是指用链表来存储队列中的元素，其中每个节点包含一个数据域和一个指针域。

head指向链表头节点，tail指向链表尾节点。

4. 实验流程(1) 编写顺序存储结构下的队列基本操作函数。

(2) 编写链式存储结构下的队列基本操作函数。

(3) 分别测试两种存储方式下各个函数是否正确实现。

三、实验步骤1. 顺序存储结构下的队列基本操作函数(1) 定义队列结构体和初始化函数。

typedef struct {int *data;int front, rear;int maxSize;} SeqQueue;SeqQueue* initSeqQueue(int maxSize) {SeqQueue *q = (SeqQueue*)malloc(sizeof(SeqQueue));q->data = (int*)malloc(sizeof(int) * maxSize);q->front = q->rear = 0;q->maxSize = maxSize;return q;}(2) 实现入队操作。

bool enqueue(SeqQueue *q, int x) {if ((q->rear + 1) % q->maxSize == q->front) return false; // 队满q->data[q->rear] = x;q->rear = (q->rear + 1) % q->maxSize; // 循环return true;}(3) 实现出队操作。

入队：Status EnQueue (LinkQueue &Q, QElemType e){ // 插入元素e为Q的新队尾元素p = (QueuePtr) malloc (sizeof (QNode)); //生成新结点if (!p) exit (OVERFLOW); //存储分配失败p->data = e; p->next = NULL; //插入队尾Q.rear->next = p;Q.rear = p; //修改队尾指针指向队尾return OK;}出队：Status DeQueue (LinkQueue &Q, QElemType &e){ // 若队列不空，则删除Q的队头元素，用e 返回其值if (Q.front == Q.rear) return ERROR; //判空p = Q.front->next; e = p->data; //用e返回队头元素值Q.front->next = p->next; //修改头指针始终指向队首元素if (Q.rear == p) Q.rear = Q.front; //特殊情况处理空队free (p); //释放队首结点return OK;}代码一：#include <stdio.h>#include <malloc.h>typedef char ElemType;typedef struct qnode{ElemType data;struct qnode *next;} QNode;typedef struct{QNode *front;QNode *rear;} LiQueue;void InitQueue(LiQueue *&q);void DestroyQueue(LiQueue *&q);bool QueueEmpty(LiQueue *q);void enQueue(LiQueue *&q, ElemType e);bool deQueue(LiQueue *&q, ElemType &e);void InitQueue(LiQueue *&q)//初始化队列{q = (LiQueue *)malloc(sizeof(LiQueue));q->front = q->rear = NULL;}void DestroyQueue(LiQueue *&q)//销毁队列{QNode *p = q->front, *r;//p指向队头数据节点if (p != NULL)//释放数据节点占用空间{r = p->next;while (r != NULL){free(p);p = r; r = p->next;}}free(p);free(q);//释放链队节点占用空间}bool QueueEmpty(LiQueue *q)//判断队列是否为空{return(q->rear == NULL);}void enQueue(LiQueue *&q, ElemType e)//进队{QNode *p;p = (QNode *)malloc(sizeof(QNode));p->data = e;p->next = NULL;if (q->rear == NULL)//若链队为空,则新节点是队首节点又是队尾节点q->front = q->rear = p;else{q->rear->next = p;//将*p节点链到队尾,并将rear指向它q->rear = p;}}bool deQueue(LiQueue *&q, ElemType &e)//出队{QNode *t;if (q->rear == NULL)//队列为空return false;t = q->front;//t指向第一个数据节点if (q->front == q->rear) //队列中只有一个节点时q->front = q->rear = NULL;else//队列中有多个节点时q->front = q->front->next;e = t->data;free(t);return true;}void main(){ElemType e;LiQueue *q;printf("链队的基本运算如下:\n");printf(" (1)初始化链队q\n");InitQueue(q);printf(" (2)依次进链队元素a,b,c\n");enQueue(q, 'a');enQueue(q, 'b');enQueue(q, 'c');printf(" (3)链队为%s\n", (QueueEmpty(q) ? "空" : "非空"));if (deQueue(q, e) == 0)printf("\t提示:队空,不能出队\n");elseprintf(" (4)出队一个元素%c\n", e);printf(" (5)依次进链队元素d,e,f\n");enQueue(q, 'd');enQueue(q, 'e');enQueue(q, 'f');printf(" (6)出链队序列:");while (!QueueEmpty(q)){deQueue(q, e);printf("%c ", e);}printf("\n");printf(" (7)释放链队\n");DestroyQueue(q);}代码二：#include <stdio.h>#include <malloc.h>typedef struct qnode{int data;struct qnode *next;} QNode;//链队节点类型typedef struct{QNode *front, *rear;} QuType;//链队类型void Destroyqueue(QuType *&qu)//释放链队{QNode *p, *q;p = qu->front;if (p != NULL)//若链队不空{q = p->next;while (q != NULL)//释放队中所有的节点{free(p);p = q;q = q->next;}free(p);}free(qu);//释放链队节点}void SeeDoctor(){int sel, flag = 1, find, no;QuType *qu;QNode *p;qu = (QuType *)malloc(sizeof(QuType));//创建空队qu->front = qu->rear = NULL;while (flag == 1) //循环执行{printf("1:排队2:就诊3:查看排队4.不再排队,余下依次就诊5:下班请选择:");scanf("%d", &sel);switch (sel){case 1:printf(" >>输入病历号:");do{scanf("%d", &no);find = 0;p = qu->front;while (p != NULL && !find){if (p->data == no)find = 1;elsep = p->next;}if (find)printf(" >>输入的病历号重复,重新输入:");} while (find == 1);p = (QNode *)malloc(sizeof(QNode));//创建节点p->data = no; p->next = NULL;if (qu->rear == NULL)//第一个病人排队qu->front = qu->rear = p;else{qu->rear->next = p; qu->rear = p;//将*p节点入队}break;case 2:if (qu->front == NULL)//队空printf(" >>没有排队的病人!\n");else//队不空{p = qu->front;printf(" >>病人%d就诊\n", p->data);if (qu->rear == p)//只有一个病人排队的情况qu->front = qu->rear = NULL;elsequ->front = p->next;free(p);}break;case 3:if (qu->front == NULL) //队空printf(" >>没有排列的病人!\n");else //队不空{p = qu->front;printf(" >>排队病人:");while (p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");}一:二：总结体会：通过本次实验掌握了链式存储队列的进队和出队等基本操作，通过这些基本操作，我对队列问题有了更深的理解，能够正确理解队列问题及其使用。