数据结构栈和队列实验报告.doc

数据结构栈和队列实验报告实验报告：数据结构栈和队列一、实验目的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)，操作效率很高。

数据结构栈与队列的实验报告实验概述本次实验的目的是通过对栈和队列进行实现和应用，加深对数据结构中的栈和队列的理解和巩固操作技能。

栈和队列作为常见的数据结构在程序开发中得到了广泛的应用，本次实验通过 C++ 语言编写程序，实现了栈和队列的基本操作，并对两种数据结构进行了应用。

实验内容1. 栈的实现栈是一种先进后出的数据结构，具有后进先出的特点。

通过使用数组来实现栈，实现入栈、出栈、输出栈顶元素和清空栈等操作。

对于入栈操作，将元素插入到数组的栈顶位置；对于出栈操作，先将数组的栈顶元素弹出，再使其下移，即将后面的元素全部向上移动一个位置；输出栈顶元素则直接输出数组的栈顶元素；清空栈则将栈中所有元素全部清除即可。

3. 栈和队列的应用利用栈和队列实现八皇后问题的求解。

八皇后问题，是指在8×8 的国际象棋盘上放置八个皇后，使得任意两个皇后都不能在同一行、同一列或者同一对角线上。

通过使用栈来保存当前八皇后的位置，逐个放置皇后并检查是否有冲突。

如果当前位置符合要求，则将位置保存到栈中，并继续查询下一个皇后的位置。

通过使用队列来进行八数码问题的求解。

八数码问题，是指在3×3 的矩阵中给出 1 至 8 的数字和一个空格，通过移动数字，最终将其变为 1 2 3 4 5 6 7 8 空的排列。

通过使用队列，从初始状态出发，枚举每种情况，利用队列进行广度遍历，逐一枚举状态转移，找到对应的状态后进行更新，周而复始直到找到正确的答案。

实验结果通过使用 C++ 语言编写程序，实现了栈和队列的基本操作，并对八皇后和八数码问题进行了求解。

程序执行结果如下：栈和队列实现的基本操作都能够正常进行，并且运行效率较高。

栈和队列的实现方便了程序编写并加速了程序运行。

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)的特点。

