栈和队列是两种重要的现行结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。

栈

栈(stack) 是限定尽在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端称为栈顶（top）, 表头端称为栈底（bottom）。不含元素的空表称为空栈。

栈的表示和实现

顺序栈

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元一次存放自栈底到栈顶的数据元素同时附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法是以top = 0表示空栈。

结构设计

typedef struct {
    SElemType data[STACK_INIT_SIZE];
    int top;
}SqStack;

顺序栈的创建

Status InitStack(SqStack *S) {
    S->top = -1;
    return OK;
}

获取栈顶元素

Status GetTop(SqStack S, SElemType *e) {
    if (S.top == -1) {
        return ERROR;
    }
    
    *e = S.data[S.top];
    return OK;
}

顺序栈的压栈

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

顺序栈的出栈

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

顺序栈的清空

Status ClearStack(SqStack *S) {
    S->top = -1;
    return OK;
}

顺序栈的为空判断

Status StackEmpty(SqStack S) {
    return S.top == -1;
}

顺序栈的遍历

Status StackTraverse(SqStack S) {
    int i = 0;
    while (i <= S.top) {
        printf("%d", S.data[i++]);
    }
    printf("\n");
    return OK;
}

链栈

结构设计

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct {
    LinkStackPtr top;
    int count;
}LinkStack;

顺序栈的创建

Status InitStack(LinkStack *S) {
    S->top = (LinkStackPtr)malloc(sizeof(StackNode));
    if (S->top == NULL) {
        return ERROR;
    }
    
    S->top = NULL;
    S->count = 0;
    return OK;
}

获取栈顶元素

Status GetTop(LinkStack S, SElemType *e) {
    if (S.count == 0) {
        return ERROR;
    }
    
    *e = S.top->data;
    return OK;
}

顺序栈的压栈

Status Push(LinkStack *S, SElemType e) {
    LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
    if (!temp) {
        return ERROR;
    }
    
    temp->data = e;
    temp->next = S->top;
    S->top = temp;
    S->count++;
    return OK;
}

顺序栈的出栈

Status Pop(LinkStack *S, SElemType *e) {
    if (S->count == 0) {
        return ERROR;
    }
    
    *e = S->top->data;
    LinkStackPtr p = S->top;
    S->top = S->top->next;
    free(p);
    S->count--;
    return OK;
}

顺序栈的清空

Status ClearStack(LinkStack *S) {
    LinkStackPtr p, q;
    p = S->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    S->count = 0;
    return OK;
}

顺序栈的为空判断

Status StackEmpty(LinkStack S) {
    return S.count == 0;
}

顺序栈的遍历

Status StackTraverse(LinkStack S) {
    LinkStackPtr p = S.top;
    while (p) {
        printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

---

Demo：https://github.com/ShoukaiWang/DataStructuresAndAlgorithms