/*
 * Include.h
 *
 * Created on: 2016.11.23
 *   Author: Jack Cui
 */

#ifndef MYSTACK_H_
#define MYSTACK_H_

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h> 
/*棧(Stack)是限定僅在表尾進(jìn)行插入或刪除操作的線性表
**棧頂(top)和棧底(bottom)相等，代表為空棧
**
*/

//SElemType是某個(gè)確定的、將由用戶自行定義的、含某個(gè)關(guān)系運(yùn)算的數(shù)據(jù)對(duì)象
typedef int SElemType;

//函數(shù)結(jié)果狀態(tài)代碼
#define TRUE    1  
#define FALSE    0
#define OK     1
#define ERROR    0
#define INFEASIBLE -1   //不可行
#define MY_OVERFLOW -2   //溢出

/**********棧的順序存儲(chǔ)表示**********/
#define STACK_INIT_SIZE 100   //存儲(chǔ)空間初始分配量
#define STACKINCREMENT 10   //存儲(chǔ)空間分配增量

typedef struct{
  SElemType *base;  //在棧構(gòu)造之前和銷毀之后，base的值為NULL
  SElemType *top;   //棧頂指針
  int stacksize;   //當(dāng)前已分配
}SqStack;
/**********基本操作的函數(shù)原型說(shuō)明**********/
//構(gòu)造一個(gè)空棧S
Status InitStack(SqStack &S);      
//銷毀棧S，S不再存在
Status DestroyStack(SqStack &S);
//把S置為空棧
Status ClearStack(SqStack &S);
//若棧S為空棧，則返回TURE，否則返回FALSE
Status StackEmpty(SqStack S); 
//返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度
int StackLength(SqStack S);
//若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR
Status GetTop(SqStack S, SElemType &e); 
//插入元素e為新的棧頂元素
Status Push(SqStack &S, SElemType e);
//若棧不空，則刪除S的棧頂元素，用e新棧頂?shù)闹?，并返回OK;否則返回ERROR;
Status Pop(SqStack &S, SElemType &e);
//從棧底到棧頂依次對(duì)棧中每個(gè)元素調(diào)用函數(shù)visit();一旦visit()失敗，則操作失敗
Status StackTraverse(SqStack S, Status(* visit)(SElemType));
//visit()函數(shù)
Status visit(SElemType e);
//測(cè)試函數(shù)
Status TestMyStack();

#endif MYSTACK_H_

#include "MyStack.h"

Status InitStack(SqStack &S){
  //構(gòu)造一個(gè)空棧S
  S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
  if(!S.base){    //存儲(chǔ)分配失敗
    printf("InitStack: malloc err\n");
    exit(MY_OVERFLOW);
  }
  S.top = S.base;
  S.stacksize = STACK_INIT_SIZE;
  return OK;
}//InitStack

Status DestroyStack(SqStack &S){
  if(!S.base){
    printf("DestroyStack: Stack does not exist\n");
    exit(MY_OVERFLOW);
  }
//在調(diào)用malloc的時(shí)候，系統(tǒng)會(huì)記住你申請(qǐng)的這塊連續(xù)空間的起始地址以及這塊空間的大小，
//釋放free的時(shí)候，只要把這個(gè)起始地址告訴系統(tǒng)，系統(tǒng)自然就知道要釋放多大的空間。
  free(S.base);    
  S.top = NULL;
  S.base = NULL;
  S.stacksize = 0;
  return OK;
}//DestroyStack

Status ClearStack(SqStack &S){
  if(!S.base){
    printf("ClearStack: Stack does not exist\n");
    exit(MY_OVERFLOW);
  }
  S.top = S.base; 
  return OK; 
}//ClearStack

Status StackEmpty(SqStack S){
  if(S.top == S.base){
    return TRUE;
  }
  else{
    return FALSE;
  }
}//StackEmpty

int StackLength(SqStack S){
  return S.top - S.base;
}//StackLength

Status GetTop(SqStack S, SElemType &e){
  ////若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR
  if(S.top == S.base){
    printf("GetTop: Stack is empty\n");
    return ERROR;
  }
  e = *(S.top - 1);
  return OK;
}//GetTop

Status Push(SqStack &S, SElemType e){
  //插入元素e為新的棧頂元素
  if(S.top - S.base >= S.stacksize){ //棧滿，追加存儲(chǔ)空間
    S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
    if(!S.base){
      printf("Push: realloc error\n");
    }
    S.top = S.base + S.stacksize;
    S.stacksize += STACKINCREMENT;
  }
  *S.top++ = e;    //*S.top = e; S.top++;
  return OK;
}//Push

Status Pop(SqStack &S, SElemType &e){
  //若棧不空，則刪除S的棧頂元素，用e返回新棧頂?shù)闹?，并返回OK，否則返回ERROR;
  if(S.top == S.base){
    printf("Pop: Stack is empty\n");
    return ERROR;
  }
  e = *--S.top;    //S.top--; e = *S.top;
  return OK;
}//Pop

Status StackTraverse(SqStack S, Status(* visit)(SElemType)){
  while(S.top > S.base){
    visit(*S.base++); 
  } 
  printf("\n");
  return OK; 
}//StackTraverse

Status visit(SElemType e){
  printf("%d ",e) ;
  return OK;
}//visit

Status TestMyStack(){
  SElemType j; 
  SqStack s; 
  SElemType e; 

  if(InitStack(s) == OK) 
  for(j = 1; j <= 12; j++) 
  { 
    Push(s,j); 
  } 
  printf("棧中的元素依次為："); 
  StackTraverse(s,visit); 
  Pop(s, e); 
  printf("彈出的棧頂元素 e=%d\n", e); 
  printf("棧空否：%d(1：是 0：否)\n", StackEmpty(s)); 
  GetTop(s, e); 
  printf("棧頂元素 e=%d,棧的長(zhǎng)度為%d\n", e, StackLength(s)); 
  ClearStack(s); 
  printf("清棧后，棧是否為空：%d(1：空 0：否)\n",StackEmpty(s)); 
  DestroyStack(s); 
  printf("銷毀棧后，s.top = %u s.base= %u s.stacksize=%d\n",s.top,s.base,s.stacksize); 
  return 0; 
}//TestMyStack

//主函數(shù)
int main(){
  TestMyStack();
  system("pause");
  return 0;
}