山东大学数据结构与算法分析:实验2 ADT栈与队列的编程与实现

一、实验目的

加深对抽象数据类型ADT栈和队列的理解；

二、实验原理

参照课本p.64-66，及Figure3.39-3.44；

​  课本p.82-83，及Figure3.57-3.60.

三、实验内容

编写程序实现ADT栈的定义，及常用操作（数组或指针实现）：

1) 生成栈；

2) Push

3) Pop

编写程序实现ADT队列的定义，及常用操作：

1) 生成队列；

2) Enqueues入列；

3) Isempty判断是否队列为空。

四、实验要求

1) 实现ADT栈的结构及操作；

2) 实现ADT队列的结构及操作，并给出应用。

五、实验源程序

（1）ADT栈

#include <stdio.h>
#define MAXSIZE 100
    typedef struct node
    {
        int *base;
        int *top;
        int stacksize;
    }Stack;

int InitStack(Stack &S);
int Push(Stack &S,int e);
void Pop(Stack &S);
int Get(Stack S);
void GetAll(Stack &S);
int main(int argc, char* argv[])
{   
    int index;
    int Value;
    int choice;
    Stack S;
    if(InitStack(S))
        printf("初始化成功\n");

    printf("输入要压入栈数据的个数:");
    scanf("%d",&index);
    for(int n=0;n<index;n++)
    {
        printf("请输入压入栈的数据%d为:",n+1);
        scanf("%d",&Value);
        Push(S,Value);
    }
    GetAll(S);
    printf("选择是否进行Pop操作，1为是，0为否：");
    scanf("%d",&choice);
    if(choice)
        Pop(S);
    GetAll(S);
    return 0;
}

int InitStack(Stack &S)        //初始栈空间    
{
    S.base=new int[MAXSIZE];
    if(!S.base) return 0;
    S.top=S.base;
    S.stacksize=MAXSIZE;
    return 1;
}

int Push(Stack &S,int e)          //压栈    
{
    if(S.top-S.base==S.stacksize) return 0;
    S.top++;
    *S.top=e;
    return 1;
}
//出栈
void Pop(Stack &S)      //删除S的栈顶元素，并用e来返回
{  
    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[100];
     int Front;
     int Rear;
     int Size;
}Queue;              
void InitQueue(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;
    InitQueue(&Q);
    EnQueue(&Q,20);            //入列操作
    EnQueue(&Q,20);
    EnQueue(&Q,11);
    EnQueue(&Q,1);
    EnQueue(&Q,13);
    EnQueue(&Q,26);
    EnQueue(&Q,3);
    
    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=7;k<100;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");
    }
    return 0;
}