实验二 堆栈和队列基本操作的编程实现

实验二栈和队列的基本操作实现及其应用一、实验目的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;}。

c语言用两个栈实现队列,分别写出入队和出队的算法。

注意可以直接调用队列和栈的基-回复C语言是一种广泛使用的编程语言，具有强大的功能和灵活性。

队列和栈是常见的数据结构，用于解决各种实际问题。

在本文中，我们将讨论如何使用两个栈来实现队列，并分别介绍入队和出队的算法。

队列是一种操作受限的线性数据结构，遵循先进先出（FIFO）的原则。

栈是另一种操作受限的线性数据结构，遵循后进先出（LIFO）的原则。

通过利用两个栈的特性，我们可以实现队列的所有操作。

一、入队算法实现将元素插入队列的过程被称为入队。

在使用两个栈实现队列时，我们可以将一个栈作为输入栈，另一个栈作为输出栈。

下面是入队的算法实现：1. 首先，检查两个栈是否为空。

2. 如果输出栈不为空，则将输出栈中的所有元素依次出栈并入栈到输入栈中，以确保新插入的元素插入到栈底。

3. 将新元素插入到输入栈的栈顶。

4. 入队完成。

下面是使用C语言编写的入队算法示例代码：cvoid enqueue(int item, Stack *inputStack, Stack *outputStack) { 检查输出栈是否为空if (!is_empty(outputStack)) {while (!is_empty(outputStack)) {将输出栈中的元素依次出栈并插入到输入栈中int popped_item = pop(outputStack);push(popped_item, inputStack);}}将新元素插入到输入栈的栈顶push(item, inputStack);}二、出队算法实现将元素从队列中移除的过程被称为出队。

在使用两个栈实现队列时，我们同样可以利用一个栈作为输入栈，另一个栈作为输出栈。

下面是出队的算法实现：1. 首先，检查输出栈是否为空。

2. 如果输出栈为空，则将输入栈中的所有元素依次出栈并入栈到输出栈中，以确保最早进入的元素在输出栈的栈顶。

3. 从输出栈的栈顶移除一个元素，并返回该元素。

实验二栈和队列的操作一、实验目的1．熟悉栈和队列的存储结构；2．熟悉栈和队列的相关操作；3．利用栈和队列求解一些常见问题。

二、实验内容1、表达式求值任何一个算术表达式都是由操作数(operand) 、运算符(operator) 和界限符(edlimiter) 组成的。

为了简化问题．这里假设算术表达式中的操作数为单个数字表示的变量：运算符有加“ + ”、减“—”、乘“ * ”、除“／”和括号，表达式以“#”结束。

运算法则是括号优先级最高，先乘除，后加减，同级运算自左至右。

程序设计时需设置两个工作栈。

一个称为运算符栈，用OP 表示，用于存放表达式中的运算符：另一个称为操作数栈，用S 表示，用于存放操作数或运算结果。

这两个栈的初始状态均为空。

计算机从左至右扫描表达式，凡遇操作数一律进S 栈；若遇运算符，则要把它的优先数和栈顶运算符的优先数进行比较：若前者大，则该运算符进OP 栈；否则，栈顶运算符退栈、并进行计算，运算对象为S 栈顶上的两个元素，且先退栈的元素在运算量的右侧，后退栈的在运算量的左侧。

试编写一程序，先输入一个表达式，再求表达式的值。

2、数制转换假设现要编制一个满足下列要求的程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。

从计算过程可见，这八进制的各个数位产生的顺序是从低位到高位的，而打印输出的顺序，一般来说应从高位到低位，这恰好和计算过程相反。

因此，需要先保存在计算过程中得到的八进制数的各位，然后逆序输出，因为它是按“后进先出”的规律进行的，所以用栈最合适。

试编写一个程序，实现将十进制数转换成八进制数并输出。

三、主要任务1、完成算法设计和程序设计，并分析算法时间复杂度和空间复杂度；2、写出程序运行情况，写出输入数据及运行结果；3、撰写实验报告，写出算法设计小结和心得。

四、思考题1、为什么说栈是一种特殊线性表？它的操作与线性表有什么不同？2、对于数制转换算法，如果不用栈如何实现？。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==队列操作实验报告篇一：栈和队列基本操作实验报告实验二堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求：堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。

也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】验证性实验（学时数：2H）【实验内容】内容：把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。

