栈

栈的本质是一个线性表，线性表中存在两种存储形式，分为栈的线性存储结构和链式存储结构。

线性存储结构

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

typedef int ElementType;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct {
  ElementType *base;
  ElementType *top;
  int stackSize;
} sqStack;


void initStack(sqStack *s)
{
  s->base = (ElementType *)malloc(STACK_INIT_SIZE * sizeof(ElementType));
  if (!s->base)
  {
    exit(0);
  }

  s->top = s->base; // 最开始，栈顶指向栈底
  s->stackSize = STACK_INIT_SIZE; // 栈的操作
}

// 入栈
void Push(sqStack *s, ElementType e)
{
  // 如果栈満，添加空间
  if (s->top - s->base >= s->stackSize) {
    s->base = (ElementType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElementType));
    if (!s->base) {
      exit(0);
    }

    s->top = s->base + s->stackSize; // 设置栈顶
    s->stackSize = s->stackSize + STACKINCREMENT; // 设置栈的最大容量
  }

  *(s->top) = e;
  s->top++;
}

void Pop(sqStack *s, ElementType *e)
{
  // 空栈
  if (s->top == s->base) return;
  // 栈容量 -1
  *e = *--(s->top);
}

// 清空栈，就是将栈中的元素全部作废，但是栈本身的物理空间并不发生改变
void ClearStack(sqStack *s)
{
  s->top = s->base;
}

void DestoryStack(sqStack *s)
{
  int i, len;
  len = s->stackSize;
  for (i = 0; i < len; i++)
  {
    free(s->base);
    s->base ++;
  }

  s->base = s->top = NULL;
  s->stackSize = 0;
}

// 计算栈的当前容量，也就是计算栈中元素的个数
long StackLen(sqStack s)
{
  return(s.top - s.base);
}

链式存储结构