实验二堆栈和队列实验目的：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{char 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<>#include<>typedef int DataType;#include ""void main(void){ LSNode *myStack;int i, x;StackInitiate(&myStack);for(i=0;i<5; 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<>#include<>typedef struct{char taskName[10];int taskNo;}DataType;#include""void main(){LSNode *myStack;FILE *fp;DataType task,x;if((fp=fopen("","r"))==NULL){printf("不能打开文件!\n");exit(0);}StackInitiate(&myStack);while(!feof(fp)){fscanf(fp,"%s %d",&,&;StackPush(myStack,task);}fclose(fp);while(StackNotEmpty(myStack)){StackPop(myStack,&x);printf("%s %d\n",,;}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)/*判断顺序循环队列Q非空否，非空时返回1，否则返回0 */{if!=0)return 1;else return 0;}/*入队列操作：QueueAppend(SeqCQueue *Q, DataType x)*/int QueueAppend(SeqCQueue *Q, DataType x)/*把数据元素x插入顺序循环队列Q的队尾，成功时返回1，否则返回0 */ {if(Q->count==MaxQueueSize){printf("The queue is full!\n");return 0;}else{ int r;r=Q->front+Q->count;Q->queue[r]=x;Q->count++;return 1;}}/*出队列操作：QueueDelete(SeqCQueue *Q, DataType *d)*/int QueueDelete(SeqCQueue *Q, DataType *d)/*删除顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0 */ {if(Q->count==0){printf("The queue is empty!\n");return 0;}else{*d=Q->queue[Q->front];Q->front=(Q->front+1)%MaxQueueSize;Q->count--;return 1;}}/*取对头数据元素操作：QueueGet(SeqCQueue Q, DataType *d)*/int QueueGet(SeqCQueue Q, DataType *d)/* 取顺序循环队列队头数据元素并赋值d，成功时返回1，否则返回0 */ {if==0){printf("The queue is empty!\n");return 0;}else{*d=[];return 1;}}（2）主函数程序：#include<>#define MaxQueueSize 100typedef int DataType;#include""void main(void){int i,j,d;SeqCQueue myQueue;QueueInitiate(&myQueue);if(QueueNotEmpty(myQueue)==0)printf("队列为空！请输入数据元素：\n"); /*判空*/for(i=0;i<=10;i++){if(QueueAppend(&myQueue,i+1)==0)break;}printf("元素个数为%d\n",; /*输出元素个数*/for(j=0;j<=9;j++){if(QueueDelete(&myQueue,&d)==0)break;printf("%d ",d); /*出队列并显示元素*/ }printf("\n");if(QueueNotEmpty(myQueue)==1)printf("队列不为空\n"); /*再次判空*/printf("This program is made by \n");}运行结果为：总结与思考对于堆栈和队列实验的操作，我明白了栈和队列这两种特殊线性结构的特性，初步掌握了栈在顺序存储结构和链表存储结构下的基本运算。