顺序栈

/*
  Name: 顺序栈的实现
  Copyright:
  Author:
  Date:
  Description:
*/

#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED

#include "ds.h" //for Status,OK ...

#ifndef ElemType
#define ElemType int /* 数据元素类型默认为 int */
#define ELEMTYPE_TAG
#endif

#define SElemType ElemType

///////////////////////////////////////////////////////////
//顺序栈的存储结构定义
#define STACK_INIT_SIZE 100 /* 存储空间初始分配容量 */
#define STACKINCREMENT 10 /* 存储空间分配的增量 */
typedef struct {
    ElemType *base; //在构造栈之前和销毁栈之后，base为NULL
    ElemType *top; //栈顶指针
    int stacksize; //当前已分配的存储空间(元素个数)
} SqStack;

///////////////////////////////////////////////////////////
//顺序栈的基本操作声明

//构造一个空栈S
Status InitStack(SqStack &S);
//销毁栈S
Status DestroyStack(SqStack &S);
//将栈S清空
Status ClearStack(SqStack &S);
//若栈S为空返回TRUE，否则FALSE
Status StackEmpty(SqStack S);
//返回栈S中的元素个数
int    StackLength(SqStack S);
//用e返回栈顶元素
//    前提：栈S存在且不空
Status GetTop(SqStack S, ElemType &e);
//元素e入栈S
Status Push(SqStack &S, ElemType e);
//S出栈用e返回出栈元素
//    前提：栈S存在且不空
Status Pop(SqStack &S, ElemType &e);

///////////////////////////////////////////////////////////
//顺序栈的基本操作的实现

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

//销毁栈S
Status DestroyStack(SqStack &S)
{
    // TODO (#1#):销毁栈S，相当于清空栈
    return ERROR;
    //-------------------------------------
}

//将栈S清空
Status ClearStack(SqStack &S)
{    S.top=S.base;
    // TODO (#1#): 将栈S清空，释放所有结点
    return OK;
    //-------------------------------------
}

//若栈S为空返回TRUE，否则FALSE
Status StackEmpty(SqStack S)
{   if(S.base==S.top) return true;
       else return false;
    // TODO (#1#): 若栈S为空返回TRUE，否则FALSE
}

//返回栈S中的元素个数
int    StackLength(SqStack S)
{    int i=0;
while(S.top!=S.base) {
     S.top--;
     i++;
}
    return i;
    // TODO (#1#): 返回栈S中的元素个数
    //-------------------------------------
}

//用e返回栈顶元素
//    前提：栈S存在且不空
Status GetTop(SqStack S, ElemType &e)
{    if(!S.base&&S.base==S.top) return ERROR;
        else e=*(S.top-1);
        return OK;
    // TODO (#1#):若栈S不空，则用e返回栈顶元素
    //-------------------------------------
}

//元素e入栈S
Status Push(SqStack &S, ElemType e)
{  if(S.top-S.base>=S.stacksize)
    // S.base=(SElemType) realloc(S.base,(STACKINCREMENT+S.stacksize)*sizeof(SElemType));默认不满
    return ERROR;
     *(S.top++)=e;
     return OK;
   // TODO (#1#): 插入元素e作为新的栈顶

    //-------------------------------------
}

//S出栈用e返回出栈元素
//    前提：栈S存在且不空
Status Pop(SqStack &S, ElemType &e)
{   if(S.base==S.top)    return ERROR;
     e=*(S.top-1);
     S.top--;
     return OK;
    // TODO (#1#):若栈S不空，则删除栈顶元素用e返回
    //-------------------------------------
}


#ifdef ELEMTYPE_TAG
#undef ElemType
#undef ELEMTYPE_TAG
#endif

#endif