实验二 栈和队列

实验二栈和队列的基本操作实现及其应用一、实验目的1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。

2、会用栈和队列解决简单的实际问题。

二、实验内容（可任选或全做）题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。

所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。

相关常量及结构定义：# define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define OK 1# define ERROR 0typedef int SElemType;//栈类型定义typedef struct SqStack{ SElemType *base;SElemType *top;int stacksize;}SqStack;设计相关函数声明：判断函数：int IsReverse()栈：int InitStack(SqStack &S )int Push(SqStack &S, SElemType e )int Pop(SqStack &S,SElemType &e)int StackEmpty(s)题目二、编程模拟队列的管理，主要包括：出队列、入队、统计队列的长度、查找队列某个元素e、及输出队列中元素。

[实现提示]：参考教材循环队列的有关算法，其中后两个算法参考顺序表的实现。

题目三、RailsDescriptionThere is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited thattime. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, ..., N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, ..., aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.InputThe input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0.The last block consists of just one line containing 0.OutputThe output contains the lines corresponding to the lines with permutations in the input.A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition,there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null'' block of the input. Sample Input51 2 3 4 55 4 1 2 366 5 4 3 2 1Sample OutputYesNoYes题目四、Sliding WindowDescriptionAn array of size n≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:The array is [1 3 -1 -3 5 3 6 7], and k is 3.Window position Minimum value Maximum value[1 3 -1] -3 5 3 6 7 -131 [3 -1 -3] 5 3 6 7 -331 3 [-1 -3 5] 3 6 7 -351 3 -1 [-3 5 3] 6 7 -351 3 -1 -3 [5 3 6] 7 361 3 -1 -3 5 [3 6 7]37Your task is to determine the maximum and minimum values in the sliding window at each position.InputThe input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.OutputThere are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.Sample Input8 31 3 -1 -3 5 3 6 7Sample Output-1 -3 -3 -3 3 33 3 5 5 6 7题目五（选作考查串知识）DNA Evolution【Description】Evolution is a seemingly random process which works in a way which resembles certain approaches we use to get approximate solutions to hard combinatorial problems. You are now to do something completely different.Given a DNA string S from the alphabet {A,C,G,T}, find the minimal number of copy operations needed to create another string T. You may reverse the strings you copy, and copy both from S and the pieces of your partial T. You may put these pieces together at any time. You may only copy contiguous parts of your partial T, and all copied strings must be used in your final T.Example: From S= “ACTG” create T= “GTACTAATAAT”1.Get GT......... by copying and reversing "TG" from S.2.Get GT AC... by copying "AC" from S.3.Get GTAC TA….. by copying "TA" from the partial T.4.Get GTACTA AT by copying and reversing "TA" from the partial T.5.Get GTACTAAT AAT by copying "AAT" from the partial T.【Input】The first line of input gives a single integer, 1 ≤k≤10, the number of test cases. Then follow, for each test case, a line with the string S , length of S is less then 19, and a line with the string T , length of T is less then 19.【Output】Output for each test case the number of copy operations needed to create T from S, or "impossible" if it cannot be done.【Sample Input】4ACGTTGCAACACGTTCGATCGAAAAAAAAAAAAAAAAAAAA【Sample output】1impossible46题目六（选作考查数组知识）Magic Squares描述Following the success of the magic cube, Mr. Rubik invented its planar version, called magic squares. This is a sheet composed of 8 equal-sized squares:1 2 3 48 7 6 5In this task we consider the version where each square has a different color. Colors are denoted by the first 8 positive integers. A sheet configuration is given by the sequence of colors obtained by reading the colors of the squares starting at the upper left corner and going in clockwise direction. For instance, the configuration of Figure 3 is given by the sequence (1,2,3,4,5,6,7,8). This configuration is the initial configuration.Three basic transformations, identified by the letters `A', `B' and `C', can be applied to a sheet:∙'A': exchange the top and bottom row,∙'B': single right circular shifting of the rectangle,∙'C': single clockwise rotation of the middle four squares.Below is a demonstration of applying the transformations to the initial squares given above:A:8 7 6 51 2 3 4B:4 1 2 35 8 7 6C:1 72 48 6 3 5All possible configurations are available using the three basic transformations.You are to write a program that computes a minimal sequence of basic transformations that transforms the initial configuration above to a specific target configuration.输入A single line with eight space-separated integers (a permutation of (1..8)) that are the target configuration.输出样例输入2 6 8 4 5 73 1样例输出7BCABCCB三、实验步骤㈠、数据结构与核心算法的设计描述㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结四、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）//int IsReverse(){ ….while( (e=getchar())!='@'){e 依次入栈、入队 //push(S,e);EnQueue(Q,e);……..}While(!StackEmpty(S)) { pop(S,a);DeQueue(Q,b);If(a!=b) return 0;}return 1;}。