可以实验一的结果自己实现数据输入、数据显示的函数。

利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。

【实验分析、说明过程】【思考问题】【实验小结】 ( 总结本次实验的重难点及心得、体会、收获)【附录-实验代码】篇二：队列存储与操作实验报告实验四队列存储与操作一. 实验目的1、掌握队列顺序存储结构（循环队列）及实现及操作2、掌握队列的链接存储结构及实现及操作二. 实验内容1、建立一个空顺序存储结构队列；对已建立的队列进行插入、删除、取队头元素等基本操作。

2、建立一个空链式存储结构队列；对已建立的队列进行插入、删除、取队头元素等基本操作。

三、详细设计：1、顺序队列的实现：#include<iostream>using namespace std;const int Size=100;typedef char DataType;class CirQueue{public:CirQueue() { } ~CirQueue(){} void EnQueue(DataType x){if((rear+1)%Size==front) {} cout<<"队列已经满了"<<endl; return; front=rear=0;//构造队列，初始化一个空的循环队列，front和rear指向};} data[rear]=x; cout<<x<<"已入队"<<endl; return; DataTypeGetQueue()//取队头 { } DataType DeQueue() { } int isEmpty()//是否为空{ } DataType data[Size]; int front,rear; if(front==rear) { } else{ } return 0; return 1; if(isEmpty()) {} front=(front+1)%Size;//队头指针在循环的意义下加 return data[front]; cout<<"队列为空"<<endl; return 0; if(isEmpty()) {} int i; i=(front+1)%Size; return data[i]; cout<<"队列为空"<<endl; return 0; private:int main(){int index; DataType temp; do{cout<<"**********************************"<<endl; cout<<"1、入队操作"<<endl; cout<<"2、取队头操作"<<endl; cout<<"3、出队操作"<<endl;cout<<"4、判断队列是否为空"<<endl; cout<<"5、退出"<<endl;cout<<"**********************************"<<endl; cin>>index;if(index==5){return 0;} switch(index) { case 1:cout<<"请输入要入队的元素"<<endl; cin>>temp; a.EnQueue(temp); break; temp=a.GetQueue();if(temp!=0) { } cout<<"队头的元素为"<<temp<<" "<<endl;case 2: break; temp=a.DeQueue(); if(temp!=0) { } cout<<"出队的元素为"<<temp<<""<<endl; case 3: break; bool temp; temp=a.isEmpty(); if(temp){cout<<"空队"<<endl; cout<<"非空队"<<endl; }else{ case 4:} } break; }while(index); return 0;2、链队列的实现： #include<iostream> using namespace std;const int Size=100; typedef char DataType; struct Node{};class LinkQueue {public:LinkQueue() { } ~LinkQueue(){} void EnQueue(DataType x) {} DataType GetQueue()//取?队ó头? {if(isEmpty()) {} cout<<"队ó列为a空?"<<endl; return 0; auto s=new Node; s->data=x; s->next=NULL;//申Θ?请?一?个?数簓据Y域?为aX的?结á点?s rear->next=s; rear=s; auto head=new Node; head->next=NULL; front=rear=head; DataType data; Node *next;};} return front->next->data; DataType DeQueue() { } int isEmpty()//是?否?为a空? { } Node*front,*rear;//队ó头?和í队ó尾2指?针?if(front==rear) { } else{ } return 0; return 1; if(isEmpty()) {} auto p=new Node;//用?于?暂Y存?队ó头?元a素? DataType x;//用?于?暂Y存?队ó头?数簓据Y p=front->next; x=p->data; front->next=p->next;if (p->next==NULL) { } delete p; return x; rear=front; cout<<"队ó列为a空?"<<endl; return 0; private:int main() {LinkQueue a; int index; DataType temp; do{cout<<"**********************************"<<endl; cout<<"1、￠入?队ó操ù作痢?<<endl;篇三：队列存储与操作实验报告实验四队列存储与操作一、实验目的1、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活运用。

