数据结构实验——队列(附程序)

实验三 队列基本操作一、实验目的掌握队列的基本操作：初始化、判空、判满、入队、出队、取队列首元素等运算。

二、实验要求包含有头文件和main函数；1.格式正确，语句采用缩进格式；2.设计子函数实现题目要求的功能；3.编译、连接通过，熟练使用命令键；4.运行结果正确，输入输出有提示，格式美观。

三、实验设备、材料和工具1.奔腾2计算机或以上机型2.turboc2,win-tc四、实验内容和步骤实验内容：1.分析程序。

2.完成程序编写和补充步骤：3.确定数据的结构；4.利用main函数调用各子函数；5.调试、分析运行结果。

五、实验报告要求1.根据实验内容初步设计好程序，并从理论上排除错误；2.针对程序的健壮性准备好测试数据；3.结果分析中如实填写运行后的结果，记录调试过程中产生的重要问题和解决方法。

六、根据实验过程填写下面内容构建栈头文件，文件名称seqstack.h构建队列头文件，文件名称seqqueue.h基础部分1.构建队列逆置的程序，补充以下程序，完成运行和调试。

#include "stdio.h"#include "seqqueue.h"#include "seqstack.h"void proc(SeqQueue *q){SeqStack s;char a;InitStack(&s);while(!IsEmpty(q)){DeleteQueue(q,&a);Push(&s,a);}while(!IsEmptys(&s)){Pop(&s,&a);EnterQueue(q,a);}}void main(){SeqQueue q;//定义队列q定义字符变量temp char str[50],temp; //定义字符数组str[50],int i; //定义整型变量iInitQueue(&q); //初始化队列q请输入队列内容：\0");printf("gets(str); //输入字符串for(i=0;str[i]!='\0';i++){temp=str[i]; //输出字符的每一个字符字符串每一个字符入队qEnterQueue(&q,temp);//}printf("\n");proc(&q); //调用proc函数,传递队列q的地址 while(!IsEmpty(&q)) //while循环,如果队列不为空则循环 {DeleteQueue(&q,&temp); //出队,出队值存放于temp变量中printf("%c",temp);//输出temp变量值}printf("\n");}2.利用上一题的队列逆置函数（返回值、函数参数及部分语句稍作修改），编写一个程序，完成判断回文序列的程序。

数据结构栈和队列实验报告数据结构栈和队列实验报告1.实验目的本实验旨在通过设计栈和队列的数据结构，加深对栈和队列的理解，并通过实际操作进一步掌握它们的基本操作及应用。

2.实验内容2.1 栈的实现在本实验中，我们将使用数组和链表两种方式实现栈。

我们将分别实现栈的初始化、入栈、出栈、判断栈是否为空以及获取栈顶元素等基本操作。

通过对这些操作的实现，我们可将其用于解决实际问题中。

2.2 队列的实现同样地，我们将使用数组和链表两种方式实现队列。

我们将实现队列的初始化、入队、出队、判断队列是否为空以及获取队头元素等基本操作。

通过对这些操作的实现，我们可进一步了解队列的特性，并掌握队列在实际问题中的应用。

3.实验步骤3.1 栈的实现步骤3.1.1 数组实现栈（详细介绍数组实现栈的具体步骤）3.1.2 链表实现栈（详细介绍链表实现栈的具体步骤）3.2 队列的实现步骤3.2.1 数组实现队列（详细介绍数组实现队列的具体步骤）3.2.2 链表实现队列（详细介绍链表实现队列的具体步骤）4.实验结果与分析4.1 栈实验结果分析（分析使用数组和链表实现栈的优缺点，以及实际应用场景）4.2 队列实验结果分析（分析使用数组和链表实现队列的优缺点，以及实际应用场景）5.实验总结通过本次实验，我们深入了解了栈和队列这两种基本的数据结构，并利用它们解决了一些实际问题。

我们通过对数组和链表两种方式的实现，进一步加深了对栈和队列的理解。