数据结构
实验题目
9.简单背包问题 问题描述 设一个背包所允许的重量是M，假设有N件物品， 物品的重量分别是Wi，可以任意挑选物品将背包装满。 实验要求 设计程序实现将给定背包装满的可能解。 1)采用栈等数据结构。 2)应用穷举法回溯策略求解。 3)尝试采用递归和非递归算法求解。
数据结构
实验题目
7.八皇后问题 问题描述 设一个8×8的棋盘里放置8个皇后，要求在每行、 每列、没斜线只允许放置1个皇后。 实验要求 设计实现所有可能解的程序。 1)采用栈等数据结构。 2)应用穷举法回溯策略求解。 3)尝试采用递归和非递归算法求解。
数据结构
实验题目
8.马踏棋盘问题 问题描述 中国象棋中的“马”走子的规则是：马走日字形。 实验要求 设计实现求象棋盘中的某一点出发踏遍棋盘所有点 的程序。 1)采用栈等数据结构。 2)应用穷举法回溯策略求解。 3)尝试求解所有出发点的可能 解。
数据结构
实验题目
3.运动员混合双打组合 问题描述 设有M个男羽毛球运动员和N个女羽毛球运动员，现 进行男女混合双打组合K轮配对。男女运动员分别编号 排队在等候队列，按顺序依次从男女运动员中各出队1 人组合配对。本轮没成功配对者等待下一轮次配对。
数据结构
实验题目
3.运动员混合双打组合 实验要求 设计程序模拟完成运动员组合配对过程。 1)采用队列等数据结构。 2)输出每轮的配对信息。
数据结构实验
LOGO
数据结构
实验二
实验题目
栈和队列应用
1.算术表达式求值 问题描述 由输入的四则算术表达式字符串，动态生成算术表 达式所对应的后缀式，通过后缀式求值并输出。
数据结构 实验题目
1.算术表达式求值 实验要求 十进制整数四则运算计算器。

数据结构栈和队列实验报告实验报告：数据结构栈和队列一、实验目的1.了解栈和队列的基本概念和特点；2.掌握栈和队列的基本操作；3.掌握使用栈和队列解决实际问题的方法。

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

三、实验原理1.栈的定义和特点：栈是一种具有后进先出(LIFO)特性的线性数据结构，不同于线性表，栈只能在表尾进行插入和删除操作，称为入栈和出栈操作。

2.队列的定义和特点：队列是一种具有先进先出(FIFO)特性的线性数据结构，不同于线性表，队列在表头删除元素，在表尾插入元素，称为出队和入队操作。

3.栈的基本操作：a.初始化：建立一个空栈；b.入栈：将元素插入栈的表尾；c.出栈：删除栈表尾的元素，并返回该元素；d.取栈顶元素：返回栈表尾的元素，不删除。

4.队列的基本操作：a.初始化：建立一个空队列；b.入队：将元素插入队列的表尾；c.出队：删除队列表头的元素，并返回该元素；d.取队头元素：返回队列表头的元素，不删除。

四、实验步骤1.栈的实现：a.使用数组定义栈，设置栈的大小和栈顶指针；b.实现栈的初始化、入栈、出栈和取栈顶元素等操作。

2.队列的实现：a.使用数组定义队列，设置队列的大小、队头和队尾指针；b.实现队列的初始化、入队、出队和取队头元素等操作。

3.使用栈解决实际问题：a.以括号匹配问题为例，判断一个表达式中的括号是否匹配；b.使用栈来实现括号匹配，遍历表达式中的每个字符，遇到左括号入栈，遇到右括号时将栈顶元素出栈，并判断左右括号是否匹配。

4.使用队列解决实际问题：a.以模拟银行排队问题为例，实现一个简单的银行排队系统；b.使用队列来模拟银行排队过程，顾客到达银行时入队，处理完业务后出队，每个顾客的业务处理时间可以随机确定。

五、实验结果与分析1.栈和队列的基本操作实现：a.栈和队列的初始化、入栈/队、出栈/队以及取栈顶/队头元素等操作均能正常运行；b.栈和队列的时间复杂度均为O(1)，操作效率很高。

实验二栈和队列的应用——数值转换器
实验目的：
本实验的目的是使学生深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，熟练掌握顺序存储映像和链式映像中各类基本操作的实现。

实验要求：
从键盘输入一个10进制数，编程将其转换成16进制数，并输出。

要求实现下列函数：
(1) 实现链栈的各个基本操作函数；
(2) Transfer( )函数实现进制转换工作；
(3) main( )函数进行调用。

[实现提示]
输入：10进制整数
输出：16进制数（由数字0~9和字符A~F组成）
[测试数据]
由学生自己确定，注意边界数据。

程序运行结果：
程序源码：（后付纸）
实验心得体会：十进制转化为十六进制的方法选用了十进制数除以十六取余，因为最先求出来的余数是个位，然后是百位千位等，所以又用到了栈，使得计数单位最大的最先输出。

判断了如果从11到15就用A-B替换。

实验二栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验内容本次实验提供2个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况任选一个！题目一：回文判断（*）[问题描述]对于一个从键盘输入的字符串，判断其是否为回文。

回文即正反序相同。

如“abba”是回文，而“abab”不是回文。

[基本要求]（1）数据从键盘读入；（2）输出要判断的字符串；（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“ok”，否则输出“fail”。