实验二栈与队列姓名：班级：学号：日期：一、实验目的：二、实验内容：三、基本思想，原理和算法描述:四、源程序：(1)栈的基本操作及应用：#include <stdio.h>#include <stdlib.h>#include<malloc.h>#include <string.h>#define ERROR 0//#define INFREASIBLE -1#define OVERFLOW -2#define SIZE 100 //存储空间初始分配量//#define INCREMENT 10 //存储空间分配增量typedef int Status;#define TRUE 1#define FLASE 0#define OK 1typedef struct{int *top; //栈顶指针int *base; //栈底指针int stacksize; //当前已分配的存储空间}SqStack;Status InitStack(SqStack *s) //初始化{s->base=(int*)malloc( SIZE * sizeof(int));if(!s->base)exit(OVERFLOW);s->top=s->base;s->stacksize=SIZE;return OK;}Status ClearStack(SqStack *s) // 置空{s->top=s->base;return OK;}Status DestroyStack(SqStack *s) //销毁{ClearStack(s);free(s->base);return OK;}Status StackEmpty(SqStack *s) //判断是否为空{if(s->top==s->base){return TRUE;}else{return FLASE;}}Status GetTop(SqStack* s,int *e) //取栈顶{//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(s->top==s->base){return ERROR;}*e=*(s->top-1);return OK;}Status Push(SqStack *s,int e) //进栈{//插入元素e为新的栈顶元素if(s->top-s->base>=s->stacksize){//栈满，追加存储空间s->base=(int *)malloc(SIZE*sizeof(int));if(!s->base)exit(OVERFLOW);s->top=s->base + s->stacksize;s->stacksize +=SIZE;}*(s->top)++=e;return OK;}Status Pop(SqStack *s ,int *e)//出栈{// 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(s->base == s->top)return ERROR;*e = *--s->top;return OK;}Status StackTraverse(SqStack *s)//遍历{while(s->top != s->base){printf("%d\t",*--s->top);}return OK;}Status Conversion(SqStack *s, int N) //进制转换{int m;printf("输入R进制");scanf("%d", &m);int e;while(N){Push(s, N % m);N = N / m;}while(s->top != s->base){Pop(s, &e);printf("%d", e);}return OK;}int main ( ){SqStack sq;InitStack(&sq);int e;int N;int k;int n=0;Z:{printf("\n\t********************************************");printf("\n\t*** 请你输入相应的操作序号进行操作***");printf("\n\t*** 1.初始化***");printf("\n\t*** 2.置空***");printf("\n\t*** 3.销毁***");printf("\n\t*** 4.是否空***");printf("\n\t*** 5.取栈顶元素***");printf("\n\t*** 6.进栈***");printf("\n\t*** 7.出栈***");printf("\n\t*** 8.遍历***");printf("\n\t*** 9.进制转换***");printf("\n\t*** 0. 退出***\n");printf("\t********************************************");printf("\n请选择功能：");scanf("%d",&k);switch(k){case 1:InitStack(&sq);goto Z;break;case 2:ClearStack(&sq);goto Z;break;case 3:DestroyStack(&sq);goto Z;break;case 4:if(StackEmpty(&sq)){printf("该栈为空!");}else{printf("该栈非空!");}goto Z;break;case 5:GetTop(&sq, &e);printf("栈顶元素为：%d", e);goto Z;break;case 6:printf("请输入要进栈的元素：");scanf("%d", &e);Push(&sq, e);goto Z;break;case 7:Pop(&sq,&e);printf("%d", e);goto Z;break;case 8:StackTraverse(&sq);goto Z;break;case 9:printf("请输入要转换的十进制数字：");scanf("%d", &N);printf("转换后R进制的数字为：");Conversion(&sq, N);goto Z;break;case 0:exit(0);break;default:break;}}}(2)队列的基本操作：#include<iostream>#include<malloc.h>using namespace std;#define TRUE 1#define FLASE 0#define OK 1typedef struct QNode{char data;struct QNode *next;}QNode,*Queue;typedef struct{Queue front;Queue rear;}LinkQueue;void InitQueue(LinkQueue &Q)//创造空队{Q.front=Q.rear=(Queue)malloc(sizeof(QNode));if(!Q.front){cout<<"OVERFLOW"<<endl;}Q.front->next=NULL;// return OK;}void EnQueue(LinkQueue &Q,int e)//入队{Queue p=(Queue)malloc(sizeof(QNode));p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;//return OK;}void DeQueue(LinkQueue &Q,int e)//出队{Queue p=(Queue)malloc(sizeof(QNode));if( Q.front==Q.rear){cout<<"队空"<<endl;}p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);cout<<e<<" 元素已经出队"<<endl;}int length(LinkQueue &Q)//求队列中元素个数{Queue p=(Queue)malloc(sizeof(QNode));p=Q.front->next;int i=0;while(p!=NULL){p=p->next;i++;}cout<<"队列中元素个数："<<endl;cout<<i<<endl;return 1;}int QueueEmpty(LinkQueue &Q)//判队列空{if( Q.front==Q.rear)return TRUE;elsereturn FLASE;}int main(){LinkQueue Q;int k;Z:{cout<<" \n\t********************************************"<<endl;cout<<"\n\t*** 请你输入相应的操作序号进行操作***"<<endl;cout<<"\n\t*** 1.初始化***"<<endl;cout<<"\n\t*** 2.入队***"<<endl;cout<<"\n\t*** 3.出队***"<<endl;cout<<"\n\t*** 4.求队列中元素个数***"<<endl;cout<<"\n\t*** 5.判队列是否为空***"<<endl;cout<<"\n\t********************************************"<<endl;cout<<"\n请选择功能："<<endl;cin>>k;switch(k){case 1:InitQueue(Q);goto Z;break;case 2:cout<<"请输入要插入的元素"<<endl;int e;cin>>e;EnQueue(Q,e);goto Z;break;case 3:cout<<"出队"<<endl;int m;DeQueue(Q,m);goto Z;break;case 4:length(Q);goto Z;break;case 5:if(QueueEmpty(Q))cout<<"队列为空"<<endl;elsecout<<"队列不为空"<<endl;goto Z;break;default:break;}}}（3）判断回文：#include <stdio.h>#include <stdlib.h>#include <malloc.h>const int STACK_INIT_SIZE = 100; // 初始分配的长度const int STACKINCREMENT = 10; // 分配内存的增量// 链式队列结构的定义typedef char ElemType;typedef struct Node{char data; // 元素数据struct Node *next; // 链式队列中结点元素的指针}QNode,*QueuePtr;typedef struct{QueuePtr front; // 队列头指针QueuePtr rear; // 队列尾指针}LinkQueue;// 栈结构的定义typedef struct Stack{ElemType *base;ElemType *top;int stacksize;}SqStack;bool InitQueue(LinkQueue *Q){Q->front = Q->rear = (QueuePtr)malloc(sizeof (QNode)); if (!Q->front){exit(0);}Q->front->next = NULL;return true;}bool EnQueue(LinkQueue *Q, ElemType e){QueuePtr p = (QueuePtr)malloc(sizeof(QNode));if (!p){exit(0);}p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;return true;}bool DeQueue(LinkQueue *Q, ElemType *e){if (Q->front == Q->rear){return false;}QueuePtr p = Q->front->next;*e = p->data;Q->front->next = p->next;if (Q->rear == p){Q->rear = Q->front;}free(p);return true;}bool InitStack(SqStack *S){S->base = (ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType)); if (S->base == NULL){return false;}S->top = S->base;S->stacksize = STACK_INIT_SIZE;return true;}bool Push(SqStack *S, ElemType e){if (S->top - S->base >= S->stacksize){S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));if (!S->base){return false;}S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT;}*(S->top++) = e;return true;}bool Pop(SqStack *S, ElemType *e){if (S->top == S->base)return false;*e = (*--S->top);return true;}int main (){//声明一个栈一个队列SqStack S;LinkQueue L;//初始化一个栈一个队列InitStack (&S);InitQueue (&L);char c[30];ElemType a,b;printf("请输入要判断的字符，以@结束：");scanf("%s",c);int i = 0;int flag1 = 0;int flag2 = 0;while (c[i] != '@'){Push(&S,c[i]); //入栈EnQueue(&L,c[i]); //入队列flag1++;i++;}while (!(S.top == S.base)){Pop(&S,&b); //出栈DeQueue(&L,&a); //出队列if (a==b){flag2++;}else{break;}}if (flag1 == flag2){printf("Right\n\n");}else{printf("Wrong\n\n");}system("pause");return 0;}五、运行结果分析：栈的基本操作及应用图1:栈图2：进栈图3：出栈图4：读取栈顶元素图5：判断是否为空图6：数值的进制转换队列的基本操作图7：队列图8：入队图9：求队列中的元素个数图10：出队列判断回文六、实验总结：。

