顺序栈与链栈的实现

栈是一种经常使用的数据结构，软硬件学习过程中都有它的身影，是一种必须掌握的数据结构，本文将结合代码简单两种栈的实行方式。

栈的定义

栈(Stack)是限定仅在表尾进行插入与删除操作的线性表。于是栈也有两种实现方式，顺序栈和链栈。

代码实现

顺序栈(SqStack)

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

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//顺序栈定义
typedef struct
{
  SElemType *top; //栈顶指针
  SElemType *base; //在栈构造之前和销毁之后为NULL
  int stacksize; //当前已分配大小
}SqStack;

//初始化
Status InitStack(SqStack *S)
{
  S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  if (!S->base) return ERROR;
  S->top = S->base;
  S->stacksize = STACK_INIT_SIZE;
  return OK;
}

//判空
Status StackEmpty(SqStack *S)
{
  if (S->top == S->base)
    return OK;
  return ERROR;
}

//栈满
Status StackFull(SqStack *S)
{
  if (S->top - S->base >= S->stacksize)
    return OK;
  return ERROR;
}

//栈顶
Status GetTop(SqStack *S, SElemType* e)
{
  if (StackEmpty(S))
    return ERROR;
  (*e) = *(S->top - 1);
  return OK;
}

//压栈
Status PushStack(SqStack *S, SElemType e)
{
  if (StackFull(S))
  {
    S->base = (SElemType *)realloc(S->base,
      (S->stacksize + STACKINCREMENT)*sizeof(SElemType));
    if (!S->base) return ERROR;
    S->top = S->base + S->stacksize;
    S->stacksize += STACKINCREMENT;
  }
  *(S->top++) = e;
  return OK;
}

//弹栈
Status PopStack(SqStack *S, SElemType* e)
{
  if (StackEmpty(S)) return ERROR;
  (*e) = *(--S->top);
  return OK;
}

//清空
Status ClearStack(SqStack *S)
{
  S->top = S->base;
  S->stacksize = 0;
  return OK;
}

//销毁
Status DestroyStack(SqStack *S)
{
  free(S->base);
  S->top = NULL;
  S->base = NULL;
  S->stacksize = 0;
  return OK;
}

//长度
int Length(SqStack *S)
{
  return S->top - S->base;
}

//遍历栈
Status Traverse(SqStack *S)
{
  SElemType *p;
  p = S->top - 1;
  while (p >= S->base)
  {
    printf("%d ", *p);
    p--;
  }
  printf("\n");
  return OK;
}

完整代码可参见：GitHub

链栈(LinkStack)

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

#define OK 1
#define ERROR 0

typedef int SElemType;
typedef int Status;

//栈节点定义
typedef struct SNode
{
  SElemType data;
  struct SNode *next;
}SNode, *LinkStack;

//初始化
Status InitStack(LinkStack *S)
{
  *S = (SNode *)malloc(sizeof(SNode));
  if (!(*S)) return ERROR;
  (*S)->next = NULL;
  return OK;
}

//栈空
Status StackEmpty(LinkStack S)
{
  if (!S->next)
    return OK;
  return ERROR;
}

//压栈
Status PushStack(LinkStack S, SElemType e)
{
  SNode *p;
  p = (SNode *)malloc(sizeof(SNode));
  if (!p) return ERROR;
  p->data = e;
  p->next = S->next;
  S->next = p;
  return OK;
}

//弹栈
Status PopStack(LinkStack S, SElemType *e)
{
  SNode *p;
  if (StackEmpty(S))
    return ERROR;
  p = S->next;
  S->next = p->next;
  (*e) = p->data;
  free(p);
  return OK;
}

//遍历栈
Status Traverse(LinkStack S)
{
  SNode *p;
  p = S->next;
  while (p)
  {
    printf("%d ", p->data);
    p=p->next;
  }
  printf("\n");
  return OK;
}

完整代码可参见：GitHub

DONE！