程序源代码如下：/**********************************用栈和队列进行回文判断输入字符以@结束***********************************/#include <stdio.h>/*定义一个栈*/typedef struct Stack{int size;char * Base;char * Top;}Stack;/*创建一个栈*/void CreateStack(Stack * S,int size) {S -> size = size;S -> Base = (char *)malloc(size);S -> Top = S -> Base;}/*推入一个元素*/void Push(Stack * S,char c){/*栈满了，不能插入了*/if(S -> Top - S -> Base == S -> size) {printf("Stack is full and can't push!"); return;}else{*(++S -> Top) = c;}}void Pop(Stack * S){/*栈空了*/if(S -> Top == S -> Base){printf("Stack is empty!");return;}else{S -> Top--;}}void main(){Stack S;int Begin;char c;CreateStack(&S,100);Begin = 0;while(1){scanf("%c",&c);if(c == '@')break;if(c == '&' && !Begin){Begin = 1;continue;}if(Begin){if(*(S.Top) == c){Pop(&S);}}elsePush(&S,c);}if(S.Top == S.Base){printf("ok\n");}else{printf("fail\n");}getch();}运行结果如下：图中的“ok”表示是回文，“fail”表现不是回文。

栈和队列基本操作实验报告实验目的1. 了解栈和队列的基本概念和特点；2. 掌握栈和队列的基本操作，包括插入、删除、判空、判满等；3. 加深对数据结构的理解，提高编程能力。

实验原理1. 栈(Stack)是一种“先进后出”(Last In First Out，简称LIFO)的数据结构，类似于一摞盘子，最先放入的盘子在最底下，最后放入的盘子在最上面，取出盘子时也是从上往下取出。

2. 队列(Queue)是一种“先进先出”(First In First Out，简称FIFO)的数据结构，类似于排队，先来的人先进队列，后来的人排在后面，服务员按照队列顺序依次为每个人提供服务。

实验内容1. 栈的实现栈的基本操作包括入栈(push)、出栈(pop)、判空(empty)、栈顶(top)。

本次实验选择使用顺序栈来实现，并通过代码模拟栈的基本操作。

在顺序栈的实现中，需要设置栈顶指针(top)、初始化栈、入栈、出栈、判空、判满等操作，其中最关键的是入栈和出栈操作。

入栈操作：在栈顶指针(top)的位置加1，将元素e放到栈顶```void push(SqStack &s, ElemType e){if (s.top == MAXSIZE - 1) // 栈满return;s.top++; // 栈顶指针加1s.data[s.top] = e; // 将元素e放到栈顶return;}```出队操作：将队头元素弹出，队头指针(front)加1实验结果1. 栈的实现通过栈的实现，我们可以进行压入和弹出元素的操作。

下面是一段示例代码：通过本次实验，我学会了栈和队列的基本概念和特点，掌握了栈和队列的基本操作，如插入、删除、判空、判满等。

这些基本操作是数据结构中的重要部分，对于算法的实现与性能优化都有很大的帮助。

此外，在实现中，我们还需要注意栈和队列指针的变化，以及对于空栈和空队列的处理。

通过本次实验，我加深了对数据结构的理解，同时也提升了编程能力。

实验2：栈和队列的应用
一、实验目的
1.掌握栈的表示与实现
2.掌握队列的表示与实现
3.掌握栈的入栈、出栈等基本操作
4.掌握队列的入队、出队等基本操作
二、实验内容
1.实现顺序栈各种基本运算的算法，具体操作要求如下：
（1）初始化栈，并判断栈是否为空；
（2）对a,b,c,d,f五个字符元素模拟进栈操作；并判断栈是否为空；
（3）取出栈顶元素；
（4）对a,b,c,d,f五个字符元素做依次出栈操作，并判断栈是否为空；
（5）释放栈。

具体效果如下：
注：若sqstack.cpp文件中的方法不合适，可以作修改。

2.实现链栈各种基本运算的算法
（1）初始化栈，并判断栈是否为空；
（2）对a,b,c,d,f五个字符元素模拟进栈操作；并判断栈是否为空；
（3）取出栈顶元素；
（4）对a,b,c,d,f五个字符元素做依次出栈操作，并判断栈是否为空；
（5）释放栈。

注：若listack.cpp文件中的方法不合适，可以作修改。

三、实验要求
1.独立完成实验程序的编写与调试；
2.实验完成后填写实验报告，学习委员按学号从小到大的顺序提交。

四、思考题
1.读入一个有限大小的整数n，然后按输入次序的相反次序输出各元素的值。

(用顺序栈
实现)
2.利用栈完成数制转换。

任意输入一个十进制数，将其转换成八进制数。

(用顺序栈实
现)。

栈和队列实验报告总结一、实验目的本次实验的主要目的是掌握栈和队列这两种数据结构的基本概念和操作方法，以及了解它们在计算机程序设计中的应用。

二、实验原理1. 栈栈是一种后进先出（LIFO）的数据结构，它可以看作是一种线性表。

栈顶指针指向栈顶元素，每次插入或删除元素时，都会改变栈顶指针的位置。

常见的操作有入栈（push）、出栈（pop）、取栈顶元素（top）等。

2. 队列队列是一种先进先出（FIFO）的数据结构，它也可以看作是一种线性表。

队头指针指向队头元素，队尾指针指向队尾元素。

常见的操作有入队（enqueue）、出队（dequeue）、取队头元素（front）等。

三、实验内容与步骤1. 栈本次实验中我们需要完成以下操作：① 初始化一个空栈；② 将10个整数依次压入栈中；③ 弹出3个整数并输出；④ 将5个整数依次压入栈中；⑤ 弹出所有整数并输出。