通过实验的操作过程，我们也学会了如何设计和实现基本的数据结构，这对我们在日后的学习和工作中都具有重要意义。

6.附件6.1 源代码（附上栈和队列的实现代码）6.2 实验报告相关数据（附上实验过程中所产生的数据）7.法律名词及注释7.1 栈栈指的是一种存储数据的线性数据结构，具有后进先出(LIFO)的特点。

栈的操作主要包括入栈和出栈。

7.2 队列队列指的是一种存储数据的线性数据结构，具有先进先出(FIFO)的特点。

队列实验报告java实验报告：队列的实现与操作一、实验目的本次实验旨在通过Java编程语言实现队列（Queue）数据结构，并掌握队列的基本操作，包括入队（enqueue）、出队（dequeue）、查看队首元素（peek）等。

二、实验内容1.实现队列数据结构2.实现队列的基本操作：入队、出队、查看队首元素3.测试队列的功能，包括顺序入队、顺序出队、逆序入队、逆序出队等三、实验步骤与代码实现1.实现队列数据结构首先，我们定义一个队列类（Queue），其中包含一个存储队列元素的数组（elements）和一个记录队首元素位置的变量（head）。

代码如下：java复制代码public class Queue {private int[] elements;private int head;private int size;public Queue(int capacity){elements = newint[capacity];head = -1;size = 0;}}1.实现队列的基本操作接下来，我们实现队列的基本操作，包括入队、出队、查看队首元素等。