实验作业二：栈（顺序栈）和队列（循环队列）1. 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。

当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。

两个栈均从两端向中间增长。

当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。

当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。

试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。

2. 求fibonacci数列算法，并比较。

（递归+非递归）（非递归方法可查阅其他资料）编写实习报告要求：一、需求分析二、概要设计1.抽象数据类型2.算法三、详细设计程序代码（注释）四、调试分析调试过程中所做的工作，时间复杂度等五、测试结果输入数据和输出数据示例六、说明（如果有）编程语言：C语言或C++语言实习报告提交方式：下次上机前，将实习报告(.doc)和源程序(.cpp)压缩成一个rar 文件，文件名称为学号_班级_姓名_第几次作业。

例如：3010216155_六班_张三_第二次作业.rar。

实习报告作为本课程的平时成绩。

抄袭、雷同，双方均为0分。

第一题：一、需求分析程序要求建立一个共享栈，分配一个存储空间，两个栈分别位于两头。

并实现对两个栈的插入，删除，和判断栈满和栈空。

栈的位置不同，所以要求对不同栈的插入和删除采用不同的算法。

二、概要设计1.抽象数据类型typedef struct {int *base;int *top;int stacksize;}stack;2.算法1.建立栈。

int instack(stack &s,stack &w,int length){s.base=(int *)malloc(length*sizeof(length));w.base=s.base+length;if(!s.base||!w.base) return 0;else{s.top=s.base;w.top=w.base;s.stacksize=length;w.stacksize=length;}return 1;}2.判断栈空。

