栈 Stack

本文章内容部分来自严蔚敏《数据结构》，大量代码为作者手写，如果改进，请评论留言

概述

栈，本质来说，就是只有一端可以添加和删除结点的线性表，而我们把这一端称之为栈顶。既然是一种线性表，那么也可以有顺序结构和存储结构两种物理实现。而栈作为一种数据结构，提供的“服务"向上是相同的，因此要尽量隐藏实现的不同。

基本操作

void initStack(Stack &s);
void clearStack(Stack &s);
void destroyStack(Stack &s);
Boolean stackEmpty(Stack s);
void stackLength(Stack s);
void push(Stack &s, int e);
void pop(Stack &s, int *e);
void getTop(Stack s, int e);
void travelStack(Stack s,  void (*visit);

注意
1.实例中数据域都是用int表示的
2.实例都是用C语言写的，但是C语言没有Boolean类型，因此需要进行宏定义，如下

#define Boolean int
#define TRUE 1
#define FALSE 0

3.最后一个遍历方法传入的是方法指针，由于markdown高亮的原因，这里应该是void (*vist)();

顺序结构

定义数据类型

#define INIT_STACK_SIZE 100
#define STACK_INCREMENT 10
typedef struct {
  int* top;
  int* base;
  int stackSize;
} SqStack;

1.top指栈的栈顶，负责删除和插入结点，同时配合base计算出栈的元素个数，注意这里实现的top指向的是下一个可放元素的位置，意味着top本身不放入任何元素，同时当栈满时，top应该再base动态分配的内存空间外了。
2.base是栈底指针，指向栈的栈底，配合top计算出栈的长度，同时负责整个栈的内存分配。
3.stackSize值目前栈最多能够放下多少结点。

基本操作

void initStack(SqStack *s) {
  s->base = (int*)malloc(sizeof(int) * INIT_STACK_SIZE);
  s->top = s->base;
  s->stackSize = INIT_STACK_SIZE;
}
void clearStack(SqStack *s) {
  destroyStack(s);
  initStack(s);
}
void destroyStack(SqStack *s) {
  free(s->base);
  free(s);
}
Boolean stackEmpty(Stack s) {
  if (s.base = s.top) {
    return TRUE;
  }
  return FALSE;
}
void push(SqStack *s, int e) {
  if (s->top - s->length >= s->stackSize) {
    s->base = (int*)realloc(s->base, (s->stackSize + STACK_INCREMENT)*sizeof(int));
    s->top = s->base + s->stackSize;
    s->stackSize += STACK_INCREMENT;
  }
  *s->top++ = e;
}
void pop(SqStack *s, int *e) {
    if(stackEmpty(*s) == TRUE) {
      exit(-2);
    }
    *e = *--s->top;
}
void getTop(SqStack s, int *e) {
  if(stackEmpty(*s) == TRUE) {
      exit(-2);
    }
    *e = *s.top;
}

void travelStack(Stack s, void (*visit)()) {
  int* cur = s.top;
  while (cur != s.base) {
    visit(*cur++);
  }
}

注意
1.在c语言中，如果指针类型为同一类型，那么相减可以表示为长度，代码中就有s->top - s->base表示长度的例子。
2.在pop和getTop的时候一定要判空，这里是如果为空直接以-2为返回值强制停止。

链式结构

如果结构要定义为链式结构，那么他必然要手动声明结点，因为在顺寻表中，无论是数据的值还是数据的关系，都是由数据表来实现的（值和下标）。但是，链表必须声明结点，以表示结点和结点之间的关系。
另外这里实现的链表，是无头节点的，而只能在第一个节点进行插入和删除的链表。

定义数据类型

typedef struct Node {
    int data;
   struct Node* next;
} LNode;
typedef struct LinkStack {
  LNode* top;
  int length;
}

1.top表示栈的栈顶，与顺寻栈的实现不同，这里的top指已经插入元素的栈顶，也就是top表示的是一个确切有意义的结点。
2.length表示的栈目前的元素个数，也就是栈的长度。

基本操作

void initStack(LinkStack *s)
{
    s->top = NULL;
    s->length = 0;
}

void push(LinkStack *s, int e)
{
    LNode* node = (LNode*)malloc(sizeof(LNode));
    node->data = e;
    node->next = s->top;
    s->top = node;
    s->length++;
}

void pop(LinkStack *s, int *e)
{
    LNode* now = s->top;
    if (now == NULL) {
        exit(-1);
    }
    *e = now->data;
    s->top = s->top->next;
    free(now);
}
void destroyStack(LinkStack *s) {
    clearStack(s);
    free(s);
}

void clearStack(LinkStack *s) {
    LNode *temp;
    while (s->top != NULL) {
        temp = s->top;
        s->top = s->top->next;
        free(temp);
    }
    s->length = 0;
}

void travelStack(LinkStack s, void (*visit)()) {
    LNode *cur = s.top;
    while(cur != NULL) {
        visit(cur->data);
        cur = cur->next;
    }
}

注意
1.部分方法因为雷同就略了
2.栈底没有元素表示，而是用NULL表示，总而言之，就是一个链表的尾结点。