数据结构栈

实验项目名称：栈与队列操作的实现
实验目的与要求：
1.基础知识:掌握数据结构中栈和队列的相关知识;掌握C或VC++语言中程序设计的方法.
2.程序功能:
(1)参考教材相关算法，采用顺序存储存储实现栈的建立与初始化、入栈、出栈、判断栈空等操作;
(2)参考教材相关算法，采用顺序存储或链式存储实现队列的建立与初始化、销毁队列、入队列、出队列、判断队列为空等操作;
●实验性质:验证性(4学时，其中栈2学时，队列2学时)
说明：●说明:每种存储结构下算法实现均包含的主要函数有:主函数、操作界面、建栈(队列)、入栈(入队列)、出栈(出队列) ,应有相关注释。
注意：
(1) 主函数调用子函数的逻辑顺序一主函数调用建栈(建队列)子函数应在调用入/出栈(队列)等子函数之前，这须在主函数中进行条件控制。
(2)2.在选定存储结构后，需要特别关注“栈不存在”和“空栈”、“队列不存在”和“空队列”的语句表达方式以及它们的使用时机和方式。
顺序式栈
源代码：
#include<stdio.h>
#include<malloc.h>
#define OVERFLOW  0
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
typedef int SElemType;
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

Status InitStack(SqStack &S)//构造一个空栈
{
    S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!S.base)return(OVERFLOW);
    S.top=S.base;
    S.stacksize=STACK_INIT_SIZE;
    return OK;
}

Status Push(SqStack &S, SElemType e)//插入元素e为新的栈顶元素
{
    if(S.top - S.base >= S.stacksize)   
    {
    S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
    if(!S.base)return(OVERFLOW);
    S.top=S.base + S.stacksize;
    S.stacksize += STACKINCREMENT;
    }
    *S.top++=e;
    return OK;
}

Status Pop(SqStack &S,SElemType &e)//若栈不为空，则删除栈顶元素，用e返回其值
{
    if(S.top == S.base)
    return ERROR;
    e=*--S.top;
    return OK;
}

Status StackEmpty(SqStack S)//判断是否为空栈
{
    if(S.top==S.base)
    return OK;
    else
    return ERROR;
}

Status PrintStack(SqStack S)//输出栈
{
    int*p;
    p=S.base;
    while(p!=S.top)
    {
        printf("%d ",*p);
        p++;
    }
    return 0;
}

Status GetTop(SqStack S,SElemType &e)//输出栈顶元素
{
    if(S.top == S.base)
    return ERROR;
    e = *(S.top-1);
    return OK;
}

Status OperateMenu(int num)
{
    printf("------****操作菜单****------\n\n");
    printf("------    0 退出系统\n");
    printf("------    1 插入一个元素\n");
    printf("------    2 删除栈顶元素\n");
    printf("------    3 判断是否为空栈\n");
    printf("------    4 输出栈中全部元素\n");
    printf("------    5 返回栈顶元素\n");
    printf("------    请选择你所需要的操作\n");
    scanf("%d",&num);
    return num;
}

int main()
{
    SqStack S;
    SElemType e;
    int num=-1;
    if(InitStack(S))
    {printf("------  顺序栈创建成功\n");}
    while(num!=0)
    {
        {
       num=OperateMenu(num);
    }
    switch(num)
    {
        case 1:    
            printf("输入入栈元素e:");
            scanf("%d",&e);
            if(!Push(S,e))
            printf("输入不合法");
            else
            printf("已经将%d存入顺序栈\n", e);
            printf("顺序栈为\n");
            PrintStack(S);//输出栈
            printf("\n");break;
        case 2:
            if(StackEmpty(S))
            printf("栈为空栈\n");
            else
            {Pop(S,e);
            printf("栈顶元素%d已删除\n",e);
            printf("\n");}
            break;
        case 3:
            if(StackEmpty(S))
            printf("栈为空栈\n");
            else
            printf("不是空栈\n");break;
        case 4:
            if(StackEmpty(S))
            printf("栈为空栈\n");
            else
            {
printf("顺序栈为\n");
PrintStack(S);//输出栈
            printf("\n");}break;
        case 5:
        if(StackEmpty(S))
        printf("栈为空栈\n");
        else
        {GetTop(S,e);
        printf("栈顶元素为：%d",e);
        printf("\n");}
        break;
      }
     }
    }