实验二栈和队列一、实验目的1.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

2.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。

二、栈和队列的顺序存储结构在教材中,我们给出了栈的链表存储结构和队列的链表存储结构及实现,下面给出的是栈的顺序存储结构及实现和队列的顺序存储结构及实现。

1．栈的顺序存储结构及实现C++语言源程序。

//--------------------------------------------------------------------------- //栈的顺序存储结构，顺序表类#include<iostream.h>//------------------------------栈的顺序存储结构---------------------------------------------typedef int ElemType; // 数据元素的类型为intconst int MAXSIZE=100; // 数组的容量class SqStack{ private:ElemType elem[MAXSIZE];int top;public:SqStack( void);~SqStack(){};int SqStack::SetEmpty();void SqStack::push( ElemType e);ElemType SqStack::pop();void SqStack::PrintOut();int SqStack::IsEmpty(void)const ;};//-------------------------------------------------------------SqStack::SqStack( void):top(0){ }int SqStack::SetEmpty(){ return top==0;}void SqStack::push( ElemType e){ if(top==MAXSIZE-1) cout<<"\n栈满溢出"<<endl;else { top++;elem[top]=e; //数据元素e进栈}}ElemType SqStack::pop(){ ElemType x;if(top==0) {cout<< "\n 栈为空，不能进行出栈操作"<<endl;x=0; //表示未曾出栈}else { x=elem[top]; //出栈top--;}return x;}void SqStack::PrintOut(){int k;cout<<"\n PrintOut Data:\n" ;for(k=top; k>=1;k--) cout<<elem[k];cout<<endl;}int SqStack::IsEmpty(void)const{ if(top==0) return 1;else return 0;}//--------------------------------------------------------------------------- int main(int argc, char* argv[]){ int i,k;ElemType e,x;SqStack as;cout<<"\n 顺序表存储结构演示";do{cout<<"\n\n";cout<<"\n\n 1.插入一个数据元素e（入栈）";cout<<"\n\n 2.删除一个元素，返回其值（出栈）";cout<<"\n\n 3..结束程序";cout<<"\n******************************** ";cout<<"\n 请输入你的选择(1,2,3,4,5,6)"; cin>>k;switch(k){case 1:{cout<<"\n 入栈，数据 e=?";cin>>e;as.push(e);as.PrintOut();}break;case 2:{ cout<<"\n 出栈";x=as.pop();cout<<"\n 出栈元素数值= "<<x;as.PrintOut();}break;default:break;} //switchcout<<"\n--------------------------------- ";}while(k>=1&&k<3);cout<<"\n 再见!";cout<<"\n 按任意键，返回。

数据结构实验二数据结构实验二：队列与栈的实现一、实验目的本实验旨在通过实现队列和栈数据结构，加深对队列和栈实现原理的理解，并熟练掌握队列和栈的基本操作。

二、实验要求1.使用C/C++语言实现队列的基本操作：初始化队列、入队、出队、判空、判满等。

2.使用C/C++语言实现栈的基本操作：初始化栈、入栈、出栈、判空、判满等。

3.验证队列和栈的实现是否正确。