具体步骤如下：Step 1：定义一个Stack类，并在其中定义初始化、入栈、出栈、取栈顶元素等方法；Step 2：在主函数中创建一个Stack对象，并调用初始化方法；Step 3：使用循环将10个整数依次压入栈中；Step 4：使用循环弹出3个整数并输出；Step 5：使用循环将5个整数依次压入栈中；Step 6：调用出栈方法弹出所有整数并输出。

2. 队列本次实验中我们需要完成以下操作：① 初始化一个空队列；② 将10个整数依次加入队列中；③ 弹出3个整数并输出；④ 将5个整数依次加入队列中；⑤ 弹出所有整数并输出。

具体步骤如下：Step 1：定义一个Queue类，并在其中定义初始化、入队、出队、取队头元素等方法；Step 2：在主函数中创建一个Queue对象，并调用初始化方法；Step 3：使用循环将10个整数依次加入队列中；Step 4：使用循环弹出3个整数并输出；Step 5：使用循环将5个整数依次加入队列中；Step 6：调用出队方法弹出所有整数并输出。

实验报告——栈和队列的应用第一篇：实验报告——栈和队列的应用实验5 栈和队列的应用目的和要求：（1）熟练栈和队列的基本操作；（2）能够利用栈与队列进行简单的应用。

一、题目题目1.利用顺序栈和队列，实现一个栈和一个队列，并利用其判断一个字符串是否是回文。

所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。

例如，a+b&b+a等等。

题目2.假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。

跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。

若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。

现要求写一算法模拟上述舞伴配对问题，并实现。

题目3.打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。

每台打印机具有一个队列（缓冲池），用户提交打印请求被写入到队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除之。

请利用队列的先进先出特性，完成打印机网络共享的先来先服务功能。

题目4.假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。

试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

题目5.利用循环链队列求解约瑟夫环问题。

请大家从本组未讨论过的五道题中选择一道，参照清华邓俊辉老师MOOC视频及课本相关知识，编写相应程序。

选择题目3：打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。

二、程序清单//Ch3.cpp #include #include #include“ch3.h” template void LinkedQueue::makeEmpty()//makeEmpty//函数的实现{ LinkNode*p;while(front!=NULL)//逐个删除队列中的结点{p=front;front=front->link;delete p;} };template bool LinkedQueue::put_in(T&x）{//提交命令函数if(front==NULL){//判断是否为空front=rear=new LinkNode;//如果为空，新结点为对头也为对尾front->data=rear->data=x;if(front==NULL)//分配结点失败return false;} else{rear->link=new LinkNode;//如不为空，在链尾加新的结点rear->link->data=x;if(rear->link==NULL)return false;rear=rear->link;} return true;};template bool LinkedQueue::carry_out()//执行命令函数 { if(IsEmpty()==true)//判断是否为空{return false;} cout<data<LinkNode*p=front;front=front->link;//删除以执行的命令，即对头修改delete p;//释放原结点return true;};void main()//主函数 { LinkedQueue q;//定义类对象char flag='Y';//标志是否输入了命令const int max=30;//一次获取输入命令的最大个数while(flag=='Y')//循环{ int i=0;char str[max];//定义存储屏幕输入的命令的数组gets(str);//获取屏幕输入的命令while(str[i]!=''){q.put_in(str[i]);//调用提交命令函数，将每个命令存入队列中i++;}for(int j=0;j<=i;j++){if(q.IsEmpty()==true)//判断是否为空，为空则说明没有可执行的命令{cout<cin>>flag;continue;//为空跳出for循环为下次输入命令做好准备}q.carry_out();//调用执行命令的函数，将命令打印并删除}三、程序调试过程中所出现的错误无。

栈和队列实验报告实验名称：栈和队列的实验研究摘要：本实验旨在通过设计并实现基于栈和队列的算法，探索其在数据结构和算法中的应用。

通过实验比较栈和队列的性能差异和适用场景，加深对栈和队列的理解和应用。

实验结果表明，栈和队列在不同的问题场景中具有不同的优势和适用性。

关键词：栈、队列、数据结构、算法、应用一、引言栈和队列是数据结构中常见且重要的两种数据结构，它们分别以LIFO（Last In First Out，后进先出）和FIFO（First In First Out，先进先出）的方式操作数据，广泛应用于各领域的编程和算法设计中。

本实验通过实现栈和队列相关操作的算法，探索它们在实际应用中的效率和优势。

二、实验设计与实现1.实验设计本实验采用C++语言来实现栈和队列的操作，并编写相应的算法来解决一些典型问题。

实验将比较栈和队列在以下几个方面的性能差异：a)插入操作的性能b)删除操作的性能c)查询操作的性能d)栈和队列的空间占用情况2.实验步骤a)设计栈的数据结构和相关操作的算法。

b)设计队列的数据结构和相关操作的算法。

c)分别使用栈和队列来解决一个典型问题，并比较它们的效率。

d)分析实验结果，总结栈和队列的适用场景和优势。

三、实验结果与分析1.栈的性能比较在本次实验中，我们使用栈来解决斐波那契数列问题。

首先，我们设计了一个栈的数据结构，并实现了如下操作：a) 入栈（push）：将元素添加到栈顶。

