堆栈和队列基本函数.docx
一?顺序栈
1. 宏定义
#include
#include
#define MAXSIZE ****
#define datatype ****
2. 结构体
typcdcf struct
{
datatype data[MAXS!ZEJ;
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==-l) return 1;
else return 0;
}
int Push_Seqstack(Seqstack *s，datatype x)
/*入栈函数1 ?先决条件:初始化顺序栈2?函数作用:将数据x入栈，栈满则不能，成功返回1,因栈满失败返回()*/
{
if(s->top==MAXSIZE-l)
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==-l)
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==-l)
return 0;
*x=s->data[s->top];
return 1;
}
int Printf_Seqstack(Seqstack *s)
/*遍历顺序栈函数1 ?先决条件:初始化顺序栈2?函数作用:遍历顺序栈，成功返回P/ {
int i,j=0;
for(i=s->top;i>=0;i-)
{
printf("%d n,s->data[i]);/*因datatype 不同而不同*/
j++；
if(j%!0==0)
printf(',\n M);
}
printf(n\n n);
return 1;
}
int Conversation_Seqstack(int N,int r)
/*数制转换函数(顺序栈)1 ?先决条件:具有置空栈，入栈，出栈函数2?函数作用:将N转换为r进制的数*/
{
Scqstack *s;
datatype x;
printf(n%d转为％d进制的数为:“,N,r);/*以后可以删除去*/
s=Init_Seqstack();
do
Push_Seqstack(s$N%r);
N=N/r;
}whilc(N);
while(Pop_Seqstack(s,&x))
{
if(x>=10)/*为了能转为十进制以上的*/ printf(” ％c”,x+55);
else
printf(” ％d”,x);
)
free(s);/*释放顺序栈*/
printf(n\n M);
return 1;
}
4.主函数
int main()
{
Scqstack *s;
int choice;
datatype x;
do{
printfCU.置空栈2 ?判栈空3 ?入栈4?出栈5 ?収栈顶元素6 ?遍历7 ?退出\「）;
printf（H请输入选择（1?7）:”）;
scanf(H%d'\&choice);
getchar(); switch(choice) case 1:s=Init_Seqstack();
if(s)
printf("B 空栈成功!\n H);break;
case 2:if(Empty_Seqstack(s))
printf(” 此为空栈An”);
else
printf(''此不为空栈.\n M);;break; case 3:printf("请输入一个整数:”);
scanf(” ％d”,&x); if(Push_Seqstack(s,x)) printf(n入栈成功An”);
else
printf('，栈已满，无法入栈An M);;break;
case 4:if(Pop_Seqstack(s,&x))
printf("出栈成功，出栈元素为:%d\n”,x);
else
printf(”出栈失败，因栈为空.\n u);break;
case 5:if(Top_Seqstack(s,&x))
print”取栈顶元素成功，栈顶元素为：%d\n”,x);
else
printf(“取栈顶元素失败，因栈为空AiT);
break;
case 6:Printf_Seqstack(s);break;
case 7:printf(M谢谢使用!\n");brcak;
default:printf("输入错误，请重新输入!\n");break;
}
}while(choice!=7);
return 0;
}
二链栈
1. 宏定义
#include
#includc
#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(sizcof(Stacknodc));
toponext二NULL;
return top;
}
int Empty_Linkstack(Linkstack top)
/*判栈空函数1 ?先决条件:初始化链栈2?函数作用:判断栈是否为空,空返回1,不空返回0引
if(top->next==N U LL)
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->ncxt=p;
return 1;
}
int Pop_Linkstack(Linkstack top^datatype *x)
八出栈函数1 ?先决条件:初始化链栈2?函数作用:若栈空退岀,若没空则将数据岀栈，并将其存放到x中，成功返回1,因栈空失败返回0*/
{
if(top->next==N U LL)
return 0;
Stacknode *p=top->next;
*x=p->data;
top->next=p->next;
free(p);
return 1;
}
int Top_Linkstack(Linkstack top,datatypc *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(H%d ",p->data);/*因datatype 不同而不同*/
j++；
if(j%10==0)
printf(n\n n);
p=p->next;
)
printf(H\n M);
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(H%d M,x);
}
printf(,,\ii M);
free(top);/*释放栈顶空间*/
return 1;
}
4.主函数
int main()
{
Linkstack top;
int choice;
datatype x;
do{
printfCl.置空栈2 ?判栈空3 ?入栈4?出栈5 ?取栈顶元素6遍历7 ?退出W);
printf(M请输入选择(1?7):”);
scanf(H%d'\&choice); getchar(); switch(choice) case 1:top=Init_Linkstack();
if(top)
printf("B 空栈成功!\n M);break;
case 2:if(Empty_Linkstack(top))
printf(”此为空栈An”);
else
printfC 毗不为空栈.\n");;break;
case 3:printf("请输入一个整数:")；
scanf(”％d”,&x);
if(Push_Linkstack(top,x))
printfC'入栈成功An”)；
else
printfC '栈已满，无法入栈An M);;break;
case 4:if(Pop_Linkstack(top,&x))
printfC*出栈成功，出栈元素为:%d\n",x); else
printfC* H J栈失败，因栈为空.\n'*);break;
case 5:if(Top_Linkstack(top,&x))
printfC?栈顶元素成功，栈顶元素为:％d\n”,x); else
printf(”取栈顶元素失败，因栈为空An”); break;
case 6:Printf_Linkstack(top);break;
case 7:printf(M谢谢使用!\n");break;
defai山：prinlf("输入错课，请重新输入!\n”);break;
}
}whilc(choicc!=7);
return 0;
三?顺序队列
1.宏定义
#include
#include
#define MAXSIZE ****
#dcfinc 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=();
return q;
}
int In_Sequeue(Sequeue *q,datatype x)
严入队函数1?先决条件:初始化顺序队列2?函数作用:将数据x入队到q中，成功返回1,因队满失败返回0*/
{
if(q->num==MAXSIZE)
{
printfC'队满An**);/*可视情况删除此句*/
return 0;
}
else
{
q->rear=(q->rear+ 1)%MAXSIZE;
q->datafq->rear]=x;
q->num++;
return 1;
)
}
int Front_Sequeue(Sequeue *q3atatype *x)
/*取队头元素函数1 ?先决条件:初始化顺序表2?函数作用:取队头元素并将其存放到x中咸功返回1,因队空而失败返回0旬
{
if(q->num==0)
printf（H队空.\『）;/*町视怙:况删除此句旬return 0;
*x=q->data[q->front+1];
return 1;
}
int Out_Sequeue(Sequeue 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];
qonum—；
return 1;
)
}
int Empty_Sequeue(Sequeue *q)
/*判空函数1?先决条件:初始化顺序队列2?函数作用:是空返回1,非空返回0*/
{
if(q->num==0)
return 1;
else return 0;
}
int PrintfLSequeue(Sequeue *q)
/*遍历函数1?先决条件:初始化顺序队列2?函数作用:遍历输岀所有数据引
{
int i,j=q->front+l,n=q->num;
for(i=0;i { printf("%d ",q->data[j]);/*因datatype 数据不同而不同*/ j++； j=j%MAXSIZE; } printf(n\ii M); return 1; } 4 ?主函数 int main() Sequeue *q; int choice; datatype x; do{ ■▲/* f I \ fix W^ ■* ▼" f printf（M l.初始化2.判队空3.入队4.出队5.取队头元6.遍历7.退出\n“）; ■▲ ,、/ f I ?士?上?士?上%L? ?&??上?士?上?&? ?土?士?&? ?上?上?&* ?士?&? ?土?士?&? ?上?&? *?V ?&? %V ?士?&? %V ?&? *?V ?^\ 11 \ W" ■#T^ #T* #T^ #T^ #T^ #T^ #T^ #T^ #T^ 吓?#T^ 吓?吓?\ B ? printf（M请输入选择（1?7）:”）; scanf(M%d n,&choice); getchar(); switch(choicc) { case l:q=lnit_Sequeue(); if(q) printf("H 空队成功!\n");break; case 2:if(Empty_Scqucuc(q)) printf(n此为空队An”); else printf(H此不为空队An n);;break; case 3:printf("请输入一个整数:")； scanf(H%d n,&x); if(In_Sequeue(q,x)) printf(“入队成功An”); else printf(H队已满，无法入队An H);;break; case 4:if(Out_Scqucuc(q,&x)) printf(”出队成功，出队元素为:%d\n”,x); else printfC*出队失败，因队为空An u);break; case 5:if(Front_Sequeue(q,&x)) printf("取队头元素成功，队头元素为:％d\n”,x); else printfC*取队头元素失败，因队为空An“）; break; case 6:Printf_Sequeue(q);break; case 7:printf(M谢谢便用!\n");break; default:printf(”输入错误，请重新输A!\n");break; } }while(choice!=7); return 0; 四?链队列 1?宏定义 # include #include #define datatype int 2. 结构体 typedef struct node { datatype data; struct node *next; JQnodc; 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->ncxt=NULL; q->front=p; q->rear=p; return q; } int In_Lqueue(Lqueue *q,datatype x) /*入队函数1 ?先决条件:初始化链队列2?函数作用:将数据x入队到q中咸功返回W { 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 datatype *x) /*出队函数1 ?先决条件:初始化链队列2?函数作用:将数据x入队到q中，成功返回1,因队空失败返回0*/ { Qnodc *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->ncxt==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{ printfCl.初始化2 ?判队空3入队4?出队5 ?取队头元6遍历7?退出W); printf(M请输入选择(1?7):”); scanf(n%d H,&choice); getchar(); switch(choicc) { case l:q=lnit_Lqueue(); if(q) printf("H 空队成功!\n");break; case 2:if(Empty_Lqucuc(q)) printf(n此为空队An”); else printf(H此不为空队An n);;break; case 3:printf("请输入一个整数:")； scanf(H%d n,&x); if(In_Lqueue(q,x)) printf(“入队成功An”); break; case 4:if(Out_Lqueue(q,&x)) printf("iTi队成功，出队元素为:%d\n",x); else printf(”出队失败，因队为空.\n n);break; case 5:if(Front_Lqueue(q,&x)) printf(”取队头元素成功，队头元素为:%d\n”,x); else printfCl队头元素失败，因队为空.\n“)； break; case 6:Printf_Lqueue(q);break; case 7:printf(H谢谢使用!\n");brcak; default:printf("输入错误，请重新输入!\ii");break; }while(choice!=7); return 0; 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 实验二堆栈和队列 实验目的： 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章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 第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); 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 《数据结构与算法》实验报告 专业班级学号 实验项目 实验二栈和队列的基本操作。 实验目的 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) 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课程组 第三章栈和队列练习题 一、单项选择题 1．一个顺序栈一旦被声明，其占用空间的大小（）。 A．已固定B．可以改变C．不能固定D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。 A．插入操作更加方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（）位置。 A．链头B．链尾C．链中D．任意位置 4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。 A．堆栈B．队列C．数组D．先性表 5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。 A．11 B．20 C．19 D．21 6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。 A．（rear+1)%m=front B．rear =front+1 C．rear=front D．（rear+1)%m-1=front 7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。 A．top->next=p; B．p->next=top->next; top->next=p; C．p->next=top; top=p; D．p->next=top->next; top=top->next; 8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。 A．x=top;top=top->next; B．x=top->data; 数据结构基础练习（栈和队列） 学号姓名蓝礼巍班级 . 一、选择题 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; 封面： 安徽大学 网络工程 栈和队列的基本操作的实现 ______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 计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编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．栈和队列的共同特点是( )。 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、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈与队列及其应用_ 一．实验目得及要求 （1）掌握栈与队列这两种特殊得线性表，熟悉它们得特性，在实际问题背景下灵活运用它们； （2）本实验训练得要点就是“栈”得观点及其典型用法； （3）掌握问题求解得状态表示及其递归算法，以及由递归程序到非递归程序得转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中得基本操作（栈得初始化、判栈空、入栈、出栈等）； （2）应用栈得基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中得基本操作（队列得初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中得语法检查（括号得匹配）。 （5）利用栈实现表达式得求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中得基本操作（栈得初始化、判栈空、入栈、出栈等）； A、顺序储存： ?代码部分： //Main、cpp: #include"SStack、h" int main() { SqStack S; SElemType e; int elect=1; InitStack(S); cout << "已经创建一个存放字符型得栈" << endl; while (elect) { Muse(); cin >> elect; cout << endl; switch (elect) { case 1: cout << "input data:"; cin >> e; Push(S, e); break; case 2: if(Pop(S, e)) {cout << e <<" is pop"<< endl; } else{cout<<"blank"< 习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。数据结构第三章栈和队列3习题
数据结构-堆栈和队列实验报告
栈和队列习题答案
完整版数据结构习题集第3章栈和队列
3 栈和队列答案
第三章栈和队列习题_数据结构电子教案
栈和队列的基本操作
PTA第三章栈与队列练习题
第三章栈和队列练习题
数据结构基础练习(栈和队列)
栈和队列(必备)
栈和队列的基本操作的实现
计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6
数据结构练习 第三章 栈和队列
第三章+栈和队列(参考答案)
数据结构_实验三_栈和队列及其应用
第3章栈与队列习题参考答案