4.分析队列和栈的时间复杂度，并给出实验结果。

5.撰写实验报告，包括实验目的、实验原理、实验步骤、程序源代码、实验结果和分析、实验总结等内容。

三、实验原理1.队列：队列是一种先进先出(FIF0)的数据结构。

在队列中，数据元素按照进入队列的顺序排列，首元素是最先进入的元素，尾元素是最后进入的元素。

队列的基本操作有：初始化队列、入队、出队、判空、判满等。

2.栈：栈是一种后进先出(LIFO)的数据结构。

在栈中，数据元素按照进入栈的顺序排列，但是只能从栈顶进出，即最后进入的元素最先出栈。

栈的基本操作有：初始化栈、入栈、出栈、判空、判满等。

四、实验步骤1.实现队列的基本操作：1.初始化队列：创建一个空队列，并设置相关指针。

2.入队：将新元素插入到队尾。

3.出队：将队头元素删除，并返回其值。

4.判空：判断队列是否为空。

5.判满：判断队列是否已满。

2.实现栈的基本操作：1.初始化栈：创建一个空栈，并设置相关指针。

2.入栈：将新元素压入栈顶。

3.出栈：将栈顶元素弹出，并返回其值。

4.判空：判断栈是否为空。

5.判满：判断栈是否已满。

3.编写测试代码，验证队列和栈的基本操作是否正确。

4.进行性能测试，分析队列和栈的时间复杂度。

五、实验结果与分析1.队列的时间复杂度：●初始化队列：O(1)●入队：O(1)●出队：O(1)●判空：O(1)●判满：O(1)2.栈的时间复杂度：●初始化栈：O(1)●入栈：O(1)●出栈：O(1)●判空：O(1)●判满：O(1)3.根据实验结果可以看出，队列和栈的基本操作的时间复杂度都是O(1)，即常数时间复杂度，具有高效性。

实验报告（学科：数据结构）姓名__________________单位_______________________班级______________________实验名称：2.1 栈和队列的基本操作【问题描述】编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。

【基本要求】（1）正确理解栈的先进后出的操作特点，建立初始栈，通过相关操作显示栈底元素。

（2）程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。

【实验步骤】（1）建立顺序栈SeqStack，存放测试数据；建立队列SeqQueue存放出栈数据；（2）建立InitStack、StackEmpty、StackFull、Pop、Push、GetTop函数用作顺序栈的基本操作；（3）建立InitQueue、QEmpty、Qfull、InQueue、OutQueue、ReadFront函数用作队列的基本操作；（4）建立主函数依次按序对子函数进行操作：InitStack初始化栈→Push压入数据→InitQueue初始化队列→Pop弹出数据→InQueue存入队列→OutQueue出队列→Push压入栈→Pop弹出数据→free清空栈与队列。

在数据的输入与数据的输出时提供必要的提示信息。

（5）使用Visual Studio C++ 2005语言环境进行调试，源代码P202-2-1.cpp通过编译生成目标文件P202-2-1.obj，运行可执行文件：实验2-2-1.exe测试通过。