b) 出栈（pop）：将栈顶元素移出栈。

c) 查询栈顶元素（top）：返回栈顶元素。

对比使用数组和链表实现栈的性能，我们发现使用链表实现的栈在插入和删除操作上有更好的性能表现，而使用数组实现的栈在查询操作上更高效。

这是因为使用链表实现的栈不需要移动大量元素，而使用数组实现的栈可以通过索引直接访问任意位置的元素。

2.队列的性能比较在本次实验中，我们使用队列来解决击鼓传花问题。

首先，我们设计了一个队列的数据结构，并实现了如下操作：a) 入队（enqueue）：将元素添加到队列末尾。

S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!S.base)
{cout<<"新分配空间失败！！！"<<endl;
exit(0);
}
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
i++;
break;
case 2:
Pop(Stack,x);
cout<<x<<"出栈"<<endl;
break;
case 3:
cout<<"栈顶值为："<<endl;
GetTop(Stack,y);
break;
case 4:
ClearStack(Stack);
break;
case 5:
cout<<"Exit!!"<<endl;
exit(0);
}
e=*--S.top;
//cout<<"删除成功！！！"<<endl;
}//Pop
void ClearStack(SqStack &S){
//把S置为空栈
if(S.base==S.top)
cout<<"此栈已经为空!!!"<<endl;
S.top=S.base;
}//ClearStack
}
*S.top++=e;

实验⼆栈、队列的实现及应⽤实验⼆栈、队列的实现及应⽤实验课程名：数据结构与算法专业班级：学号：姓名：实验时间：实验地点：指导教师：冯珊⼀、实验⽬的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运⽤。

2、掌握栈和队列的特点，即先进后出与先进先出的原则。

3、掌握栈和队列的基本操作实现⽅法。

⼆、实验内容⼀、实验⽬的及要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运⽤。

2、掌握栈和队列的特点，即先进后出与先进先出的原则。

3、掌握栈和队列的基本操作实现⽅法。

⼆、实验学时2学时三、实验任务任务⼀：（1）实现栈的顺序存储（2）实现栈的链式存储。

任务⼆：实现顺序存储的循环队列，完成键盘缓冲区的功能。

四、实验重点、难点1.进栈、出栈栈顶指针都要改变。

2.队空、队满的条件及⼊队、出队时指针的变更。

五、操作内容与要求1.任务⼀（1）：完成下列程序，该程序实现栈的顺序存储结构，构建顺序栈（栈中的元素依次为R，S，Y，F，C，T），依次进⾏进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。

要求⽣成顺序栈时，从键盘上读取数据元素。

（1）源代码：#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10# define OK 1# define ERROR 0typedef char SElemType;/* 顺序栈的存储类型 */typedef struct//define structure SqStack()SElemType *base;SElemType *top;int stacksize;}SqStack;/*构造空顺序栈*/int InitStack(SqStack *S) //InitStack() sub-function{S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base){printf("分配空间失败!\n");return (ERROR);}S->top = S->base;S->stacksize = STACK_INIT_SIZE;printf("栈初始化成功！\n");return (OK);} //InitStack() end/*取顺序栈顶元素*/int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function{if (S->top == S->base){printf("栈为空!\n"); //if empty SqStackreturn (ERROR);}*e = *(S->top - 1);return (OK);} //GetTop() end/*将元素压⼊顺序栈*/int Push(SqStack *S) //Push() sub-function{SElemType e;if (S->top - S->base>S->stacksize)S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType)));if (!S->base){printf("存储空间分配失败!\n");return (ERROR);}S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;}fflush(stdin);//清除输⼊缓冲区，否则原来的输⼊会默认送给变量x printf("请输⼊要⼊栈的元素的值:");e = getchar();*S->top++ = e;return (OK);} //Push() end/* 将元素弹出顺序栈*/int Pop(SqStack *S, SElemType *e) //Pop() sub-function {if (S->top == S->base){printf("栈为空!\n");return (ERROR);}*e = *--S->top;return (OK);} //Pop() endvoid display(SqStack *s){if (s->top == s->base)printf("栈为空!\n");else{while (s->top != s->base){s->top = s->top - 1;}}printf("\n");}int main(){int choice;SElemType e;SqStack s;do{printf("===============================\n");printf(" 0:退出\n");printf(" 1:初始化栈\n");printf(" 2:⼊栈\n");printf(" 3:出栈\n");printf(" 4:读取栈顶元素\n");printf(" 5:显⽰栈中元素\n");printf("===============================\n");printf("输⼊操作选择代码(0-5):");scanf("%d", &choice);while(choice<0 || choice>5) { printf("输⼊有误，请重新输⼊(0-5):"); scanf("%d", &choice); } switch (choice){case 0:exit(1);case 1:InitStack(&s); break;case 2:printf("2\n"); Push(&s); break;case 3:Pop(&s, &e); printf("出栈元素的值是:%c\n", e); break;case 4:GetTop(&s, &e); printf("栈顶元素的值是:%c\n", e); break;case 5: printf("栈中元素的值是为：\n"); display(&s); break;}} while (choice);return 0;}（3）结果分析2.任务⼀（2）：完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China，Japan，France，India，Australia），依次进⾏进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。