代码如下：java复制代码public class Queue {private int[] elements;private int head;private int size;public Queue(int capacity) {elements = new int[capacity];head = -1;size = 0;}// 入队操作public void enqueue(int value) {if (size == elements.length) {System.out.println("Queue is full.");return;}if (head == -1) { // 队列为空时，头指针为-1，将头指针和数组第一个位置都赋值为新元素，size加1。

数据结构队列实验报告队列实验报告小组成员：xxxxxxxx日期：xxxxxxxx一、需求分析（xxx）1.链队列1）在本演示程序中，首先要链队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。

最后销毁队列，释放空间。

2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“销毁队列”“清空队列”之后。

由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。

3）程序执行的命令包括：欢迎来到链队列1输出队列长度2元素入队3元素出队4销毁队列5清空队列6对头元素7退出链队列4）测试数据入队 12345分别执行“元素入队”“元素出队”“销毁队列”“清空队列”等操作。

2.顺序队列1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。

2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。

由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。

3）程序执行的命令包括：欢迎来到顺序队列1入队2出队3判断是否为空4取得头结点5输出显示6退出顺序队列4）测试数据入队 12345分别执行“元素入队”“元素出队”等操作。

3循环队列1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，初始化建空队列时，“头指针增1”。

令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。

数据结构实验报告之栈和队列1. 编写程序实现顺序栈的各种基本运算：初始化、销毁、清空、判断是否为空栈、求栈的长度、取栈顶元素、进栈、出栈。

在此基础上设计⼀个主程序完成如下功能：（1）初始化栈s；（2）判断栈s是否为空；（3）依次进栈元素a，b，c，d；（4）判断栈s是否为空；（5）输出栈s的长度；（6）栈⾥元素依次出栈,并输出；（7）销毁栈s。

#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef char SElemType;#define STACK_INIT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量typedef struct {SElemType *base; //栈底指针SElemType *top; //栈顶指针int stacksize; //当前已分配的存储空间} SqStack;Status InitStack(SqStack &S) { //构造⼀个空栈SS.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}//InitStackStatus StackLength(SqStack S) {return S.top - S.base;}//StackLengthStatus DestoryStack(SqStack &S) {S.top = S.base;free(S.base);//若base的值为NULL，则表明栈结构不存在S.base = NULL;S.top = NULL;S.stacksize = 0;return OK;}Status StackEmpty(SqStack S) {if (S.top == S.base)return1;elsereturn0;}//StackEmptyStatus GetTop(SqStack S, SElemType &e) {if (S.top == S.base) return ERROR;e = *(S.top - 1);return OK;}//GetTopStatus Push(SqStack &S, SElemType e) {if (S.top - S.base >= S.stacksize) {S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));if (!S.base)exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize+= STACKINCREMENT;}*S.top++=e;return OK;}//PushStatus Pop(SqStack &S, SElemType &e) {//判断栈是否为空if (S.base == S.top)return ERROR;e = *(S.top - 1);S.top--;return OK;}//Popvoid main(){SqStack s;SElemType e;printf("(1)初始化栈\n");InitStack(s);printf("(2)The stack is ");if (StackEmpty(s))printf("empty.\n");elseprintf("not empty.\n");printf("(3)依次进栈元素a，b，c，d\n");Push(s, 'a');Push(s, 'b');Push(s, 'c');Push(s, 'd');printf("(4)The stack is ");if (StackEmpty(s))printf("empty.\n");elseprintf("not empty.\n");printf("(5)The length of the stack is %d\n", StackLength(s));printf("(6)The stack is ");while (!StackEmpty(s)){Pop(s, e);printf("%c \n", e);}printf("(7)销毁栈s");DestoryStack(s);}运⾏结果：2. 编写程序实现链队列的各种基本运算：初始化、销毁、清空、判断是否为空队列、求队列的长度、取队列的头元素、⼊队、出队。

数据结构队列实验报告实验报告：数据结构队列一、引言数据结构是计算机科学中的重要概念，它用于组织和存储数据，使得数据的访问和操作更加高效。

队列是一种常见的数据结构，它遵循先进先出（FIFO）的原则，类似于现实生活中的排队等候。

本实验旨在通过实现队列的基本操作，加深对数据结构队列的理解，并掌握队列的应用。

二、实验目的1. 理解队列的概念和特点；2. 掌握队列的基本操作，包括入队、出队、判空、判满等；3. 熟悉队列的应用场景。

三、实验内容1. 实现队列的基本操作函数；2. 设计测试用例，验证队列的功能和正确性；3. 分析队列的时间复杂度。

四、实验步骤1. 定义队列的数据结构：- 使用数组作为队列的存储结构；- 定义队列的最大长度；- 定义队列的头指针和尾指针。

2. 实现队列的基本操作函数：- 初始化队列：设置头指针和尾指针为-1；- 判空操作：判断头指针和尾指针是否相等，相等则队列为空；- 判满操作：判断尾指针是否等于最大长度减一，相等则队列已满；- 入队操作：将元素插入队尾，并更新尾指针；- 出队操作：将队头元素删除，并更新头指针；- 获取队头元素：返回队头元素的值。

3. 设计测试用例：- 针对队列的各种操作编写测试用例，包括正常情况和异常情况；- 测试用例应覆盖队列的各种操作，包括入队、出队、判空、判满等。

4. 进行测试：- 使用设计的测试用例对队列的功能和正确性进行验证；- 检查程序输出结果是否符合预期；- 分析测试结果，发现并修复可能存在的问题。

五、实验结果与分析1. 队列的功能和正确性经过测试验证，符合预期；2. 队列的时间复杂度分析：- 入队操作的时间复杂度为O(1)；- 出队操作的时间复杂度为O(1)；- 判空操作的时间复杂度为O(1)；- 判满操作的时间复杂度为O(1)；- 获取队头元素的时间复杂度为O(1)。

六、实验总结通过本次实验，我深入理解了数据结构队列的概念和特点，掌握了队列的基本操作，并熟悉了队列的应用场景。

一、实验目的1. 理解队列的概念和特点；2. 掌握队列的基本操作，包括入队、出队、查看队列头元素等；3. 能够使用队列解决实际问题。

二、实验环境1. 操作系统：Windows 10；2. 编程语言：C语言；3. 开发环境：Visual Studio 2019。

三、实验内容1. 队列的定义和实现；2. 队列的基本操作；3. 使用队列解决实际问题。

四、实验步骤1. 队列的定义和实现（1）定义队列的数据结构```c#define MAXSIZE 100 // 队列的最大容量typedef struct {int data[MAXSIZE]; // 队列的存储空间int front; // 队列头指针int rear; // 队列尾指针} Queue;```（2）初始化队列```cvoid InitQueue(Queue q) {q->front = 0;q->rear = 0;}```（3）判断队列是否为空```cint IsEmpty(Queue q) {return q->front == q->rear;}```（4）判断队列是否已满```cint IsFull(Queue q) {return (q->rear + 1) % MAXSIZE == q->front; }```2. 队列的基本操作（1）入队操作```cint EnQueue(Queue q, int x) {if (IsFull(q)) {return 0; // 队列已满}q->data[q->rear] = x;q->rear = (q->rear + 1) % MAXSIZE; return 1;}```（2）出队操作```cint DeQueue(Queue q, int x) {if (IsEmpty(q)) {return 0; // 队列为空}x = q->data[q->front];q->front = (q->front + 1) % MAXSIZE; return 1;}```（3）查看队列头元素```cint GetHead(Queue q, int x) {if (IsEmpty(q)) {return 0; // 队列为空}x = q->data[q->front];return 1;}```3. 使用队列解决实际问题（1）实现一个简单的函数，将一个整数数组中的元素按照逆序输出```cvoid ReversePrint(int arr[], int n) {Queue q;InitQueue(&q);for (int i = 0; i < n; i++) {EnQueue(&q, arr[i]);}int x;while (!IsEmpty(&q)) {DeQueue(&q, &x);printf("%d ", x);}printf("\n");}```（2）实现一个函数，计算两个整数序列的交集```cvoid Intersection(int arr1[], int n1, int arr2[], int n2, int result[]) {Queue q;InitQueue(&q);for (int i = 0; i < n1; i++) {EnQueue(&q, arr1[i]);}int x;int i = 0, j = 0;while (!IsEmpty(&q)) {DeQueue(&q, &x);while (i < n2 && arr2[i] < x) {i++;}if (i < n2 && arr2[i] == x) {result[j++] = x;}}result[j] = 0; // 标记交集结束}```五、实验结果与分析1. 实验结果（1）定义队列的数据结构（2）初始化队列（3）判断队列是否为空（4）判断队列是否已满（5）入队操作（6）出队操作（7）查看队列头元素（8）使用队列逆序输出整数数组（9）使用队列计算两个整数序列的交集2. 实验分析通过本次实验，我们掌握了队列的基本概念、数据结构、操作方法以及在实际问题中的应用。

实验一队列操作程序设计与调试一、实验目的1．掌握栈和队列的存储结构。

2．掌握栈和队列的特点。

2．掌握栈和队列的基本运算。

二、实验条件1．硬件：一台微机2．软件：操作系统和C语言（或VC++）环境三、实验原理1．栈和队列是两种特殊的线性表，它们是运算要受到某些限制的线性表，因此也称为限定性的数据结构。

2．栈是限定只有在表的一端进行插入和删除的线性表，允许插入和删除的一端叫栈顶（top），不允许插入和删除的一端为栈底（bottom）。

由于只能在一端进行，因此后进入的元素只能先退出，这种结构也叫做“后进先出(Last In First Out ,LIFO)”表。

3.队列是一种先进先出(First In First Out, FIFO)的线性表，只允许在表的一端进行插入，而在另一端删除元素。

四、实验内容设栈S为空，队Q的状态是abcd，其中a为队首元素，d为队尾元素，经过下面两个操作后，给出队Q的状态，用程序实现，并显示结果。

（1）删除队Q中的元素，将删除的元素插入栈S，直到队Q为空。

（2）依次将栈S中的元素插入队Q，直到栈S为空。

五、预习要求实验前学生必须明确实验内容及实验目的，须持实验预习报告后（提前编制好程序），方可进入实验室进行实验。

六、实验步骤1.根据实验内容设计程序流程图；2.根据流程图完成主程序设计；3.完成入队子程序设计；4.完成出队子程序设计；5.完成进栈子程序设计；6.完成出栈子程序设计；7.调试程序；8.给出运行结果。

七、实验报告要求1. 按要求设计程序流程图；a)根据流程图编写程序；b)写出程序运行结果。