2输入自己编好的程序。
3检查一遍已输入的程序是否有错〔包括输入时输错的和编程中的错误〕，如发现有错，及时改正。
4进展编译和连接。如果在编译和连接过程中发现错误，频幕上会出现"报错信息〞，根据提示找到出错位置和原因，加以改正。再进展编译，如此反复直到不出错为止。
5运行程序并分析运行结果是否合理。在运行是要注意当输入不同的数据时所得结果是否正确，应运行屡次，分别检查在不同情况下结果是否正确。
s->ne*t=NULL;
}
void DestroyStack(LiStack *&s)//销毁栈
{LiStack *p=s,*q=s->ne*t;
while (q!=NULL)
{free(p);
p=q;
q=p->ne*t;
}
free(p);//此时p指向尾节点,释放其空间
}
bool StackEmpty(LiStack *s)//判断栈是否为空
printf("栈s的根本运算如下:\n");
printf(" (1)初始化栈s\n");
InitStack(s);
printf(" (2)栈为%s\n",(StackEmpty(s)""空":"非空"));
printf(" (3)依次进栈元素a,b,c,d,e\n");
Push(s,'a');Байду номын сангаас
Push(s,'b');
#include <stdio.h>
#include <malloc.h>
#define Ma*Size 100

数据结构实验报告之栈和队列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. 编写程序实现链队列的各种基本运算：初始化、销毁、清空、判断是否为空队列、求队列的长度、取队列的头元素、⼊队、出队。

【精品】数据结构栈和队列实验报告实验目的：1.了解栈和队列的概念和基本操作。

2.熟练掌握按顺序存储、链式存储、循环存储结构。

3.掌握栈和队列的应用。

实验环境：操作系统：Windows 7编程软件：Dev-C++实验内容：1.用数组作为栈的存储结构，并以学生管理系统为例，实现“进栈”、“出栈”等基本操作。

先用 typedef struct 学生信息实现一个结构体类型，包含了学号、姓名、性别、出生日期、专业等成员。

typedef struct student{char num[10]; //学号char name[10]; //姓名char sex[2]; //性别int year; //出生年份int major; //专业}StuType;定义一个常量 MAXSIZE 来代表栈的最大空间，建立一个顺序栈。

初始化栈：void init_seqstack(SeqStack &p){p.top = -1;}判断是否为空：进栈操作：bool push_seqstack(SeqStack &p,StuType e){if(p.top==MAXSIZE-1)return 0;p.top++;p.data[p.top]=e;return 1;}定义一个链表结构体类型以存放队列，包含首节点指针和尾结点指针。

typedef struct link_queue{ComType data;struct QueueNode *next;}QueueNode;出队操作：bool de_queue(queue &q,ComType &qdata){QueueNode *p=q.front->next;if(q.front==q.rear)return false;qdata=p->data;q.front->next=p->next;if(q.rear==p)q.rear=q.front;free(p);return true;}实验结果：通过本次实验，我可以熟练掌握栈和队列的基本概念和操作，并能够在相应的程序设计中熟练操作，达到掌握栈和队列的目标。

s->stacksize=stack_init_size;
return 1;
int Push(sqst->base>=s->stacksize)
{
s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int));
实验三 栈与队列
一、实验目的：
（1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基 本操作。
（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判 断条件及描述方法；
（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空 的判断条件和描述方法；
（4）掌握栈的应用；
if(!s->base)
return 0;
s->top=s->base+s->stacksize;
s->stacksize+=stackincrement;
*(s->top++)=e;
return e;
}
int Pop(sqstack *s,int e)
{
if(s->top==s->base)
return 0;
while(!stackempty(s)) { e=Pop(s,e); switch(e) { case 10: printf("A"); break; case 11: printf("B"); break; case 12: printf("C"); break; case 13: printf("D"); break; case 14: printf("E"); break; case 15: printf("F"); break;

数据结构栈与队列实验报告学院：数学与计算机学院班级：计算机科学与技术姓名：***学号：************实验三栈与队列一、实验目的：（1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。

（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法；（4）掌握栈的应用；二、实验要求：(1) 给出程序设计的基本思想、原理和算法描述。

(2) 对源程序给出注释。

(3) 记录程序的运行结果，并结合程序进行分析。

三、程序设计的基本思想、原理和算法描述：四、实验内容：1、利用栈的基本操作将一个十进制的正整数转换成R进制数据，并将其转换结果输出。

#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define stack_init_size 100#define stackincrement 10typedef struct sqstack {int *base;int *top;int stacksize;} sqstack;int StackInit(sqstack *s){ s->base=(int *)malloc(stack_init_size *sizeof(int));if(!s->base)return 0;s->top=s->base;s->stacksize=stack_init_size;return 1;}int Push(sqstack *s,int e){if(s->top-s->base>=s->stacksize){s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int));if(!s->base)return 0;s->top=s->base+s->stacksize;s->stacksize+=stackincrement;}*(s->top++)=e;return e;}int Pop(sqstack*s,int e){if(s->top==s->base)return0;e=*--s->top;return e;}int stackempty(sqstack*s){if(s->top==s->base){return1;}else{return0;}}int conversion(sqstack*s){int n,e=0,flag=0;printf("输入要转化的十进制数：\n");scanf("%d",&n);printf("要转化为多少进制：2进制、8进制、16进制填数字！\n"); scanf("%d",&flag);printf("将十进制数%d转化为%d进制是：\n",n,flag);while(n){Push(s,n%flag);n=n/flag;}while(!stackempty(s)){e=Pop(s,e);switch(e){case10:printf("A");break;case11:printf("B");break;case 12: printf("C");break;case 13: printf("D");break;case 14: printf("E");break;case 15: printf("F");break;default: printf("%d",e);}}printf("\n");return 0; }int main(){sqstack s;StackInit(&s);conversion(&s);return 0;}2、回文数判断#include<stdio.h>#include<string.h>#define MAX 50#define FALSE 0#define TURE 1//定义栈typedef struct{char elem[MAX];int top;}SeqStack;//定义循环队列typedef struct{char element[MAX];int front;int rear;}SeqQuene;//初始化栈void InitStack(SeqStack *S){S->top = -1;//构造一个空栈}//入栈int Push(SeqStack *S,char x,int cnt) {if(S->top == cnt-1)return(FALSE);S->top++;S->elem[S->top] = x;return(TURE);}//出栈int Pop(SeqStack * S,char * x){if(S->top == -1)return(FALSE);else{*x = S->elem[S->top];S->top--;return(TURE);}}//初始化队列void InitQuene(SeqQuene *Q){Q->front = Q->rear = 0;}//入队int EnterQuene(SeqQuene *Q,char x,int cnt) {if((Q->rear+1)%(cnt+1) == Q->front)return(FALSE);Q->element[Q->rear] = x;Q->rear = (Q->rear+1)%(cnt+1);return(TURE);}//出队int DeleteQuene(SeqQuene *Q,char *x,int cnt) {if(Q->front == Q->rear)return(FALSE);*x = Q->element[Q->front];Q->front = (Q->front+1)%(cnt+1);return(TURE);}//主函数void main(){int i,cnt,flag;SeqStack s;SeqQuene q;char a[MAX],b[MAX],c[MAX];flag=0;printf("请输入由*结束且小于%d的回文序列：\n",MAX); for(i = 0;i<MAX+1;i++){scanf("%c",&a[i]);if(a[i] == '*')break;}cnt = i;InitStack(&s);InitQuene(&q);for(i = 0;i<cnt;i++){EnterQuene(&q,a[i],cnt);Push(&s,a[i],cnt);}for(i = 0;i<cnt+1;i++){DeleteQuene(&q,&b[i],cnt);printf("%c",b[i]);}printf("\n");for(i = 0;i<cnt+1;i++){Pop(&s,&c[i]);printf("%c",c[i]);}printf("\n");for(i = 0;i<cnt+1;i++){if(b[i] == c[i])flag = 1;else{flag = 0;break;}}if(flag)printf("Right");elseprintf("Wrong");printf("\n"); }五、运行结果。

实验报告<四>试验报告项目栈和队列（进队和出队）所属课程名称数据结构试验类型实验验证试验日期2018/4/17#include<iostream>#include<stdlib.h>using namespace std;#define OK 1typedef int QElemType;typedef int Status;typedef struct QNode{QElemType data;struct QNode *next;};//定义节点typedef struct{struct QNode * rear;//尾指针struct QNode * front;//头指针int Length;}LinkQueue;//定义队列Status InitQueue(LinkQueue &Q);//初始化队列Status EnQueue(LinkQueue &Q,QElemType e);//入队在队尾插入元素e Status ShowQueue(LinkQueue Q);//打印当前队列元素Status GetTop(LinkQueue Q,QElemType &e);//获取当前队头元素，并用e返回Status DeQueue(LinkQueue &Q);//出队Status IsEmptyQueue(LinkQueue Q);//判断是否为空，队空返回1。

Status ClearQueue(LinkQueue &Q);//清空队列Status DestroyQueue(LinkQueue &Q);//销毁队列Status InitQueue(LinkQueue &Q){//传地址，修改QQ.rear=Q.front=(QNode *)malloc(sizeof(QNode));//指向头结点if(!Q.rear)cout<<"Error Overflow!"<<endl;Q.front->next=NULL;Q.Length=0;return 0;}Status EnQueue(LinkQueue &Q,QElemType e){//在队尾插入新的节点，需要开辟空间QNode *p=(QNode *)malloc(sizeof(QNode));if(!p) cout<<"分配内存失败"<<endl;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;if(Q.front->next==NULL)Q.front->next=p;Q.Length++;return 0;}Status ShowQueue(LinkQueue Q){QNode *p;p=Q.front->next;//p指向第一个元素if(Q.front==Q.rear){cout<<endl<<"当前队列为空！没有元素可以显示"<<endl;return 0;}cout<<endl<<"当前队列共计"<<Q.Length<<" 个元素"<<endl;cout<<"------------------------------当前队列元素为：-------------------"<<endl;while(p!=Q.rear){cout<<p->data<<" ";p=p->next;//不能用p++}cout<<p->data<<endl;return 0;}Status GetTop(LinkQueue Q,QElemType &e){e=Q.front->next->data;return OK;}Status DeQueue(LinkQueue &Q){if(Q.front==Q.rear)cout<<endl<<"队列为空，没有元素可以删除！"<<endl;else{Q.front->next=Q.front->next->next;Q.Length--;}return OK;}Status IsEmptyQueue(LinkQueue Q){if(Q.front==Q.rear)return 1;elsereturn 0;}Status DestroyQueue(LinkQueue &Q){if(Q.front!= NULL){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear; //释放一块内存要做两点：1.释放指向它的指针。

第1篇一、实验目的本次实验旨在通过实际操作，加深对栈这一数据结构的理解，掌握栈的基本操作，包括初始化、入栈、出栈、取栈顶元素、判栈空等。

同时，通过实验练习，提高编程能力和问题解决能力。

二、实验内容1. 栈的定义及特点2. 栈的顺序存储结构3. 栈的链式存储结构4. 栈的基本操作5. 栈的应用实例三、实验过程1. 栈的定义及特点栈是一种后进先出（LIFO）的数据结构，它只允许在一端进行插入和删除操作。

栈的顶元素总是最后被插入的元素，也是最先被删除的元素。

2. 栈的顺序存储结构顺序存储结构是使用数组来实现栈。

定义一个数组作为栈的存储空间，同时定义一个指针top来指示栈顶元素的位置。

3. 栈的链式存储结构链式存储结构是使用链表来实现栈。

定义一个节点结构体，其中包含数据和指向下一个节点的指针。

头节点作为栈顶元素。

4. 栈的基本操作（1）初始化：创建一个空栈，top指针指向栈底。

（2）入栈：将新元素插入到栈顶。

如果栈满，则进行扩容。

（3）出栈：删除栈顶元素，并将其返回。

如果栈空，则返回错误信息。

（4）取栈顶元素：返回栈顶元素的值，但不删除栈顶元素。

（5）判栈空：判断栈是否为空，如果为空，则返回true；否则，返回false。

5. 栈的应用实例（1）括号匹配检验：利用栈判断一个字符串中的括号是否匹配。

（2）算术表达式求值：利用栈实现算术表达式求值，包括四则运算和括号。

四、实验结果与分析1. 初始化栈初始化栈后，栈为空，top指针指向栈底。

2. 入栈操作将元素1、2、3依次入栈，栈的状态如下：```top -> 3 -> 2 -> 1```3. 出栈操作依次出栈元素，栈的状态如下：```top -> 2 -> 1```4. 取栈顶元素取栈顶元素2，栈的状态不变。

5. 判栈空当栈中只有一个元素时，判断栈为空，返回false。

6. 括号匹配检验对于字符串"((()))"，括号匹配检验结果为true；对于字符串"(()))"，括号匹配检验结果为false。

数据结构实验报告实验名称：实验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<<"种摆放方法。

数据结构栈和队列实验报告一、实验目的本次实验的主要目的是深入理解和掌握数据结构中的栈和队列的基本概念、操作原理以及实际应用。

通过编程实现栈和队列的相关操作，加深对其特性的认识，并能够运用栈和队列解决实际问题。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验原理（一）栈栈（Stack）是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out，LIFO）的原则。

可以将栈想象成一个只有一端开口的容器，元素只能从开口端进出。

入栈操作（Push）将元素添加到栈顶，出栈操作（Pop）则从栈顶移除元素。

（二）队列队列（Queue）也是一种线性表，但其操作遵循“先进先出”（FirstIn First Out，FIFO）的原则。

队列就像是排队买票的队伍，先到的人先接受服务。

入队操作（Enqueue）将元素添加到队列的末尾，出队操作（Dequeue）则从队列的头部移除元素。

四、实验内容（一）栈的实现与操作1、定义一个栈的数据结构，包含栈顶指针、存储元素的数组以及栈的最大容量等成员变量。

2、实现入栈（Push）操作，当栈未满时，将元素添加到栈顶，并更新栈顶指针。

3、实现出栈（Pop）操作，当栈不为空时，取出栈顶元素，并更新栈顶指针。

4、实现获取栈顶元素（Top）操作，返回栈顶元素但不进行出栈操作。

5、实现判断栈是否为空（IsEmpty）和判断栈是否已满（IsFull）的操作。

（二）队列的实现与操作1、定义一个队列的数据结构，包含队头指针、队尾指针、存储元素的数组以及队列的最大容量等成员变量。

2、实现入队（Enqueue）操作，当队列未满时，将元素添加到队尾，并更新队尾指针。

3、实现出队（Dequeue）操作，当队列不为空时，取出队头元素，并更新队头指针。

4、实现获取队头元素（Front）操作，返回队头元素但不进行出队操作。

5、实现判断队列是否为空（IsEmpty）和判断队列是否已满（IsFull）的操作。

数据结构栈和队列实验报告南京信息⼯程⼤学实验（实习）报告实验（实习）名称栈和队列⽇期2017.11.8 得分指导⽼师崔萌萌系计算机系专业软件⼯程年级2016 班次(1) 姓名学号⼀、实验⽬的1、学习栈的顺序存储和实现，会进⾏栈的基本操作2、掌握递归3、学习队列的顺序存储、链式存储，会进⾏队列的基本操作4、掌握循环队列的表⽰和基本操作⼆、实验内容1、⽤栈解决以下问题：（1）对于输⼊的任意⼀个⾮负⼗进制数，显⽰输出与其等值的⼋进制数，写出程序。

（2）表达式求值，写出程序。

2、⽤递归写出以下程序：（1）求n！。

（2）汉诺塔程序，并截图显⽰3、4、5个盘⼦的移动步骤,写出移动6个盘⼦的移动次数。

3、编程实现：（1）创建队列，将asdfghjkl依次⼊队。

（2）将队列asdfghjkl依次出队。

4、编程实现创建⼀个最多6个元素的循环队列、将ABCDEF依次⼊队，判断循环队列是否队满。

三、实验步骤1.栈的使⽤1.1 ⽤栈实现进制的转换：代码如下：#include#includeusing namespace std;int main(){stack s; //栈s;int n,radix;printf("请输⼊要转换的⼗进制⾮负整数： ");scanf("%d",&n);printf("请输⼊⽬标进制： ");scanf("%d",&radix);printf("转换为%d进制： ",radix);while(n) {s.push(n%radix);n /= radix;}while(!s.empty()) { //⾮空printf("%d",s.top());s.pop();}printf("\n");return 0;}运⾏结果如下：2.2 求表达式的值代码如下：#include#include#include#include#define true 1#define false 0#define OPSETSIZE 8typedef int Status;unsigned char Prior[8][8] = { //运算符优先级表// '+' '-' '*' '/' '(' ')' '#' '^'/*'+'*/ '>','>','<','<','<','>','>','<',/*'-'*/ '>','>','<','<','<','>','>','<',/*'*'*/ '>','>','>','>','<','>','>','<',/*'/'*/ '>','>','>','>','<','>','>','<',/*'('*/ '<','<','<','<','<','=',' ','<',/*')'*/ '>','>','>','>',' ','>','>','>',/*'#'*/ '<','<','<','<','<',' ','=','<',/*'^'*/ '>','>','>','>','<','>','>','>'};typedef struct StackChar { //StackChar类型的结点SC char c;struct StackChar *next;}SC;struct StackFloat *next;}SF;SC* Push(SC* s,char c) //SC类型的指针Push，返回p{SC* p = (SC* )malloc(sizeof(SC));p->c = c;p->next = s;return p;}SF* Push(SF* s,float f) //SF类型的指针Push，返回p{SF* p = (SF* )malloc(sizeof(SF));p->f = f;p->next = s;return p;}SC* Pop(SC* s) //SC类型的指针Pop{SC* q = s;s = s->next;free(q);return s;}SF* Pop(SF* s) //SF类型的指针Pop{SF* q = s;s = s->next;free(q);return s;}float Operate(float a,unsigned char theta, float b) //计算函数Operate { switch(theta){case '+': return a+b;case '-': return a-b;case '*': return a*b;case '/': return a/b;case '^': return pow(a,b);default : return 0;}char OPSET[OPSETSIZE] = {'+','-','*','/','(',')','#','^'};Status In(char Test,char *TestOp){int Find = false;for (int i=0; i< OPSETSIZE; i++) {if(Test == TestOp[i]) Find = true;}return Find;}Status ReturnOpOrd(char op,char *TestOp){for(int i=0; iif(op == TestOp[i]) return i;}}char precede(char Aop, char Bop){return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];}float EvaluateExpression(char* MyExpression)//表达式的运算符优先算法{//OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合SC* OPTR = NULL; //运算符栈，字符元素SF* OPND = NULL; //运算数栈，实数元素char TempData[20];float Data,a,b;char theta, *c, Dr[] = {'#','\0'};OPTR = Push(OPTR,'#');c = strcat(MyExpression,Dr);strcpy(TempData,"\0"); //字符串拷贝函数while (*c != '#' || OPTR->c != '#') {if (!In(*c, OPSET)) {Dr[0] = *c;strcat(TempData,Dr); //字符串连接函数c++;if (In(*c, OPSET)) {Data = atof(TempData); //字符串转换函数(double) OPND = Push(OPND, Data); strcpy(TempData,"\0");}} else { //不是运算符则进栈switch (precede(OPTR->c, *c))case '<': //栈顶元素优先级低OPTR=Push(OPTR, *c); c++; break;case '=': //去括号并接收下⼀字符OPTR = Pop(OPTR); c++; break;case '>': //退栈并将运算结果⼊栈theta = OPTR->c; OPTR = Pop(OPTR);b = OPND->f; OPND = Pop(OPND);a = OPND->f; OPND = Pop(OPND);OPND = Push(OPND, Operate(a, theta, b)); break;}}}return OPND->f;}int main(){char s[128];printf("请输⼊表达式: \n");scanf("%s",s);printf("该表达式的值为: \n");printf("%s = ",s);printf("%g\n",EvaluateExpression(s)); // %g return 0; }运⾏结果如下：2.递归的使⽤2.1 求n！：代码如下：#includeint Fact(int n){if(0 == n) return 1;else return n*Fact(n-1);}{int n;scanf("%d",&n);printf("%d的阶乘为：",n);printf("%d",Fact(n));return 0;}运⾏结果如下：2.2 哈诺塔：代码如下：#includeint Hanoi(int n,char a,char b,char c) { if(1 == n)printf("%c-%d->%c ",a,1,c);else{Hanoi(n-1,a,c,b);printf("%c-%d->%c ",a,n,c);Hanoi(n-1,b,a,c);}return 0;}int main(){int n;char a='A',b='B',c='C';printf("请输⼊汉诺塔的层数: "); scanf("%d",&n);Hanoi(n,a,b,c);printf("\n");return 0;}运⾏结果如下：n=3时n=4时n=5时n=6时由3,4,5可推知n 层哈诺塔需要移动 12 n次；n=6时,需要移动63次。

栈和队列基本操作实验报告实验二堆栈和队列基本操作的编程实现【实验目的】堆栈和队列基本操作的编程实现要求:堆栈和队列基本操作的编程实现(2学时，验证型)，掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。

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

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

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

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

【实验分析、说明过程】分析:进栈操作先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下: 将新结点p的指针域指向原栈顶S(执行语句p->next=S)。

将栈顶S指向新结点p(执行语句S=p)。

注:进栈操作的?与?语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。

出栈操作先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下: 结点p 指针域指向原栈顶S(执行语句p=S)。

栈顶S指向其的下一个结点(执行语句S=S->next)释放p结点空间(执行语句free(p))。

队列分析:用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。

队列中元素的结构和前面单链表中的结点的结构一样。

为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。

【思考问题】1. 栈的顺序存储和链表存储的差异,答:栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。

链表存储:通过链表的存储可以实现链表中任意位置的插入元素，删除任意元素，可以实现无序进出。

2. 还会有数据移动吗,为什么,答:栈的顺序存储不会有数据移动，移动的只是指向该数据地址的指针。

数据结构堆栈实验报告篇一：数据结构-堆栈和队列实验报告实验报告实验二堆栈和队列实验目的：1.熟悉栈这种特殊线性结构的特性；2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算；3.熟悉队列这种特殊线性结构的特性；3.熟练掌握队列在链表存储结构下的基本运算。

实验原理：堆栈顺序存储结构下的基本算法；堆栈链式存储结构下的基本算法；队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容：3-18 链式堆栈设计。

要求（1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d);（2）设计一个主函数对链式堆栈进行测试。

测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素；（3）定义数据元素的数据类型为如下形式的结构体，Typedef struct{c(本文来自：小草范文网:数据结构堆栈实验报告)har taskName[10];int taskNo;}DataType;首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。

3-19 对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。

现要求：（1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空；（2）编写一个主函数进行测试。

实验结果：3-18typedef struct snode{DataType data;struct snode *next;} LSNode;/*初始化操作：*/void StackInitiate(LSNode **head)/*初始化带头结点链式堆栈*/{if((*head = (LSNode *)malloc(sizeof(LSNode))) == NULL) exit(1); (*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;}/*出栈操作：*/int StackPop(LSNode *head, DataType *d)/*出栈并把栈顶元素由参数d带回*/{LSNode *p = head->next;if(p == NULL){printf("堆栈已空出错！");return 0;}head->next = p->next;/*删除原栈顶结点*/ *d = p->data; /*原栈顶结点元素赋予d*/ free(p); /*释放原栈顶结点内存空间*/ return 1;}/*取栈顶数据元素操作：*/int StackTop(LSNode *head, DataType *d)/*取栈顶元素并把栈顶元素由参数d带回*/{LSNode *p = head->next;if(p == NULL){printf("堆栈已空出错！");return 0;}*d = p->data;return 1;}/*撤销*/void Destroy(LSNode *head){LSNode *p, *p1;p = head;while(p != NULL){p1 = p;p = p->next;free(p1);}}（2）主函数程序：#include#includetypedef int DataType;#include "LinStack.h"void main(void){ LSNode *myStack;int i, x;StackInitiate(&myStack);for(i=0;i { if(StackPush(myStack,i+1)==0) {printf("error!\n");return;}}if(StackTop(myStack, &x)==0){printf("error!\n");return;}elseprintf("The element of local top is :%d\n",x); printf( "The sequence of outing elements is:\n"); while(StackNotEmpty(myStack)){StackPop(myStack, &x);printf("%d ", x);}printf("\n");Destroy(myStack);printf("This program is made by\n"); }运行结果为：（3）设计结构体和测试函数如下：#include#include#includetypedef struct{char taskName[10];int taskNo;}DataType;#include"LinStack.h"void main(){LSNode *myStack;FILE *fp;DataType task,x;if((fp=fopen("task.txt","r"))==NULL){printf("不能打开文件task.txt!\n");exit(0);}StackInitiate(&myStack);while(!feof(fp)){fscanf(fp,"%s %d",&task.taskName,&task.taskNo); StackPush(myStack,task);}fclose(fp);while(StackNotEmpty(myStack)){StackPop(myStack,&x);printf("%s %d\n",x.taskName,x.taskNo); } Destroy(myStack);printf("This program is made by \n");}运行结果为：3-19（1）typedef struct{DataType queue[MaxQueueSize];int front; /*队头指针*/int count;/*计数器*/} SeqCQueue;/*初始化操作：QueueInitiate(SeqCQueue *Q) */ void QueueInitiate(SeqCQueue *Q)/*初始化顺序循环队列Q */{Q->front=0; /*定义初始队头指针下标*/Q->count=0;/*定义初始计数器值*/}/*判非空否操作：QueueNotEmpty(SeqCQueue Q)*/ int QueueNotEmpty(SeqCQueue Q)篇二：数据结构栈和队列实验报告一、实验目的和要求(1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。

一、实验目的1. 理解栈和队列的基本概念、特点及逻辑结构。

2. 掌握栈和队列的存储结构，包括顺序存储结构和链式存储结构。

3. 熟练掌握栈和队列的基本操作，如入栈、出栈、入队、出队等。

4. 分析栈和队列在实际问题中的应用，提高解决实际问题的能力。

二、实验内容1. 栈和队列的定义及特点2. 栈和队列的存储结构3. 栈和队列的基本操作4. 栈和队列的实际应用案例分析三、实验过程1. 栈和队列的定义及特点栈（Stack）是一种后进先出（Last In First Out，LIFO）的数据结构，它只允许在一端进行插入和删除操作。

栈的典型应用场景有函数调用、递归算法等。

队列（Queue）是一种先进先出（First In First Out，FIFO）的数据结构，它允许在两端进行插入和删除操作。

队列的典型应用场景有打印队列、任务队列等。

2. 栈和队列的存储结构（1）顺序存储结构栈和队列的顺序存储结构使用数组来实现。

对于栈，通常使用数组的一端作为栈顶，入栈操作在栈顶进行，出栈操作也在栈顶进行。

对于队列，通常使用数组的一端作为队首，入队操作在队尾进行，出队操作在队首进行。

（2）链式存储结构栈和队列的链式存储结构使用链表来实现。

对于栈，每个元素节点包含数据和指向下一个节点的指针。

入栈操作在链表头部进行，出栈操作在链表头部进行。

对于队列，每个元素节点包含数据和指向下一个节点的指针。

入队操作在链表尾部进行，出队操作在链表头部进行。

3. 栈和队列的基本操作（1）栈的基本操作- 入栈（push）：将元素添加到栈顶。

- 出栈（pop）：从栈顶删除元素。

- 获取栈顶元素（peek）：获取栈顶元素，但不删除它。

- 判断栈空（isEmpty）：判断栈是否为空。

（2）队列的基本操作- 入队（enqueue）：将元素添加到队列尾部。

- 出队（dequeue）：从队列头部删除元素。

- 获取队首元素（peek）：获取队首元素，但不删除它。

实验日期2010.4.26 教师签字成绩实验报告【实验名称】第三章栈和队列的基本操作及应用【实验目的】（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。

【实验内容】1.链栈的基本操作（链栈的初始化、进栈、出栈以及取栈顶的值）#include "stdio.h"#include "malloc.h"#include "stdlib.h"typedef int Elemtype;typedef struct stacknode {Elemtype data;stacknode * next;}StackNode;typedef struct {stacknode * top; //栈顶指针}LinkStack;/*初始化链栈*/void InitStack(LinkStack * s){ s->top=NULL;printf("\n已经初始化链栈！\n");}/*链栈置空*/void setEmpty(LinkStack * s){ s->top=NULL;printf("\n链栈被置空！\n");}/*入栈*/void pushLstack(LinkStack * s, Elemtype x){ StackNode * p;p=(StackNode *)malloc(sizeof(StackNode)); //建立一个节点。

p->data=x;p->next=s->top; //由于是在栈顶pushLstack，所以要指向栈顶。

s->top=p; //插入}/*出栈*/Elemtype popLstack(LinkStack * s){ Elemtype x;StackNode * p;p=s->top; //指向栈顶if (s->top ==0){ printf("\n栈空，不能出栈！\n");exit(-1);}x=p->data;s->top=p->next; //当前的栈顶指向原栈的nextfree(p); //释放return x;}/*取栈顶元素*/Elemtype StackTop(LinkStack *s){ if (s->top ==0){ printf("\n链栈空\n");exit(-1);}return s->top->data;}/*遍历链栈*/void Disp(LinkStack * s){ printf("\n链栈中的数据为：\n");printf("=======================================\n");StackNode * p;p=s->top;while (p!=NULL){ printf("%d\n",p->data);p=p->next;}printf("=======================================\n");}void main(){ printf("================= 链栈操作=================\n\n");int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack));int cord;do{ printf("\n");printf("第一次使用必须初始化！\n");printf("\n");printf("\n 主菜单\n");printf("\n 1 初始化链栈\n");printf("\n 2 入栈\n");printf("\n 3 出栈\n");printf("\n 4 取栈顶元素\n");printf("\n 5 置空链栈\n");printf("\n 6 结束程序运行\n");printf("\n--------------------------------\n");printf("请输入您的选择( 1, 2, 3, 4, 5,6)");scanf("%d",&cord);printf("\n");switch(cord){ case 1:{ InitStack(s);Disp(s);}break;case 2:{printf("输入将要压入链栈的数据的个数：n=");scanf("%d",&n);printf("依次将%d个数据压入链栈：\n",n);for(i=1;i<=n;i++){scanf("%d",&a);pushLstack(s,a);}Disp(s);}break;case 3:{ printf("\n出栈操作开始!\n");printf("输入将要出栈的数据个数：m=");scanf("%d",&m);for(i=1;i<=m;i++){printf("\n第%d次出栈的数据是：%d",i,popLstack(s));}Disp(s);}break;case 4:{ printf("\n\n链栈的栈顶元素为：%d\n",StackTop(s));printf("\n");}break;case 5:{ setEmpty(s);Disp(s);}break;case 6:exit(0);}}while (cord<=6);}2.顺序栈的基本操作（顺序栈的初始化、进栈、出栈以及取栈顶的值）#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define STACKSIZE 100#define STACKINCREMENT 10#define null 0typedef struct {int *base;int *top;int stacksize;}SqStack;SqStack Initstack(){SqStack S;S.base=(int *)malloc(STACKSIZE*sizeof(int));if(!S.base){printf("\n存储分配失败\n");exit(0);}S.top=S.base;S.stacksize=STACKSIZE;return S;}int StackEmpty(SqStack S){if(S.top==S.base) return 1;else return 0;}int StackLength(SqStack S){int *p;p=S.base;for(int i=0;p!=S.top;p++,i++);return i;}int GetTop(SqStack S){int e;if(StackEmpty(S)) {printf("当前栈为空，不能执行此操作\n");exit(0);}e=*(S.top-1);return e;}int Push(SqStack &S,int e){if(StackLength(S)>=S.stacksize){S.base=(int*)realloc(S.base,(STACKSIZE+STACKINCREMENT)*sizeof(int));if(!S.base){printf("\n再分配存储失败\n");return 0;}S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return 1;}int Pop(SqStack &S){int e;if(StackEmpty(S)){printf("当前栈为空，不能执行此操作\n");exit(0);}e=*--S.top;return e;}void main(){int i=0,e;int *p;SqStack S;S=Initstack();printf("\n 1.元素进栈\n 2.元素出栈\n 3.取栈顶元素\n 4.求栈的长度\n 5.判栈空\n 6.退出\n");for(;i!=6;){printf("\n请选择你要进行的操作：");scanf("%d",&i);switch(i){case 1:printf("\n请输入进栈元素：");scanf("%d",&e);Push(S,e);p=S.base;printf("\n当前栈中元素：");if(StackEmpty(S))printf("当前栈为空\n");while(p!=S.top){printf("%d ",*p);p++;}break;case 2:printf("\n%d已出栈\n",Pop(S));printf("\n当前栈中元素：");if(StackEmpty(S))printf("当前栈为空\n");p=S.base;while(p!=S.top){printf("%d ",*p);p++;}break;case 3:printf("\n栈顶元素为：%d\n",GetTop(S));break;case 4:printf("\n栈的长度为：%d\n",StackLength(S));break;case 5:if(StackEmpty(S))printf("\n当前栈为空\n");else printf("\n当前栈不空\n");break;default:printf("\n退出程序\n");}}}3.顺序队列的基本操作（顺序队的初始化、进队、出对以及取对头）#include <stdio.h>#include <malloc.h>#define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef struct{ Elemtype queue[MAXNUM];int front;int rear;}sqqueue;/*队列初始化*/int initQueue(sqqueue *q){ if(!q) return FALSE;q->front=-1;q->rear=-1;return TRUE;}/*入队*/int append(sqqueue *q, Elemtype x){ if(q->rear>=MAXNUM-1) return FALSE;q->rear++;q->queue[q->rear]=x;return TRUE;/*出队*/Elemtype Delete(sqqueue *q){ Elemtype x;if (q->front==q->rear) return 0;x=q->queue[++q->front];return x;}/*判断队列是否为空*/int Empty(sqqueue *q){ if (q->front==q->rear) return TRUE;return FALSE;}/*取队头元素*/int gethead(sqqueue *q){ if (q->front==q->rear) return 0;return(q->queue[q->front+1]);}/*遍历队列*/void display(sqqueue *q){ int s;s=q->front;if (q->front==q->rear)printf("队列空!\n");else{printf("\n顺序队列依次为：");while(s<q->rear){s=s+1;printf("%d<-", q->queue[s]);}printf("\n");printf("顺序队列的队尾元素所在位置:rear=%d\n",q->rear);printf("顺序队列的队头元素所在位置:front=%d\n",q->front);}}/*建立顺序队列*/void Setsqqueue(sqqueue *q){ int n,i,m;printf("\n请输入将要入顺序队列的长度:");scanf("%d",&n);printf("\n请依次输入入顺序队列的元素值:\n");for (i=0;i<n;i++){ scanf("%d",&m);append(q,m);}main(){ sqqueue *head;int x,y,z,select;head=(sqqueue*)malloc(sizeof(sqqueue));do{printf("\n第一次使用请初始化！\n");printf("\n请选择操作(1--7):\n");printf("===================================\n");printf("1 初始化\n");printf("2 建立顺序队列\n");printf("3 入队\n");printf("4 出队\n");printf("5 判断队列是否为空\n");printf("6 取队头元素\n");printf("7 遍历队列\n");printf("===================================\n");scanf("%d",&select);switch(select){case 1:{ initQueue(head);printf("已经初始化顺序队列！\n");break;}case 2:{ Setsqqueue(head);printf("\n已经建立队列！\n");display(head);break;}case 3:{ printf("请输入队的值:\n ");scanf("%d",&x);append(head,x);display(head);break;}case 4:{ z=Delete(head);printf("\n队头元素%d已经出队！\n",z);display(head);break;}case 5:{ if(Empty(head))printf("队列空\n");elseprintf("队列非空\n");break;}case 6:{ y=gethead(head);printf("队头元素为:%d\n",y);break;}case 7:{ display(head);break;}}}while(select<=7);}4.链队列的基本操作（链队列的初始化、进队、出对操作）#include<stdio.h>#include<stdlib.h>#define ElemType inttypedef struct Qnode{ ElemType data;struct Qnode *next;}Qnodetype;typedef struct{ Qnodetype *front;Qnodetype *rear;}Lqueue;/*初始化并建立链队列*/void creat(Lqueue *q){ Qnodetype *h;int i,n,x;printf("输入将建立链队列元素的个数：n= ");scanf("%d",&n);h=(Qnodetype*)malloc(sizeof(Qnodetype));h->next=NULL;q->front=h;q->rear=h;for(i=1;i<=n;i++){ printf("链队列第%d个元素的值为：",i);scanf("%d",&x);Lappend(q,x);}}/*入链队列*/void Lappend(Lqueue *q,int x){ Qnodetype *s;s=(Qnodetype*)malloc(sizeof(Qnodetype));s->data=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*出链队列*/ElemType Ldelete(Lqueue *q){ Qnodetype *p;ElemType x;if(q->front==q->rear){ printf("队列为空!\n");x=0;}else{ p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;free(p);}return(x);}/*遍历链队列*/void display(Lqueue *q){ Qnodetype *p;p=q->front->next; /*指向第一个数据元素节点*/printf("\n链队列元素依次为：");while(p!=NULL){ printf("%d-->",p->data);p=p->next;}printf("\n\n遍历链队列结束！\n");}main(){ Lqueue *p;int x,cord;printf("\n*****第一次操作请选择初始化并建立链队列！*****\n ");do{ printf("\n 链队列的基本操作\n ");printf("=========================================\n");printf(" 主菜单\n");printf("=========================================\n");printf(" 1 初始化并建立链队列\n");printf(" 2 入链队列\n");printf(" 3 出链队列\n");printf(" 4 遍历链队列\n");printf(" 5 结束程序运行\n");printf("==========================================\n");scanf("%d",&cord);switch(cord){ case 1:{ p=(Lqueue *)malloc(sizeof(Lqueue));creat(p);display(p);}break;case 2:{ printf("请输入队列元素的值：x=");scanf("%d",&x);Lappend(p,x);display(p);}break;case 3:{ printf("出链队列元素：x=%d\n",Ldelete(p));display(p);}break;case 4:{display(p);}break;case 5:{exit (0);}}}while (cord<=5);}5.循环队列的基本操作：#include<stdio.h>#include<iostream.h>#include<malloc.h>#define maxsize 100struct Queue{int *base;int front;int rear;};void initQueue(Queue &Q){Q.base=(int *)malloc(maxsize*sizeof(int));Q.front=Q.rear=0;}int QueueLen(Queue Q){return(Q.rear-Q.front+maxsize)%maxsize;}void EnQueue(Queue &Q,int e){if((Q.rear+1)%maxsize==Q.front)cout<<"队列已满，无法插入!"<<endl;else{Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%maxsize;}}int DeQueue(Queue &Q,int &e){if(Q.rear==Q.front) cout<<"队列已空，无法删除!"<<endl;else{e=Q.base[Q.front]; Q.front=(Q.front+1)%maxsize;cout<<"被删除的元素是:"<<'\t'<<e<<endl;return e;}}void main(){Queue Q;initQueue(Q);loop:cout<<'\t'<<"请选择你要进行的操作:"<<endl;cout<<'\t'<<"1.插入元素"<<endl<<'\t'<<"2.删除元素"<<endl<<'\t'<<"3.求队列长度"<<endl<<'\t'<<"4.结束"<<endl;int i; cin>>i;switch(i){case(1):{int e;cout<<"请输入要插入的元素:"<<'\t';cin>>e;EnQueue(Q,e);goto loop;}case(2):{int e;DeQueue(Q,e);goto loop;}case(3):{int l;l=QueueLen(Q);cout<<"队列的长度为:"<<'\t'<<l<<endl;goto loop;}case(4):break;default:cout<<"输入错误，请重新输入!"<<endl;goto loop;}}6.两个栈实现队列的功能#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<iostream.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;//队列由两个栈S1,S2构成typedef struct{SqStack S1;SqStack S2;}Queue;void InitStack(SqStack *S){S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S->base) exit(0);S->top=S->base; S->stacksize=STACK_INIT_SIZE;}void 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(0);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*(S->top)++=e;}void pop(SqStack *S,SElemType *e){if(S->top==S->base) exit(0);S->top--; *e=*(S->top);}//队列的相关操作void InitQueue(Queue *Q){InitStack(&(Q->S1));InitStack(&(Q->S2));}void EnQueue(Queue *Q,SElemType e){push(&(Q->S1),e);}void DeQueue(Queue *Q,SElemType *e){if((Q->S2).top==(Q->S2).base){while((Q->S1).top!=(Q->S1).base){pop(&(Q->S1),e);push(&(Q->S2),*e);} pop(&(Q->S2),e);}else pop(&(Q->S2),e);}int QueueEmpty(Queue Q){if(Q.S1.base==Q.S1.top&&Q.S2.base==Q.S2.top) return 0;else return 1;}void main(){SElemType e; Queue Q; int i;InitQueue(&Q);for(i=0;i<10;i++) EnQueue(&Q,'a'+i);while(QueueEmpty(Q)!=0){DeQueue(&Q,&e); cout<<e;}cout<<endl;}7．用双端队列模拟栈#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define null 0typedef struct QNode{int data;struct QNode *next;struct QNode *prior;}QNode;typedef struct{QNode *front1,*front2;QNode *rear1,*rear2;}LinkDeque;LinkDeque InitQueue(){LinkDeque Q;Q.front1=Q.rear1=(QNode *)malloc(sizeof(QNode));if(!Q.front1){printf("\n存储分配失败\n");exit(0);}Q.front2=Q.rear2=(QNode *)malloc(sizeof(QNode));if(!Q.front2){printf("\n存储分配失败\n");exit(0);}Q.front1->next=Q.front2;Q.front2->next=Q.front1;return Q;}int EnDeque(LinkDeque &Q,int e){QNode *p;p=(QNode *)malloc(sizeof(QNode));if(!p){printf("\n存储分配失败\n");exit(0);}p->data=e;p->next=Q.front2;p->prior=Q.rear1;Q.rear1->next=p;Q.rear1=p;Q.rear2=Q.front1->next;return 1;}int DeDeque(LinkDeque &Q){int e;QNode *p;if(Q.front1==Q.rear1){printf("栈为空，不能执行删除操作\n");return 0;}p=Q.rear1;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;Q.rear1=p->prior;if(Q.front1==Q.front2){Q.rear1=Q.front1;Q.rear2=Q.front2;}free(p);return e;}int DequeLength(LinkDeque Q){int len=0;QNode *p;p=Q.front1->next;while(p!=Q.front2){len++;p=p->next;}return len;}int Gethead(LinkDeque Q){QNode *p;if(Q.front1!=Q.rear1){p=Q.rear1;return p->data;}}void main(){int i=0,e;LinkDeque Q;QNode *p;Q=InitQueue();printf("\n 1.元素进栈\n 2.元素出栈\n 3.求栈的长度\n 4.取栈顶元素\n 5.退出\n");for(;i!=5;){printf("\n请选择你要进行的操作：");scanf("%d",&i);switch(i){case 1:printf("\n请输入进栈元素：");scanf("%d",&e);EnDeque(Q,e);if(Q.front1!=Q.rear1){printf("\n当前栈元素:");p=Q.front1->next;while(p!=Q.front2){printf("%d ",p->data);p=p->next;}}else printf("当前栈为空\n");break;case 2:if(Q.front1!=Q.rear1)printf("\n已删除%d\n",DeDeque(Q));else printf("栈为空，不能此删除操作\n");if(Q.front1!=Q.rear1){printf("\n当前栈元素:");p=Q.front1->next;while(p!=Q.front2){printf("%d ",p->data);p=p->next;}}else printf("当前栈为空\n");break;case 3:printf("\n栈的长度：%d",DequeLength(Q));break;case 4:if(Q.front1!=Q.rear1)printf("\n栈顶元素:%d\n",Gethead(Q));else printf("栈为空，不能此删除操作\n");break;default:printf("\n结束程序\n");}}}8.约瑟夫队列:#include<stdio.h>#include<malloc.h>#include<iostream.h>#define len sizeof(struct QNode)struct QNode{int data;QNode *next;};void main(){int m,n,k,i,e,num=1;cout<<"请输入总人数:"<<endl; cin>>n;cout<<"请输入出局数:"<<endl; cin>>m;cout<<"请输入开始报数人的编号:"<<endl; cin>>k;QNode *Q,*p,*r,*t;Q=(QNode *)malloc(len);Q->next=Q;Q->data=1;p=Q;for(i=2;i<=n;i++){p->next=(QNode *)malloc(len);p=p->next;p->data=i;}p->next=Q;r=Q;t=r;for(i=1;i<=k-1;i++){t=r;r=r->next;}cout<<"出队顺序为:"<<endl;do{for(i=1;i<=m-1;i++){t=r;r=r->next;}e=r->data;t->next=r->next;r=t->next;cout<<e<<" ";num++;}while(num<=n);cout<<endl;}【小结讨论】1. 一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现，即双向栈共享邻接空间。