struct QNode *next;}QNode,*Queueptr;typedef struct{Queueptr front;//队头指针Queueptr rear;//队尾指针}LinkQueue;2.基本操作描述void InitStack(SqStack &S);//初始化一个栈void Push(SqStack &S,struct Park e);//压入一个栈顶元素struct Park GetTop(SqStack &S);//得到栈顶元素,函数的返回值为存放车的信息的结构体变量struct Park Pop(SqStack &S);//删除栈顶元素，且函数的返回值为栈顶元素int EmptyStack(SqStack S);//判断一个栈是否为空，空返回1，非空返回0void VisitStack(SqStack S);//遍历一个栈而且输出栈元素的信息,输出顺序为从栈底元素到栈顶元素 void InitQueue(LinkQueue &Q);//初始化一个队列void InsertQueue(LinkQueue &Q,struct Park e);//在队列的队尾处中插入一个元素void DeleteQueue(LinkQueue &Q);//删除队头元素void VisitQueue(LinkQueue Q);//遍历队列，且输出队列元素信息,按照从队头到队尾的顺序输出void DQueue(LinkQueue &Q,struct Park e);//在队列中删除元素信息的数据域中的num值和e的num相等的元素int DStack(SqStack &S,struct Park p,double &d);//在栈中查找是否有与p的num值相等的元素，如果找到，改变d的值，函数值返回1，否则函数值返回03.主程序模块处理过程描述首先输入该车辆信息，判断是否是输入结束标志，是则跳出循环，否则判断是否是进入的车辆，如果是进入的车辆，那么判断此时栈是否已经满了，如果此时栈已满，那么该车辆就要入队列，否则入栈。

栈和队列的应用实验报告
《栈和队列的应用实验报告》
一、实验目的
本实验旨在通过实际操作，掌握栈和队列的基本概念、操作及应用，加深对数
据结构的理解和应用能力。

二、实验内容
1. 栈的基本操作：包括入栈、出栈、获取栈顶元素等。

2. 队列的基本操作：包括入队、出队、获取队首元素等。

3. 栈和队列的应用：通过实际案例，探讨栈和队列在实际生活中的应用场景。

三、实验步骤
1. 学习栈和队列的基本概念和操作。

2. 编写栈和队列的基本操作代码，并进行调试验证。

3. 分析并实现栈和队列在实际应用中的案例，如表达式求值、迷宫问题等。

4. 进行实际应用案例的测试和验证。

四、实验结果
1. 成功实现了栈和队列的基本操作，并通过实际案例验证了其正确性和可靠性。

2. 通过栈和队列在实际应用中的案例，加深了对数据结构的理解和应用能力。

五、实验总结
通过本次实验，我深刻理解了栈和队列的基本概念和操作，并掌握了它们在实
际应用中的重要性和作用。

栈和队列作为数据结构中的重要内容，对于解决实
际问题具有重要意义，希望通过不断的实践和学习，能够更加熟练地运用栈和
队列解决实际问题，提高自己的编程能力和应用能力。

六、感想与展望
本次实验让我对栈和队列有了更深入的了解，也让我对数据结构有了更加深刻的认识。

我将继续学习和探索更多的数据结构知识，提高自己的编程能力和解决问题的能力，为将来的学习和工作打下坚实的基础。

同时，我也希望能够将所学知识应用到实际工程中，为社会做出更大的贡献。

实验二栈和队列一、实验目的1、了解栈和队列的特性2、掌握栈的顺序表示和实现3、掌握栈的链式表示和实现4、掌握队列的顺序表示和实现5、掌握队列的链式表示和实现6、掌握栈和队列在实际问题中的应用二、实验要求1、认真阅读和掌握数据结构课本中实验相关程序的算法2、尽可能少的改动，使之成为可以运行的C程序3、保存和打印程序的运行结果，并结合程序进行分析4、你的实验体会三、实验内容实验2.1 栈的顺序表示和实现编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：1.建立栈：构造一个空栈,并插入元素2.入栈，插入元素3.出栈，删除栈顶元素4.取栈顶元素5.输出显示栈内元素，从栈底到栈顶『参考程序清单』#include <stdio.h>/*程序中使用了动态存储分配函数，ANSI建议在stdlib.h头文件内包含有关信息*/ /*也有些编辑系统要求用malloc.h ,参见C程序设计附录p377动态存储分配函数*/ /*但是用WinTc居然可以省略这些文件！！史守正2011*//*包含数据结构的预定义常量和类型P10 */#include "Datahead.h"/*文件名大于8位出错*//*定义元素类型为整数类型*/typedef int SElemType;/*栈的顺序存储表示*/#define STACK_INIT_SIZE 4 /* p46 */#define STACKINCREMENT 1typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;/*函数申明*/Status InitStack(SqStack *L); /* p47 */Status GetTop(SqStack S,SElemType *e);Status Push(SqStack *L, SElemType e); /* 进栈，插入 */ Status Pop(SqStack *L, SElemType *e); /* 出栈，删除*/ void Out_Stack(SqStack L); /*补充，输出打印栈*//*主函数*/void main(){int i,k,loc; /* k ，菜单控制变量*/SElemType e,x;char ch;SqStack L;SqStack *p;system("graftabl 936");/*调用MS_DOS中文支持*/p=&L;/*p指向 L*/do{printf("\n========实验二：栈和队列 ===============");printf("\n 1.建立栈：构造一个空栈,并插入元素");printf("\n 2.入栈，插入元素");printf("\n 3.出栈，删除元素");printf("\n 4.取栈顶元素");printf("\n 5.输出显示栈内元素，从栈底到栈顶");printf("\n 0.结束程序运行");printf("\n=====================================");printf("\n 请输入您的选择（1,2,3,4,0)\n");scanf("%d",&k);switch(k){case 1:{loc=InitStack(p);printf("\n请输入入栈元素个数，并依次输入整数类型的元素值"); scanf("%d",&loc);for(i=1;i<=loc;i++) {scanf("%d",&e);Push(p, e); /*也可以不处理函数返回值*/}Out_Stack(L);}break;case 2:{ /* 此处要求补充代码……*/}break;case 3:{ printf("\n请输入出栈元素个数");/* 此处要求补充代码……*/}break;case 4:{ /* 此处要求补充代码……*/}; break;case 5:{Out_Stack(L);}; break;case 0:{exit(0);}}}while(k!=0);ch =getchar();}Status InitStack(SqStack *S) { /* p47 *//* 构造一个空栈 */S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) exit(OVERFLOW); /* 存储分配失败 */S->top = S->base;S->stacksize = STACK_INIT_SIZE; /* 初始存储容量 */return OK;} /* InitStack */Status GetTop(SqStack S, SElemType *e) { /* p47 *//* 此处要求自己参考课本补充代码……*/return OK;} /* GetTop */Status Push(SqStack *S, SElemType e) { /* P47 */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;} /* Push */void Out_Stack(SqStack L){int *i;printf("\n当前栈内元素从栈底到栈顶为：");for(i=L.base;i<L.top;i++) printf("%10d",*i);}Status Pop(SqStack *S, SElemType *e) { /* p47 *//* 此处要求自己参考课本补充代码……*/return OK;} /* Pop */实验2.2 栈的链式表示和实现编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈实验2.3 队列的顺序表示和实现编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列（2）建立顺序队列（3）入队（4）出队（5）判断队列是否为空（6）取队列头元素（7）遍历队列实验2.4 队列的链式表示和实现编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化并建立链队列（2）入链队列（3）出链队列（4）遍历链队列四、程序调试和结果输出五、实验小结。

实验二：栈与队列的应用学时：4学时实验目的：掌握栈与队列的基本结构和操作方法，并能利用其解决实际问题。

实验内容： (任选一题，有能力的同学可以两题都做)一、输入一个表达式(4+2*4#),利用栈求表达式的值。

（只对整数求值，目前只考虑操作数为个位数的情况，即24+34*34这种情况不考虑）提示：1，先实现栈的基本操作：初始化，入栈，出栈等。

2，首先将一个中缀式变成后缀式，然后，对后缀式求值。

3，可用顺序栈或者链栈实现。

二、编写一个程序，反映病人到医院看病排队看医生的情况，在病人排队过程中，主要重复两件事：（1）病人到达诊室，将病历交给护士，排到等待队列中侯诊（2）护士从等待队列中取出下一位病人的病历，改病人进入诊室就诊要求：模拟病人等待就诊这一过程，程序采用菜单式，其选项和功能说明如下：（1）排队——输入排队病人的病历号，加入到病人排队队列中（2）就诊——病人排队队列中最前面的病人就诊，将其从队列中删除（3）查看排队——从队首到队尾理出所有的排队病人的病历号（4）不在排队，余下依次就诊——从队首到队尾列出所有的排队病人的病历号，并退出运行（5）下班——退出运行（6）上班——初始化排队队列。

提示：1，先实现队列的基本操作：初始化，入队，出队等。

2，在main（）程序中，模拟病人看病这个过程。

给出菜单选择，进行相应的操作3，可用顺序队列或者链队列实现。

可参考如下代码：顺序栈的实现ch32_sstack.c#include "stdio.h"#define StackSize 100typedef int ElemType;typedef struct {ElemType elem[StackSize];int top;}SqStack;InitStack(SqStack *pS){pS->top=0; /* top指向栈顶的上一个元素*/}int Push(SqStack *pS,ElemType e){if (pS->top==StackSize-1) /* 栈满*/return 0;pS->elem[pS->top]=e;pS->top=pS->top+1;return 1;}int Pop(SqStack *pS,ElemType* pe){if (pS->top==0) /* 栈空*/return 0;pS->top = pS->top - 1;*pe = pS->elem[pS->top];return 1;}main(){SqStack S;ElemType e;int N;InitStack(&S);N=1348;while(N){e = N % 8;Push(&S,e);N = N/8;}while(Pop(&S,&e)){printf("%d",e);}getch();}链栈的实现ch3_lstack.c #include "stdio.h"/* 数据元素的类型*/typedef int ElemType;/* 节点的类型（包括头节点）*/typedef struct Node{ElemType elem;struct Node *next;}SNode;/* 初始化，头节点*/InitStack(SNode* pS){pS->next=NULL;}/* 入栈：在头节点之后插入一个新节点*/Push(SNode* pS,ElemType e){SNode* node;node = (SNode*)malloc(sizeof(SNode));node->elem = e;node->next = pS->next;pS->next = node;}int Pop(SNode* pS,ElemType* pe){SNode* node;if (pS->next==NULL){return 0;}*pe = pS->next->elem;node=pS->next;pS->next=node->next;free(node);return 1;}main(){SNode S; ElemType e;int N;InitStack(&S);N=1348;while(N){e = N % 8;Push(&S,e);N = N/8;}while(Pop(&S,&e)){printf("%d",e);}getch();}队列的顺序实现（循环队列）ch3_squeue.c/*队列的顺序实现（循环队列）author: Shirleydate: 2011.3*/#define MaxSize 100typedef int ElemType;typedef struct {ElemType elem[MaxSize];int front,rear;}SqQueue;InitQueue(SqQueue* pQ){pQ->front=pQ->rear=0;}int EnQueue(SqQueue* pQ,ElemType e){if ((pQ->rear+1)%MaxSize == pQ->front) /* 队满*/ return 0;pQ->elem[pQ->rear] = e;pQ->rear = (pQ->rear+1)%MaxSize;return 1;}int DeQueue(SqQueue* pQ,ElemType* pe){if (pQ->rear == pQ->front) /* 队空*/return 0;*pe = pQ->elem[pQ->front];pQ->front = (pQ->front+1)%MaxSize;return 1;}main(){SqQueue Q;ElemType e;InitQueue(&Q);e=2;EnQueue(&Q,e);e=5;EnQueue(&Q,e);e=3;EnQueue(&Q,e);while(DeQueue(&Q,&e)){printf("\n%d",e);}getch();}队列的链式实现ch3_lqueue.c /*队列的链式实现author: Shirleydate: 2011.3*/#include "stdio.h"#define MaxSize 100typedef int ElemType;typedef struct QNode{ElemType elem;struct QNode * next;}QNode;typedef struct {QNode* front;QNode* rear;}LinkQueue;InitQueue(LinkQueue* pQ){QNode* node;node=(QNode*)malloc(sizeof(QNode)); /*分配一个头节点*/ node->next = NULL;pQ->front=pQ->rear=node;}int EnQueue(LinkQueue* pQ,ElemType e){QNode* node;node=(QNode*)malloc(sizeof(QNode));node->elem = e;node->next = NULL;pQ->rear->next = node;pQ->rear = node;return 1;}int DeQueue(LinkQueue* pQ,ElemType* pe){QNode* node;if (pQ->rear == pQ->front) /* 队空*/return 0;node = pQ->front->next;*pe = node->elem;pQ->front->next = node->next;/* 注意有个头节点，当最后一个元素出队时，记得更新尾指针*/ if (pQ->rear==node)pQ->rear=pQ->front;free(node);return 1;}DestoryQueue(LinkQueue* pQ){while(pQ->front){pQ->rear=pQ->front->next;free(pQ->front);pQ->front = pQ->rear;}}main(){LinkQueue Q;ElemType e;InitQueue(&Q);e=2;EnQueue(&Q,e);e=5;EnQueue(&Q,e);e=3;EnQueue(&Q,e);while(DeQueue(&Q,&e)){printf("\n%d",e);}DestoryQueue(&Q);getch();}。

栈和队列实验报告背景栈（Stack）和队列（Queue）是常用的数据结构，它们在计算机科学中具有广泛的应用。

栈和队列虽然在逻辑上都是线性结构，但其特点和操作有很大的差别。

栈是一种后进先出（Last In First Out，LIFO）的数据结构。

在栈中，最后插入的元素最先被访问。

类似于现实生活中的堆栈，最先放入的物品最后需要取出。

栈的主要操作有入栈（Push），将元素放入栈顶；出栈（Pop），将栈顶元素取出；以及获取栈顶元素（Top）等。

队列是一种先进先出（First In First Out，FIFO）的数据结构。

在队列中，最先插入的元素最先被访问。

类似于现实生活中的排队，最先排队的人最先被服务。

队列的主要操作有入队（Enqueue），将元素放入队尾；出队（Dequeue），将队首元素取出；以及获取队首元素（Front）等。

本次实验的目的是加深对栈和队列的理解，并实现相关的操作。

分析栈的实现栈的实现可以有多种方式，常见的有基于数组和基于链表。

基于数组的栈实现相对简单，可以使用固定大小的数组，通过一个变量来记录栈顶指针。

基于链表的栈实现更加灵活，可以动态地分配内存。

基于数组的栈实现主要需要考虑的问题是栈的大小限制和溢出处理。

当栈已满时，继续入栈会导致溢出；当栈为空时，进行出栈操作会导致栈错误。

因此，需要对入栈和出栈操作进行边界检查。

队列的实现队列的实现也可以有多种方式，常见的有基于数组和基于链表。

基于数组的队列实现可以使用固定大小的数组，通过两个变量来记录队首和队尾的位置。

基于链表的队列实现可以使用链表节点表示队列中的元素。

在实现队列的过程中，需要注意队列的大小限制和溢出处理。

当队列已满时，继续入队会导致溢出；当队列为空时，进行出队操作会导致队列错误。

因此，需要对入队和出队操作进行边界检查。

实验过程栈的实现本次实验选择使用基于数组的栈实现。

首先定义一个固定大小的数组，以及一个整数变量来记录栈顶元素的位置。