ADT栈与队列的编程与实现
一 实验目的：
加深对抽象数据类型 ADT 栈和队列的理解。
二 实验环境：
Microsoft Visual C++ 2010
三 实验内容：
编写程序实现 ADT 栈的定义，及常用操作（数组或指针实现）：
- 生成栈；
- Push
- Pop
编写程序实现 ADT 队列的定义，及常用操作： - 生成队列；
- Enqueues 入列；
- Isempty 判断是否队列为空。
四 实验步骤：
1.实验程序：
（1）ADT栈：
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
typedef struct node
{
int *base;
int *top;
int s;
}Stack;
int MakeEmpty(Stack &S);
int Push(Stack &S,int d);
void Pop(Stack &S);
int Get(Stack S);
void GetAll(Stack &S);
int main(int argc, char* argv[])
{
int a;
int b;
int c;
Stack S;
if(MakeEmpty(S))
printf(“初始化成功\n”);
printf("输入要压入栈数据的个数:");
scanf("%d",&a);
for(int n=0;n<a;n++)
{
printf("请输入压入栈的数据%d为:",n+1);
scanf("%d",&b);
Push(S,b);
}
GetAll(S);
printf("选择是否进行Pop操作，1为是，0为否：");
scanf("%d",&c);
if(c)
Pop(S);
GetAll(S);
system("pause");
return 0;
}
int MakeEmpty(Stack &S)//初始栈空间
{
S.base=new int[MAXSIZE];
if(!S.base) return 0;
S.top=S.base;
S.s=MAXSIZE;
return 1;
}
int Push(Stack &S,int d)//压栈
{
if(S.top-S.base==S.s) return 0;
S.top++;
*S.top=d;
return 1;
}
//出栈
void Pop(Stack &S)//出栈
{
printf(“栈顶值为%d，已取出\n”,*S.top);
S.top–;
}
int Get(Stack S)//取栈
{
if(S.top!=S.base)
return *(S.top-1);
}
void GetAll(Stack &S)//遍历栈
{
int i;
if(S.top==S.base) printf(“栈为空\n”);
else
{
printf(“当前链表不为空,栈内数据如下\n”);
i=S.top-S.base;
for(int j=0;j<i;j++)
{
printf(“%d\n”,*(S.top-j));
}
}
}
（2）ADT队列：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct{
char data[6];
int Front;
int Rear;
int Size;
}Queue;
void MakeQueue(Queue *Q) //初始化队列
{
Q->Front =0;
Q->Rear =0;
Q->Size =0;
}
int IsEmpty(Queue *Q)//判断队列是否为空
{
return Q->Size ==0;
}
void EnQueue(Queue *Q,int x) //入队列
{
Q->data[Q->Rear]=x;
Q->Rear ++;
Q->Front =Q->Rear -1;
Q->Size ++;
}
int main()
{
Queue Q;
MakeQueue(&Q);
int m=Q.Rear;
for(int i=0;i<m;i++)
printf("%d ",Q.data[i]);
if(IsEmpty(&Q))
printf("\n队列为空\n");
else
printf("\n队列不为空\n");
int f;
for(int k=0;k<6;k++)
{
printf("\n请输入下一个想要入列的数：");
scanf("%d",&f);
EnQueue(&Q,f);
printf("队列变为：");
m=Q.Rear;
int i;
for(i=0;i<m;i++)
printf("%d ",Q.data[i]);
if(IsEmpty(&Q))
printf("\n队列为空\n");
else
printf("\n队列不为空\n");
}
system("pause");
return 0;
}
2.程序实验结果：
（1）ADT栈：生成栈、压栈结果：
出栈结果：
（2）ADT队列：
开始时队列数据为0，判断队列为空，之后添加数据，直到队列达到最大（6），则无法再添加数据。
3.分析和改进：
（1）ADT栈：
压栈：首先判断栈是否已满，满则不进行数据压栈，未满则将栈段指向压入数据。
出栈：一次出栈，出一个数据，栈顶指针减一。
栈遍历：判断Top指针是否与底部指向同一数据，然后有Top指针指向的数据开始，依次输出数据。
（2）ADT队列：
入队列：指向头元素的指针不动，指向尾部指针加一，同时记录队列长度的Size加一。
判断队列是否为空：Size初始为0，入队列后加一，根据Size的值判断队列是否为空
五 实验小结：
更进一步了解了ADT栈与队列的定义，实现了Push、Pop以及队列入元素和判断是否为空的操作。