栈

栈的基本概念

1 栈的定义

栈（Stack）：只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但是限定这种线性表只能在某一端进行插入和删除操作。
栈顶（Top）：线性表允许进行插入和删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。
栈的一个明显的操作特性可以概括为后进先出（Last In First Out,LIFO），故又称为后进先出的线性表。

2 栈的基本操作

InistStack(&S):初始化一个空栈S。
StackEmpty(S):判断一个栈是否为空，若栈S为空返回true，否则返回false。
Push(&S,x):进栈，若栈S未满，将x加入使之称为新栈顶。
Pop(&S,&x):出栈，若栈S非空，弹出栈顶元素，并用x返回。
GetTop(S,&x):读栈顶元素，若栈S非空，用x返回栈顶元素。
ClearStack(&S):销毁栈，并释放栈S占用的存储空间。

3 栈的顺序存储结构

（1）动态顺序栈
采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。
用 bottom 表示栈底指针，栈底固定不变的;栈顶则随着进栈和退栈操作而变化。用 top(称为栈顶指针)指示当前栈顶位置。
用 top=bottom 作为栈空的标记，每次 top 指向栈顶数组中的下一个存储位置。
用 top-bottom = stacksize-1 表示栈满
结点进栈：首先将数据元素保存到栈顶（top指针所指的当前位置），然后执行top加1，使top指向栈顶的下一个存储位置。
结点出栈:首先执行 top 减 1，使 top 指向栈顶元素的存储位置，然后将栈顶元素取出。
基本操作的实现

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

#define STACK_SIZE 100 /* 栈初始向量大小 */
#define STACKINCREMENT 10 /* 空间分配增量 */
#define ERROR 0
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct sqstack {
    ElemType *bottom; /* 栈不存在时值为 NULL */
    ElemType *top; /* 栈顶指针 */
    int stacksize; /*当前已分空间，以元素为单位 */
} SqStack;

Status Init_Stack(SqStack *S) {
    S->bottom = (ElemType *) malloc(STACK_SIZE * sizeof(ElemType));
    if (!S->bottom) {
        return ERROR;
    }
    S->top = S->bottom; /*栈空时栈顶和栈底指针相同 */
    S->stacksize = STACK_SIZE;
    return OK;
}

Status push(SqStack *S, ElemType e) {
    if (S->top - S->bottom >= S->stacksize - 1) {
        /*栈满，追加存储空间*/
        S->bottom = (ElemType *) realloc(S->bottom, (STACKINCREMENT + STACK_SIZE) * sizeof(ElemType));
        if (!S->bottom) {
            return ERROR;
        }
        S->top = S->bottom + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *S->top = e;
    S->top++;/*栈顶指针加 1，e 成为新的栈顶 */
    return OK;
}

Status pop(SqStack *S, ElemType *e) /*弹出栈顶元素*/
{
    if (S->top == S->bottom) {
        return ERROR;
    }
    S->top--;
    *e = *S->top;
    return OK;
}

int main() {
    SqStack S;
    Init_Stack(&S);
    push(&S, 1);
    int e;
    pop(&S, &e);
}

（2）静态顺序栈

栈顶指针：S->top，初始时设置为-1；栈顶元素：S->data[S->top]。
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。
栈空条件：S->top == -1
栈满条件：S->top == MaxSize - 1
栈长：S->top + 1

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

#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int Status;
#define MAXSIZE 100
typedef struct {
    ElemType data[MAXSIZE];
    int top;
} SqStack;

void InitStack(SqStack *S) {
    S->top = -1;
}

Status StackEmpty(SqStack *S) {
    if (S->top == -1) {
        return OK;
    } else {
        return ERROR;
    }
}

Status Push(SqStack *S, ElemType x) {
    if (S->top == MAXSIZE - 1) {
        return ERROR;
    }
    S->data[++S->top] = x;
    return OK;
}

Status Pop(SqStack *S, ElemType *x) {
    if (S->top == -1) {
        return ERROR;
    }
    *x = S->data[S->top--];
    return OK;
}

Status GetTop(SqStack *S, ElemType *x) {
    if (S->top == -1) {
        return ERROR;
    }
    *x = S->data[S->top];
    return OK;
}

int main() {
    SqStack S;
    InitStack(&S);
    ElemType e = 1;
    Push(&S, e);
    ElemType a;
    Pop(&S, &a);
    printf("%d", a);
}

4 栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高效率，且不存在栈满上溢的情况。通常采用单链表来实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead指向栈顶元素。
栈的链式存储类型可描述为

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

#define ERROR 0
#define OK 1
typedef int ElemType;
typedef int Status;
typedef struct Stack_Node {
    ElemType data;
    struct Stack_Node *next;
} Stack_Node;

Stack_Node *Init_Link_Stack(void) {
    Stack_Node *top;
    top = (Stack_Node *) malloc(sizeof(Stack_Node));
    top->next = NULL;
    return (top);
}

Status push(Stack_Node *top, ElemType e) {
    Stack_Node *p;
    p = (Stack_Node *) malloc(sizeof(Stack_Node));
    if (!p) {
        /* 申请新结点失败，返回错误标志 */
        return ERROR;
    }

    p->data = e;
    p->next = top->next;
    top->next = p; /* 钩链 */
    return OK;
}

Status pop(Stack_Node *top, ElemType *e) /* 将栈顶元素出栈 */
{
    Stack_Node *p;
    if (top->next == NULL) {
        /*栈空，返回错误标志 */
        return ERROR;
    }
    p = top->next;
    *e = p->data; /*取栈顶元素*/
    top->next = p->next; /*修改栈顶指针*/
    free(p);
    return OK;
}

int main() {
    Stack_Node *S;
    S = Init_Link_Stack();
    ElemType e = 4;
    push(S, e);
    ElemType a;
    pop(S, &a);
    printf("%d", a);
}

5 共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

两个栈的栈顶指针都指向栈顶元素，top0 = -1时0号栈为空，top1 = MaxSize时1号栈为空；仅当两个栈顶指针相邻（top1 - top0 = 1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈时刚好相反。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存储数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。