【源代码】#include "stdio.h"#include "stdlib.h"#define MaxSize 8typedef int ElemType;/*顺序栈的类型定义*/struct SeqStack{ElemType data[MaxSize];int top;};struct SeqStack * s;/*顺序队列的类型定义*/struct SeqQueue{ElemType data[MaxSize];int front,rear;};struct SeqQueue * sq;/*栈的基本运算*//*初始化栈操作*/void InitStack(struct SeqStack * s){s->top=-1;}/*判断栈空操作*/int StackEmpty(struct SeqStack * s){if(s->top==-1){ return(1);}else{return(0);}}/*判断栈满操作*/int StackFull(struct SeqStack * s){if(s->top==MaxSize-1){ return(1);}else{ return(0);}}/*压栈操作*/void Push(struct SeqStack *s,ElemType x) {if(s->top==MaxSize-1){printf("栈满溢出错误!\n");exit(1);}s->top++;s->data[s->top]=x;}/*弹栈操作*/ElemType Pop(struct SeqStack * s){if(StackEmpty(s)){printf("栈下溢错误!!\n");return(1);}s->top--;return s->data[s->top+1];}/*获取栈顶元素操作*/ElemType GetTop(struct SeqStack * s){if(StackEmpty(s)){printf("栈下溢错误!\n");exit(1);}return s->data[s->top];}/*队列的基本运算*//*初始化队列*/void InitQueue(struct SeqQueue * sq){sq->front=0;sq->rear=0;}/*判队空*/int QEmpty(struct SeqQueue * sq){if(sq->front==sq->rear){printf("队列已空，不能进行出队操作!\n");return(1); /*如果链队为空，则返回*/}else{return(0); /*否则返回*/ };}/*判队满*/int Qfull(struct SeqQueue * sq){if(sq->rear==MaxSize){ /*判队列是否已满*/printf("队列已满!\n");return(1); /*入队失败，退出函数运行*/ }return(0);}/*入队列操作*/void InQueue(struct SeqQueue * sq, int x){if(!Qfull(sq)){sq->data[sq->rear]=x; /*数据送给队尾指针所指单元*/sq->rear++; /*将队尾指针加*/ }}/*出队列操作*/ElemType OutQueue(struct SeqQueue *sq){if(sq->rear==sq->front){ /*判断队列是否为空*/printf("队列已空，不能进行出队操作!!\n");return(1); /*出队失败，退出函数运行*/ }sq->front++;return sq->data[sq->front-1];}/*读队头元素*/void ReadFront(struct SeqQueue * sq,int x){if(!QEmpty(sq)){sq->front++; /*将头指针加,前移*/OutQueue(sq); /*出队列操作*/ }}void main(){int n;struct SeqStack *a=(SeqStack *)malloc(sizeof(struct SeqStack));/*分配栈的内存空间，使结构指针a指向栈地址*/struct SeqQueue *sq=(SeqQueue *)malloc(sizeof(struct SeqQueue));InitStack(a);do{printf("输入栈中的数据:");scanf("%d",&n);Push(a,n);/*把数据压入栈中*/}while(!StackFull(a));InitQueue(sq);do{InQueue(sq,Pop(a)); /*弹出栈数据，把数据放进队列中*/}while(!(StackEmpty(a)&&Qfull(sq)));do{Push(a,OutQueue(sq)); /*从队列输出数据，把数据压入到栈内*/}while(!(QEmpty(sq)&&StackFull(a)));do{printf("输出栈中的数据:%d\n",Pop(a)); /*弹出栈中所有数据*/ }while(!StackEmpty(a));free(a);free(sq);}【实验数据】【结论】由于栈的结构特点决定了栈对数据的操作规则。

数据结构实验报告实验名称：实验2——栈和队列1 实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2 实验内容利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析主程序：#include<iostream>using namespace std;const int StackSize=8; //皇后的个数int num=0;template <class T>class SeqStack //定义顺序栈模板类{public:SeqStack(){top=-1;} //构造函数，初始化空栈void Push(T x); //入栈操作void Pop();//出栈操作void PlaceQueen(int row); //放置皇后bool Judgement();//判断是否符合条件void Print();//输出符合条件的皇后排列bool Empty(){if(top==-1) return true;else return false;}; //判断栈是否为空private:T data[StackSize]; //定义数组int top; //栈顶指针};template <class T>void SeqStack<T>::Push(T x) //入栈操作{if(top>=StackSize-1) throw"上溢";top++;//栈顶指针上移data[top]=x;}template <class T>void SeqStack<T>::Pop()//出栈操作{if(Empty()) throw"下溢";top--;//栈顶指针下移}template <class T>bool SeqStack<T>::Judgement()//判断该位置是否合适{for(int i=0;i<top;i++)if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))//判断是否满足任意两个皇后不在同列同一斜线return false;return true;}template <class T>void SeqStack<T>::PlaceQueen(int row) //放置皇后{for (int i=0;i<StackSize;i++){Push(i); //入栈if (Judgement())//判断位置是否合适{if (row<StackSize-1)PlaceQueen(row+1); //如果合适满足条件则放置一个皇后,递归调用else{num++;//不满足条件则到下一行Print();//输出符合条件的皇后}}Pop();//出栈}}template <class T>void SeqStack<T>::Print()//输出皇后函数{cout<<"NO."<<num<<":"<<endl; for(int i=0;i<StackSize;i++){for(int j=0;j<data[i];j++){cout<<"□";}cout<<"■";for(int j=StackSize-1;j>data[i];j--){cout<<"□";}cout<<endl;}cout<<endl;}void main(){SeqStack<int> Queen;Queen.PlaceQueen(0);cout<<"总共有"<<num<<"种摆放方法。