一.顺序栈
1.宏定义
#include
#include
#define MAXSIZE ****
#define datatype ****
2.结构体
typedef struct
{
datatype data[MAXSIZE];
int top;
}Seqstack;
3.基本函数
Seqstack *Init_Seqstack()
/*置空栈函数(初始化)1.先决条件:无;2.函数作用:首先建立栈空间,然后初始化栈顶指针,返回栈s的地址*/
{
Seqstack *s;
s=(Seqstack *)malloc(sizeof(Seqstack));
s->top=-1;
return s;
}
int Empty_Seqstack(Seqstack *s)
/*判栈空函数1.先决条件:初始化顺序栈;2.函数作用:判断栈是否为空,空返回1,不空返回0*/ {
if(s->top==-1) return 1;
else return 0;
}
int Push_Seqstack(Seqstack *s,datatype x)
/*入栈函数1.先决条件:初始化顺序栈2.函数作用:将数据x入栈,栈满则不能,成功返回1,因栈满失败返回0*/
{
if(s->top==MAXSIZE-1)
return 0;
s->top=s->top+1;
s->data[s->top]=x;
return 1;
}
int Pop_Seqstack(Seqstack *s,datatype *x)
/*出栈函数1.先决条件:初始化顺序栈2.函数作用:从栈中出一个数据,并将其存放到x中,成功返回1,因栈空失败返回0*/
{
if(s->top==-1)
return 0;
*x=s->data[s->top];
s->top--;
return 1;
}
int Top_Seqstack(Seqstack *s,datatype *x)
/*取栈顶元素函数1.先决条件:初始化顺序栈2.函数作用:取栈顶元素,并把其存放到x中,成功返回1,因栈空失败返回0*/
{
if(s->top==-1)
return 0;
*x=s->data[s->top];
return 1;
}
int Printf_Seqstack(Seqstack *s)
/*遍历顺序栈函数1.先决条件:初始化顺序栈2.函数作用:遍历顺序栈,成功返回1*/
{
int i,j=0;
for(i=s->top;i>=0;i--)
{
printf("%d ",s->data[i]);/*因datatype不同而不同*/
j++;
if(j%10==0)
printf("\n");
}
printf("\n");
return 1;
}
int Conversation_Seqstack(int N,int r)
/*数制转换函数(顺序栈)1.先决条件:具有置空栈,入栈,出栈函数2.函数作用:将N转换为r进制的数*/
{
Seqstack *s;
datatype x;
printf("%d转为%d进制的数为:",N,r);/*以后可以删除去*/
s=Init_Seqstack();
do
{
Push_Seqstack(s,N%r);
N=N/r;
}while(N);
while(Pop_Seqstack(s,&x))
{
if(x>=10)/*为了能转为十进制以上的*/
printf("%c",x+55);
else
printf("%d",x);
}
free(s);/*释放顺序栈*/
printf("\n");
return 1;
}
4.主函数
int main()
{
Seqstack *s;
int choice;
datatype x;
do{
printf("****************************************************************\n");
printf("1.置空栈 2.判栈空 3.入栈 4.出栈 5.取栈顶元素 6.遍历7.退出\n");
printf("****************************************************************\n");
printf("请输入选择(1~7):");
scanf("%d",&choice);
getchar();
switch(choice)
{
case 1:s=Init_Seqstack();
if(s)
printf("置空栈成功!\n");break;
case 2:if(Empty_Seqstack(s))
printf("此为空栈.\n");
else
printf("此不为空栈.\n");;break;
case 3:printf("请输入一个整数:");
scanf("%d",&x);
if(Push_Seqstack(s,x))
printf("入栈成功.\n");
else
printf("栈已满,无法入栈.\n");;break;
case 4:if(Pop_Seqstack(s,&x))
printf("出栈成功,出栈元素为:%d\n",x);
else
printf("出栈失败,因栈为空.\n");break;
case 5:if(Top_Seqstack(s,&x))
printf("取栈顶元素成功,栈顶元素为:%d\n",x);
else
printf("取栈顶元素失败,因栈为空.\n");
break;
case 6:Printf_Seqstack(s);break;
case 7:printf("谢谢使用!\n");break;
default :printf("输入错误，请重新输入!\n");break;
}
}while(choice!=7);
return 0;
}
二.链栈
1.宏定义
#include
#include
#define datatype ****
2.结构体
typedef struct snode
{
datatype data;
struct snode *next;
}Stacknode,*Linkstack;
3.基本函数
Linkstack Init_Linkstack()
/*初始化栈函数1.先决条件:无2.函数作用:初始化链栈,返回top地址*/
{
Linkstack top;
top=(Linkstack)malloc(sizeof(Stacknode));
top->next=NULL;
return top;
}
int Empty_Linkstack(Linkstack top)
/*判栈空函数1.先决条件:初始化链栈2.函数作用:判断栈是否为空,空返回1,不空返回0*/ {
if(top->next==NULL)
return 1;
else return 0;
}
int Push_Linkstack(Linkstack top,datatype x)
/*入栈函数1.先决条件:初始化链栈2.函数作用:将数据x入栈,成功返回1,失败返回0*/ {
Stacknode *p;
p=(Stacknode *)malloc(sizeof(Stacknode));
p->data=x;
p->next=top->next;
top->next=p;
return 1;
}
int Pop_Linkstack(Linkstack top,datatype *x)
/*出栈函数1.先决条件:初始化链栈2.函数作用:若栈空退出,若没空则将数据出栈,并将其存放到x中,成功返回1,因栈空失败返回0*/
{
if(top->next==NULL)
return 0;
Stacknode *p=top->next;
*x=p->data;
top->next=p->next;
free(p);
return 1;
}
int Top_Linkstack(Linkstack top,datatype *x)
/*取栈顶元素函数1.先决条件:初始化链栈2.函数作用:取栈顶元素并放到x中,成功返回1,因栈空失败返回0*/
{
if(top->next==NULL)
return 0;
*x=top->next->data;
return 1;
}
int Printf_Linkstack(Linkstack top)
/*遍历链栈函数1.先决条件:初始化链栈2.函数作用:遍历链栈,成功返回1*/
{
Stacknode *p=top->next;
int j=0;
while(p)
{
printf("%d ",p->data);/*因datatype不同而不同*/
j++;
if(j%10==0)
printf("\n");
p=p->next;
}
printf("\n");
return 1;
}
int Conversation_Linkstack(int N,int r)
/*数制转换函数(链栈)1.先决条件:具有置空栈,入栈,出栈函数2.函数作用:将N转换为r进制的数*/
{
Linkstack top;
datatype x;
printf("%d转为%d进制的数为:",N,r);/*以后可以删除去*/
top=Init_Linkstack();
do
{
Push_Linkstack(top,N%r);
N=N/r;
}while(N);
while(Pop_Linkstack(top,&x))
{
if(x>=10)/*为了能转为十进制以上的*/
printf("%c",x+55);
else
printf("%d",x);
}
printf("\n");
free(top);/*释放栈顶空间*/
return 1;
}
4.主函数
int main()
{
Linkstack top;
int choice;
datatype x;
do{
printf("****************************************************************\n");
printf("1.置空栈 2.判栈空 3.入栈 4.出栈 5.取栈顶元素 6.遍历7.退出\n");
printf("****************************************************************\n");
printf("请输入选择(1~7):");
scanf("%d",&choice);
getchar();
switch(choice)
{
case 1:top=Init_Linkstack();
if(top)
printf("置空栈成功!\n");break;
case 2:if(Empty_Linkstack(top))
printf("此为空栈.\n");
else
printf("此不为空栈.\n");;break;
case 3:printf("请输入一个整数:");
scanf("%d",&x);
if(Push_Linkstack(top,x))
printf("入栈成功.\n");
else
printf("栈已满,无法入栈.\n");;break;
case 4:if(Pop_Linkstack(top,&x))
printf("出栈成功,出栈元素为:%d\n",x);
else
printf("出栈失败,因栈为空.\n");break;
case 5:if(Top_Linkstack(top,&x))
printf("取栈顶元素成功,栈顶元素为:%d\n",x);
else
printf("取栈顶元素失败,因栈为空.\n");
break;
case 6:Printf_Linkstack(top);break;
case 7:printf("谢谢使用!\n");break;
default :printf("输入错误，请重新输入!\n");break;
}
}while(choice!=7);
return 0;
}
三.顺序队列
1.宏定义
#include
#include
#define MAXSIZE ****
#define datatype ****
2.结构体
typedef struct
{
datatype data[MAXSIZE];
int rear,front;
int num;
}Sequeue;
3.基本函数
Sequeue *Init_Sequeue()
/*初始化顺序队列函数1.先决条件:无2.函数作用:初始化顺序队列,成功返回顺序队列首地址q*/
{
Sequeue *q;
q=(Sequeue *)malloc(sizeof(Sequeue));
q->front=q->rear=MAXSIZE-1;
q->num=0;
return q;
}
int In_Sequeue(Sequeue *q,datatype x)
/*入队函数1.先决条件:初始化顺序队列2.函数作用:将数据x入队到q中,成功返回1,因队满失败返回0*/
{
if(q->num==MAXSIZE)
{
printf("队满.\n");/*可视情况删除此句*/
return 0;
}
else
{
q->rear=(q->rear+1)%MAXSIZE;
q->data[q->rear]=x;
q->num++;
return 1;
}
}
int Front_Sequeue(Sequeue *q,datatype *x)
/*取队头元素函数1.先决条件:初始化顺序表2.函数作用:取队头元素并将其存放到x中,成功返回1,因队空而失败返回0*/
{
if(q->num==0)
{
printf("队空.\n");/*可视情况删除此句*/
return 0;
}
*x=q->data[q->front+1];
return 1;
}
int Out_Sequeue(Sequeue *q,datatype *x)
/*出队函数1.先决条件:初始化顺序队列2.函数作用:将数据x入队到q中,成功返回1,因队空失败返回0*/
{
if(q->num==0)
{
printf("队空.\n");/*可视情况删除此句*/
return 0;
}
else
{
q->front=(q->front+1)%MAXSIZE;
*x=q->data[q->front];
q->num--;
return 1;
}
}
int Empty_Sequeue(Sequeue *q)
/*判空函数1.先决条件:初始化顺序队列2.函数作用:是空返回1,非空返回0*/
{
if(q->num==0)
return 1;
else return 0;
}
int Printf_Sequeue(Sequeue *q)
/*遍历函数1.先决条件:初始化顺序队列2.函数作用:遍历输出所有数据*/
{
int i,j=q->front+1,n=q->num;
for(i=0;i { printf("%d ",q->data[j]);/*因datatype数据不同而不同*/ j++; j=j%MAXSIZE; } printf("\n"); return 1; } 4.主函数 int main() { Sequeue *q; int choice; datatype x; do{ printf("**************************************************************\n"); printf("1.初始化 2.判队空 3.入队 4.出队 5.取队头元 6.遍历7.退出\n"); printf("**************************************************************\n"); printf("请输入选择(1~7):"); scanf("%d",&choice); getchar(); switch(choice) { case 1:q=Init_Sequeue(); if(q) printf("置空队成功!\n");break; case 2:if(Empty_Sequeue(q)) printf("此为空队.\n"); else printf("此不为空队.\n");;break; case 3:printf("请输入一个整数:"); scanf("%d",&x); if(In_Sequeue(q,x)) printf("入队成功.\n"); else printf("队已满,无法入队.\n");;break; case 4:if(Out_Sequeue(q,&x)) printf("出队成功,出队元素为:%d\n",x); else printf("出队失败,因队为空.\n");break; case 5:if(Front_Sequeue(q,&x)) printf("取队头元素成功,队头元素为:%d\n",x); else printf("取队头元素失败,因队为空.\n"); break; case 6:Printf_Sequeue(q);break; case 7:printf("谢谢使用!\n");break; default :printf("输入错误，请重新输入!\n");break; } }while(choice!=7); return 0; } 四.链队列 1.宏定义 #include #include #define datatype int 2.结构体 typedef struct node { datatype data; struct node *next; }Qnode; typedef struct { Qnode *front,*rear; }Lqueue; 3.基本函数 Lqueue *Init_Lqueue() /*初始化链队列函数 1.先决条件:无2.函数作用:初始化链队列,成功返回顺序队列首地址q(头结点)*/ { Lqueue *q; Qnode *p; q=(Lqueue *)malloc(sizeof(Lqueue)); p=(Qnode *)malloc(sizeof(Qnode)); p->next=NULL; q->front=p; q->rear=p; return q; } int In_Lqueue(Lqueue *q,datatype x) /*入队函数1.先决条件:初始化链队列2.函数作用:将数据x入队到q中,成功返回1*/ { Qnode *p; p=(Qnode *)malloc(sizeof(Qnode)); p->data=x; p->next=NULL; q->rear->next=p; q->rear=p; return 1; } int Empty_Lqueue(Lqueue *q) /*判空函数1.先决条件:初始化链队列2.函数作用:是空返回1,非空返回0*/ { if(q->front==q->rear) return 1; else return 0; } int Front_Lqueue(Lqueue *q,datatype *x) /*取队头元素函数1.先决条件:初始化链队列2.函数作用:取队头元素并将其存放到x中,成功返回1,因队空而失败返回0*/ { if(Empty_Lqueue(q)) { printf("队空.\n");/*可视情况删除此句*/ return 0; } *x=q->front->next->data; return 1; } int Out_Lqueue(Lqueue *q,datatype *x) /*出队函数1.先决条件:初始化链队列2.函数作用:将数据x入队到q中,成功返回1,因队空失败返回0*/ { Qnode *p; if(Empty_Lqueue(q)) { printf("队空.\n");/*可视情况删除此句*/ return 0; } p=q->front->next; *x=p->data; q->front->next=p->next; free(p); if(q->front->next==NULL) q->rear=q->front; return 1; } int Printf_Lqueue(Lqueue *q) /*遍历函数1.先决条件:初始化链队列2.函数作用:遍历输出所有数据*/ { Qnode *p; for(p=q->front->next;p!=NULL;p=p->next) printf("%d ",p->data);/*因datatype数据不同而不同*/ printf("\n"); return 1; } 4.主函数 int main() { Lqueue *q; int choice; datatype x; do{ printf("**************************************************************\n"); printf("1.初始化 2.判队空 3.入队 4.出队 5.取队头元 6.遍历7.退出\n"); printf("**************************************************************\n"); printf("请输入选择(1~7):"); scanf("%d",&choice); getchar(); switch(choice) { case 1:q=Init_Lqueue(); if(q) printf("置空队成功!\n");break; case 2:if(Empty_Lqueue(q)) printf("此为空队.\n"); else printf("此不为空队.\n");;break; case 3:printf("请输入一个整数:"); scanf("%d",&x); if(In_Lqueue(q,x)) printf("入队成功.\n"); break; case 4:if(Out_Lqueue(q,&x)) printf("出队成功,出队元素为:%d\n",x); else printf("出队失败,因队为空.\n");break; case 5:if(Front_Lqueue(q,&x)) printf("取队头元素成功,队头元素为:%d\n",x); else printf("取队头元素失败,因队为空.\n"); break; case 6:Printf_Lqueue(q);break; case 7:printf("谢谢使用!\n");break; default :printf("输入错误，请重新输入!\n");break; } }while(choice!=7); return 0; } 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法；队列链式存储结构下的基本算法；实验内容： 3-18链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化Stacklnitiate （S）, 非空否StackNotEmpty（S），入栈StackiPush（S,x）, 出栈StackPop （S,d）,取栈顶数据元素StackTop（S,d）; （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3, 4，5 入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 3-19对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当 前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写一个主函数进行测试。 实验结果： 3-18 typedef struct snode { DataType data; struct snode *n ext; } LSNode; /* 初始化操作：*/ 第三章栈和队列习题答案 一、基础知识题 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈) (2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } .. // 设Q1已有内容，Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的 第3章栈和队列 一、基础知识题 3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 3.2 链栈中为何不设置头结点? 3.3 循环队列的优点是什么? 如何判别它的空和满? 3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1 (2) SeqStack S1, S2, tmp; DataType x; ...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) { x=Pop(&S1) ; Push(&tmp,x); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &S1,x); Push( &S2, x); } (3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) { i=Pop(&T); Push(S,i); 封面： 安徽大学 网络工程 栈和队列的基本操作的实现 ______2010\4\12 【实验目的】 1.理解并掌握栈和队列的逻辑结构和存储结构； 2.理解栈和队列的相关基本运算； 3.编程对相关算法进行验证。 【实验内容】 （一）分别在顺序和链式存储结构上实现栈的以下操作（含初始化，入栈，出栈，取栈顶元素等）： 1.构造一个栈S，将构造好的栈输出； 2.在第1步所构造的栈S中将元素e 入栈，并将更新后的栈S输出； 3.在第2步更新后所得到的栈S中将栈顶元素出栈，用变量e返回该元素，并将更新后的栈S输出。（二）分别在链队列和循环队列上实现以下操作（初始化，入队，出队，取队头元素等）： 1.构造一个队列Q，将构造好的队列输出； 2.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出； 3.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出。 【要求】 1.栈和队列中的元素要从终端输入； 2.具体的输入和输出格式不限； 3.算法要具有较好的健壮性，对运行过程中的错误 操作要做适当处理。 三、实验步骤 1．本实验用到的数据结构 (1)逻辑结构：线性结构 (2)存储结构：程序一、四（顺序存储结构）； 程序二、三（链式存储结构）； 2．各程序的功能和算法设计思想 程序一：顺序栈 # include 《数据结构与算法》实验报告 专业班级学号 实验项目 实验二栈和队列的基本操作。 实验目的 1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。 2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。 实验容 题目1： 进制转换。利用栈的基本操作实现将任意一个十进制整数转化为R进制整数 算法提示： 1、定义栈的顺序存取结构 2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3、定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈输出栈顶元素 题目2： 利用队列的方式实现辉三角的输出。 算法设计分析 （一）数据结构的定义 1、栈的应用 实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。因此，运用栈先进后出的性质，即可完成进制转换。 栈抽象数据结构描述 typedef struct SqStack /*定义顺序栈*/ { int *base; /*栈底指针*/ int *top; /*栈顶指针*/ int stacksize; /*当前已分配存储空间*/ } SqStack; 2、队列的应用 由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成辉三角的递归性。即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造辉三角的第N+1行，从而实现打印辉三角的目的。 队列抽象数据结构描述 typedef struct SeqQueue { int data[MAXSIZE]; int front; /*队头指针*/ int rear; /*队尾指针*/ }SeqQueue; （二）总体设计 1、栈 （1）主函数：统筹调用各个函数以实现相应功能 int main() （2）空栈建立函数：对栈进行初始化。 int StackInit(SqStack *s) （3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。 int stackempty(SqStack *s) （4）入栈函数：将元素逐个输入栈中。 int Push(SqStack *s,int x) （5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。 int Pop(SqStack *s,int x) （6）进制转换函数：将十进制数转换为R进制数 int conversion(SqStack *s) 2、队列 （1）主函数：统筹调用各个函数以实现相应功能 void main() （2）空队列建立函数：对队列进行初始化。 SeqQueue *InitQueue() （3）返回队头函数：判断队是否为空，若不为空则返回队头元素。 int QueueEmpty(SeqQueue *q) （4）入队函数：将元素逐个输入队列中。 void EnQueue(SeqQueue *q,int x) （5）出队函数：若队列不空，则删除队列元素，并用x返回其值。 int DeQueue(SeqQueue *q) （6）计算队长函数：计算队列的长度。 int QueueEmpty(SeqQueue *q) （7）输出辉三角函数：按一定格式输出辉三角。 void YangHui(int n) 实验二堆栈和队列基本操作的编程实现 【实验目的】 堆栈和队列基本操作的编程实现 要求： 堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。 【实验性质】 验证性实验（学时数：2H） 【实验内容】 内容： 把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。 利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。 【思考问题】 1.栈的顺序存储和链表存储的差异？ 2.还会有数据移动吗？为什么？ 3.栈的主要特点是什么？队列呢？ 4.栈的主要功能是什么？队列呢？ 5.为什么会有环状队列？ 【参考代码】 （一）利用顺序栈实现十进制整数转换转换成r进制 1、算法思想 将十进制数N转换为r进制的数，其转换方法利用辗转相除法，以N=3456，r=8为例转换方法如下： N N / 8 （整除）N % 8（求余） 3456 432 0 低 432 54 0 54 6 6 6 0 6 高 所以：（3456）10 =（6600）8 我们看到所转换的8进制数按底位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。 算法思想如下：当N>0时重复1，2 ①若N≠0，则将N % r 压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。 ②用N / r 代替N 2、转换子程序 1-1 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出得序列为:123。(2分) T F 作者: DS课程组 单位: 浙江大学 1-2 在用数组表示得循环队列中,front值一定小于等于rear值。(1分) T F 作者: DS课程组 单位: 浙江大学 1-3 若一个栈得输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样得出栈序列。(2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}、(2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。(1分) T F 作者: DS课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、(1分) T F 2-1 设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、 a、g,则栈S得容量至少就是: (2分) 1. 1 2. 2 3. 3 4. 4 作者: DS课程组 实验报告 课程名称数据结构实验名称栈的基本操作与应用 姓名王灵慧专业班级软工18104 学号 201817040409 试验日期 2019-11-06试验地点E3-502指导老师邹汉斌成绩 一、实验目的 1．熟悉并能实现栈的定义和基本操作。 2．了解和掌握栈在递归和非递归算法的应用。 二、实验要求 1．进行栈的基本操作时要注意栈“后进先出”的特性。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。 2.已知函数t(n)=2*t(n/2)+n 其中t(0)=0，n为整数。编写程序实现： (1)计算t(n)的递归算法。 (2)分别用链式栈和顺序栈实现计算t(n)的非递归算法。 四、思考与提高 1．如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？ 五、实验步骤（每个实验内容包含代码、输入、输出、错误分析）： 1、实验内容（1）： #include 数据结构基础练习（栈和队列） 学号姓名蓝礼巍班级 . 一、选择题 1．有5个元素a,b,c,d,e依次进栈，允许任何时候出栈，则可能的出栈序列是 c 。 A．baecd B．dceab C．abedc D．aebcd 2．下列有关递归的叙述，不正确的是 b 。 A．在计算机系统内，执行递归函数是通过自动使用栈来实现的。 B．在时间和空间效率方面，递归算法比非递归算法好。 C．递归函数的求解过程分为递推（进栈）和回推（出栈）两个阶段。 D．在递归函数中必须有终止递归的条件。 3．栈和队列均属于哪一种逻辑结构 A 。 A．线性结构B．顺序结构C．非线性结构D．链表结构4．设输入元素为1、2、3、P和A，输入次序为123PA，元素经过栈后得到各种输出序列，则可以作为高级语言变量名的序列有 d 种。 A．4 B．5 C．6 D．7 5．一个队列的入队序列为a，b，c，d，则该队列的输出序列是 b 。 A．dcba B．abcd C．adcb D．cbda 6．在一个链式队列中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是b 。 A. f->next=s; f=s; B. r->next=s; r=s; C. s->next=s; r=s; D. s->next=f; f=s; 7．如果5个元素出栈的顺序是1、2、3、4、5，则进栈的顺序可能是 c 。 A．3、5、4、1、2 B．1、4、5、3、2 C．5、4、1、3、2 D．2、4、3、1、5 8．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。 A．i B．n-i C．n-i+1 D．不确定 二、填空题 1．栈和队列是一种特殊的线性表，其特殊性体现在是运算受限线性表。设现有元素e1,e2,e3,e4,e5和e6依次进栈，若出栈的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少是 3 。 2．顺序循环队列中，设队头指针为front，队尾指针为rear，队中最多可有MAX个元素，采用少用一个存储单元的方法区分队满与队空问题，则元素入队列时队尾指针的变化为 Rear=(rear+1)%MAX ；元素出队列时队头指针的变化为fort=(fotr+1)%MAX ；队列中的元素个数为 (rear-fort+MAX)%MAX 。若则可用表示队满的判别条件，队空的判别条件仍然为 rear==fort 。 三、解答题 栈和队列是操作受限的线性表，好像每本讲数据结构的数都是这么说的。有些书按照这个思路给出了定义和实现；但是很遗憾，这本书没有这样做，所以，原书中的做法是重复建设，这或许可以用不是一个人写的这样的理由来开脱。 顺序表示的栈和队列，必须预先分配空间，并且空间大小受限，使用起来限制比较多。而且，由于限定存取位置，顺序表示的随机存取的优点就没有了，所以，链式结构应该是首选。 栈的定义和实现 #ifndef Stack_H #define Stack_H #include "List.h" template class Stack : List//栈类定义 { public: void Push(Type value) { Insert(value); } Type Pop() { Type p = *GetNext(); RemoveAfter(); return p; } Type GetTop() { return *GetNext(); } List ::MakeEmpty; List ::IsEmpty; }; #endif 队列的定义和实现 #ifndef Queue_H #define Queue_H #include "List.h" template class Queue : List//队列定义{ public: void EnQueue(const Type &value) { LastInsert(value); } Type DeQueue() { Type p = *GetNext(); RemoveAfter(); IsEmpty(); return p; } Type GetFront() { return *GetNext(); } List ::MakeEmpty; List ::IsEmpty; }; #endif 测试程序 #ifndef StackTest_H #define StackTest_H #include "Stack.h" void StackTest_int() { cout << endl << "整型栈测试" << endl; 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现表达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释) 1、2. #include typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack; void StackTraverse(Sqstack S) { while (S.top != S.base) { cout << *(S.top-1) << endl; S.top--; } } Status InitStack(Sqstack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base){ exit(OVERFLOW); } 计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6 (总分：60.00，做题时间：90分钟) 一、单项选择题(总题数：14，分数：28.00) 1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年 全国试题1(2)分】 A.栈 B.队列√ C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。【2009年全国试题2(2)分】 A.1 B.2 C.3 √ D.4 按元素出队顺序计算栈的容量。b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈 中有aef,fea出栈，栈空，g进栈后出栈。所以栈S的容量至少是3。 3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 A.d,c，e，b，f,a B.c，b，d,a，e，f C.b，c，a，e，f，d D.a,f，e,d,c，b √ 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 A.b，a，c，d, e B.d,b，a，c，e C.d，b,c，a，e √ D.e，c，b，a，d a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 A.3 B.4 √ C.5 D.6 元素d进栈时，元素a，b，c已在栈中，d出栈后，P可以在a，b，c任一元素的前面进栈并出栈，也可以在元素a后出栈，c，b，a必须依次出栈，所以元素d开头的序列个数是4。 6.已知循环队列存储在一维数组A[0．n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。[2011年全国试题3(2)分】 A.0，0 B.0，n—1 √ C.n一1，0 建立堆栈和队列的库函数 摘要 堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。 队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为队头。用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。 关键词：堆栈；队列；线性表；存储结构 第1章前言 栈和队列是两种常用的数据结构，广泛应用在编译软件和程序设计，操作系统、事物管理等各类软件系统中。从数据结构角度看，栈和队列是受限制的线性表，栈和队列的数据元素具有单一的前驱和后继的线性关系；从抽象数据类型角度看，栈和队列又是两种重要的抽象数据类型。 第2章堆栈和队列定义 2.1 定义 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。 队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”的线性表。 2.2 队列基本操作 2.2.1栈的建立和初始化： voidInitStack(SqStack * &s) 实验二栈和队列的基本操作实现及其应用 一_一、实验目的 1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 一_二、实验内容 题目一、试写一个算法，判断依次读入的一个以@为结束符的字符序列，是否为回文。所谓“回文“是指正向读和反向读都一样的一字符串,如“321123”或“ableelba”。 相关常量及结构定义： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef 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) 一_三、数据结构与核心算法的设计描述 1、初始化栈 /* 函数功能：对栈进行初始化。参数：栈(SqStack S)。 成功初始化返回0,否则返回-1 */ int InitStack(SqStack &S) { S.base=(SElemType *)malloc(10*sizeof(SElemType)); if(!S.base) //判断有无申请到空间 return -1; //没有申请到内存,参数失败返回-1 S.top=S.base; S.stacksize=STACK_INIT_SIZE; S.base=new SElemType; return 0; } 2、判断栈是否是空 /*函数功能:判断栈是否为空。参数; 栈(SqStack S)。栈为空时返回-1,不为空返回0*/ int StackEmpty(SqStack S) { if(S.top==S.base) return -1; else return 0; } 3、入栈 /*函数功能:向栈中插入元素。参数; 栈(SqStack S),元素(SElemtype e)。成功插入返回0,否则返回-1 */ int Push(SqStack &S,SElemType e) { if(S.top-S.base>=S.stacksize) { S.base=(SElemType *)realloc(S.base,(S.stacksize+1) * sizeof(SElemType)); 数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 实验报告 课程名称_______数据结构实验__________________ 实验项目___ 栈和队列的基本操作与应用____ 实验仪器_____________________________________ 系别 ___ 计算机学院_______________ 专业 __________________ 班级/学号______ _________ 学生姓名_____________________ __ 实验日期__________________ 成绩_______________________ 指导教师____ __________________ 一、实验内容： 本次实验主要内容是表达式求值，主要通过栈和队列来编写程序，需要实现整数运算其中需要实现的功能有加减乘除以及括号的 运用，其中包含优先级的判断。 二、设计思想 1.优先级中加减、乘除、小括号、以及其他可以分组讨论优先 级 2.优先级关系用“>”“<”“=”来表示三种关系 3.为实现运算符优先使用两个栈：OPTR 运算符栈与OPND操作 符栈 4.运用入栈出栈优先级比较等方式完成运算 三、主要算法框架 1.建立两个栈InitStack(&OPTR); InitStack(&OPND); 2.Push“#”到 OPTR 3.判断优先级做入栈出栈操作 If“<” Push(&OPTR, c); If“=” Pop(&OPTR, &x) If“>” Pop(&OPTR, &theta); Pop(&OPND, &b); Pop(&OPND, &a); Push(&OPND, Operate(a, theta, b)); 四、调试报告 遇到的问题与解决 1.C语言不支持取地址符，用*S代替&S来编写代码 2.一开始没有计算多位数的功能只能计算一位数，在几个中间 不含运算符的数字中间做p = p*10+c运算。代码如下：p = p * 10 + c - '0'; c = getchar(); if (In(c)) { Push(&OPND, p); p = 0; } 主要算法改进设想： 1.可以用数组储存优先级 2.可以用C++编写，C++支持取地址符&。 五、实验总结 陕西科技大学实验报告 班级：学号：姓名：实验组别： 实验日期：报告日期：成绩： 报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称：栈与队列 一、实验目的 1.掌握栈、队列的思想及其存储实现。 2.掌握栈、队列的常见算法的程序实现。 二、实验要求 1.编写函数,采用链式存储实现栈的初始化、入栈、出栈操作。 2.编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作。 3.编写函数,采用链式存储实现队列的初始化、入队、出队操作。 4.编写函数,采用顺序存储实现队列的初始化、入队、出队操作。 5.编写一个主函数,在主函数中设计一个简单的菜单,分别调试 上述算法。 三、实验原理（流程图）： 四、实验数据（源代码）： package B_Stack; public class SqLinkStackDemo { // 主函数中设计一个简单的菜单,分别调试上述算法 public static void main(String[] args) throws Exception { /** 顺序栈 */ SqStack s = new SqStack(8); // 顺序栈栈的初始化 s.clear(); // 顺序栈的入栈 System.out.println("顺序栈入栈："); s.push(5); s.push('c'); s.push("Hello"); s.display(); // 顺序栈的出栈 System.out.println('\r' + "顺序栈出栈："); s.pop(); s.display(); /** 链表栈 */ LinkStack ls = new LinkStack(); // 链表栈的初始化 ls.clear(); // 链表栈的入栈 System.out.println('\r' + "链表栈入栈："); ls.push(88); ls.push('Z'); ls.push("HelloWorld"); ls.display(); // 顺序栈的出栈 System.out.println('\r' + "链表栈出栈："); ls.pop(); ls.display(); /** 顺序队列 */ CircleSqQueue circleSqQueue = new CircleSqQueue(8); // 顺序存储实现队列的初始化 circleSqQueue.clear(); // 顺序存储实现队列的入队 System.out.println('\r' + "顺序队列入队："); circleSqQueue.offer(666); circleSqQueue.offer("队列"); circleSqQueue.offer('Q'); circleSqQueue.display(); 实验二栈和队列的基本操作及其应用 一、实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。 2、掌握栈和队列的特点，即后进先出和先进先出的原则。 3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序 存储结构和链式存储结构上的实现。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生 可以根据自己的情况任选一个！ 题目一：回文判断（*） [问题描述] 对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如 “abba”是回文，而“abab”不是回文。 [基本要求] （1）数据从键盘读入； （2）输出要判断的字符串； （3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出 “Yes”，否则输出“No”。 [测试数据] 由学生任意指定。 题目二：顺序栈和循环队列基本操作（*） [基本要求] 1、实现栈的基本操作 六项基本操作的机制是：初始化栈：init_stack(S)；判断栈空：stack_empty(S)；取栈顶元素：stack_top(S,x)；入栈：push_stack(S,x)；出栈：pop_stack(S)；判断栈满：stack_full(S) 2、实现队列的基本操作 六项基本操作的机制是：初始化队列：init_queue(Q)；判断队列是否为空：queue_empty(Q)；取队头元素：queue_front(Q,x)；入队：enqueue(Q,x)；出队：outqueue(Q,x)；判断队列是否为满：queue_full(Q) [测试数据] 由学生任意指定。 题目三：商品货架管理（**） [问题描述] 商店货架以栈的方式摆放商品。生产日期越近的越靠近栈底，出货时从栈顶取货。一天营业结束，如果货架不满，则需上货。入货直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，使生产日期越近的越靠近栈底。 [基本要求] 设计一个算法，保证每一次上货后始终保持生产日期越近的商品越靠近栈底。 [实现提示] 可以用一个队列和一个临时栈作为周转。 [测试数据] 由学生任意指定。 三、实验前的准备工作 1、掌握栈的逻辑结构和存储结构。 2、熟练掌握栈的出栈、入栈等操作。 3、掌握队列的逻辑结构和存储结构。 4、熟练掌握队列的出队、入队等操作 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 *2、写出算法设计思路。 3、实验上要写出多批测试数据的运行结果。 4、结合运行结果，对程序进行分析。 题目四：Rails（ACM训练题） Description There 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 that time. It was possible to establish only a surface track. Moreover, it turned out that the数据结构-堆栈和队列实验报告
栈和队列习题答案
3 栈和队列答案
栈和队列的基本操作的实现
栈和队列的基本操作
实验二 堆栈和队列基本操作的编程实现
PTA第三章栈与队列练习题
栈的基本操作与应用
数据结构基础练习(栈和队列)
栈和队列(必备)
数据结构栈的定义及基本操作介绍
计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6
建立堆栈和队列的库函数
栈和队列的基本操作实现及其应用
数据结构练习 第三章 栈和队列
数据结构实验二-栈和队列的基本操作与应用
堆栈和队列
数据结构实验二(栈和队列)
相关主题
文本预览