/*
  栈的循序存储结构
  声明一段连续的地址
  地址的 top - base 就是当前栈中数据的个数
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define STACK_INIT_SIZE 20
#define STACKINCREAMENT 10

typedef char DataType;

typedef struct {
  DataType *base;
  DataType *top;
  int stackSize;
}strStack;

void initStack(strStack *stack){
  stack->base = (DataType *)malloc(STACK_INIT_SIZE * sizeof(DataType));
  if(!stack->base){
    exit(0);
  }

  stack->top = stack->base;
  stack->stackSize = STACK_INIT_SIZE;
}

//
void printStrack(strStack *stack){
  DataType *newBase;
  newBase = stack->base;

  while(newBase != stack->top){
    printf("%c ->", *newBase);
    newBase++;
  }
  printf("\n");
}

// 压栈
strStack *Push(strStack *stack, DataType data){
  if(stack->top - stack->base >= STACK_INIT_SIZE){
    int baseLength = stack->top - stack->base;

    stack->base = (DataType *)realloc(stack->base, (stack->stackSize + STACKINCREAMENT) * sizeof(DataType));
    if(!stack->base){
      exit(0);
    }
    stack->stackSize = stack->stackSize + STACKINCREAMENT;
    stack->top = stack->base + baseLength;
  }

  *(stack->top) = data; //当前Top地址指向的数据
  stack->top++; // 当前的Top执行的地址 + 1

  return stack;
}

// 出栈
strStack *Pop(strStack *stack, DataType *data){
  int popStart, incrRate;
  if(stack->top == stack->base){
    return stack;
  }

  // 开始需要额外增加
  if (stack->top - stack->base <= STACK_INIT_SIZE){
    popStart = 0;
  }else{
    popStart = (stack->top - stack->base - STACK_INIT_SIZE) / STACKINCREAMENT + 1;
  }

  *data = *--(stack->top);

  // 结束需要额外增加
  if (stack->top - stack->base <= STACK_INIT_SIZE){
    incrRate = 0;
  }else{
    incrRate = (stack->top - stack->base - STACK_INIT_SIZE) / STACKINCREAMENT + 1;
  }

  // 重新去计算栈的大小，这样会节约空间吧，不会因为一个栈声明的空间很大，但是存储的数据很小
  if(popStart != incrRate){
    int baseLength = stack->top - stack->base;

    stack->base = (DataType *)realloc(stack->base, (STACK_INIT_SIZE + STACKINCREAMENT * incrRate) * sizeof(DataType));
    if(!stack->base){
      exit(0);
    }
    stack->stackSize = STACK_INIT_SIZE + STACKINCREAMENT * incrRate;
    stack->top = stack->base + baseLength;
  }

  printStrack(stack);
  return stack;
}

int stackLength(strStack *stack){
  return (stack->top - stack->base);
}

// 初始化栈
void reintStack(strStack *stack){
  stack->top = stack->base;
  stack->stackSize = STACK_INIT_SIZE;
}

// 键盘输入
strStack *screenPop(strStack *stack){
  char data;

  printf("输入字符,回车结束: ");
  while(1){
    scanf("%c", &data);

    if(data == '\n'){
      fflush(stdin);
      return stack;
    }
    printf("正在Push--%c\n", data);
    stack = Push(stack, data);
  }
  fflush(stdin);

  return stack;
}

int main(int argc, char const *argv[])
{
  DataType c;
  strStack *stack;
  char oprator, *popData;

  stack = (strStack *)malloc(sizeof(strStack));
  initStack(stack);

  printf("A: 入栈\n");
  printf("B: 出栈\n");
  printf("C: 计算栈大小\n");
  printf("D: 清空栈\n");
  printf("E: 打印栈数据\n");
  printf("Q: 退出\n");
  while(1){
    printf("-----------------输入操作: ");
    scanf("%c", &oprator);
    getchar();

    switch(oprator){
      case 'A':
        stack = screenPop(stack);
        break;
      case 'B':
        stack = Pop(stack, popData);
        break;
      case 'C':
        printf("当前栈容量是: %d\n", stack->stackSize);
        printf("当前栈的大小是: %d\n", stackLength(stack));
        break;
      case 'D':
        reintStack(stack);
        break;
      case 'E':
        printStrack(stack);
        break;
      case 'Q': exit(0);
    }
    fflush(stdin);
  }

  printf("\n");
  return 0;
}