八、思考题1．队列出队和入队的位置有什么不同？2. 如何实现循环队列?参考程序：#define stacksize 10#define MAX 6void main(){int S[stacksize], Q[MAX]={'a','b','c','d','e'}; /*栈数组S，队列数组Q*/ int top=0, front=MAX-1, rear=4; /*栈顶指针, 队头指针, 队尾指针*/ int py; int i;for (i=0; i<5; i++){DeQueue(Q, &py, &front, &rear); /*出队*/push(S, py, &top); /*入栈*/}for (i=0; i<5; i++){ pop(S, &top, &py); /*出栈*/EnQueue(Q, py, &front, &rear); /*入队*/}printf("\nThe queue is : ");{ /*队中数据循环存储*/for (i=front+1; i<MAX; i++)printf("%c ", Q[i]);for (i=0; i<=rear; i++)printf("%c ", Q[i]);}}int EnQueue(int Q[ ],int x, int *pf, int *pr) /*入队*/{ int front,rear;front=*pf; rear=*pr;if((rear+1)%MAX==front) return(0);else{ rear=(rear+1)%MAX;Q[rear]=x;*pr=rear;return(0); }}int DeQueue(int Q[ ], int *py, int *pf, int *pr) /*出队*/ { int front, rear;front=*pf; rear=*pr;if(rear==front) return(0);else{ front=(front+1)%MAX;*py=Q[front];*pf=front;return(0); }}。

《算法与数据结构》课程一、实验目的掌握队列的存储结构及进队/出队等操作的实现。

二、实验内容及要求1.实现队列的一种存储结构。

2.实现队列的相关操作。

3.利用队列的操作特点，借助进队与出队操作完成打印二项式系数的任务。

三、系统分析（1）数据方面：该队列数据元素类型采用整型，在此基础上进行队列的一些基本操作，应用体现在打印二项式系数即打印杨辉三角形。

（2）功能方面：1.进队操作：若队列不满，则将元素x进入队列。

2.出队操作：若队列不空，则退出队头元素x并由函数返回true，否则返回false。

3.获取队头元素：若队列不为空，则函数返回true及队头元素的值，否则返回false。

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

5.计算队列中元素个数：直接返回队列中元素个数。

6.清空队列内容：队头指针和队尾指针置0。

7.打印杨辉三角形前n行数字。

四、系统设计（1）设计的主要思路队列得基于数组得存储表示亦称为顺序队列，是利用一个一维数组作为队列元素的存储结构，并且设置两个指针front和rear，分别指示队列的队头和队尾位置。

每当添加一个新元素时，先将新元素添加到rear所指位置，再让队尾指针rear进1。

每当退出队头元素，应当先把front所指位置元素记录下来，再让队头指针进1，指示下一队头元素位置，最后把记录下来的元素值返回。

但当队头指针front==rear，队列为空；而当rear==maxSize时，队列满，如果再加入新元素，就会产生“溢出”。

但这种“溢出”可能时假溢出，因为在数组的前端可能还有空位置。

为了能够充分地使用数组中的存储空间，把数组的前端和后端连接起来，形成一个环形表，即把存储队列元素的表从逻辑上看成一个环，成为循环队列。

循环队列的首尾相接，当队头指针front和队尾指针rear进到maxSize-1后，再前进一个位置就自动到0.这可以利用除法取余的运算实现。

（2）数据结构的设计队列的定义是一种限定存取位置的线性表。