栈

栈（stack）是一种限定在表的一端进行插入或删除操作的线性表。可以被操作的一端被称为栈顶（top），相对地，把另一端称为栈底（bootom）。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈，退栈或弹栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈限定只能在栈顶进行插入或删除操作，因此符合一个先进后出（LIFO：last in first out）的特性。

ADT 栈（stack）
Data
    同线性表，并规定表的一端称为底，另一端称为顶。
Operation
    init_stack(*S)：初始化栈。构造一个空的栈S。
    clear_stack(*S)：清空栈。
    stack_is_empty(S)：判空操作。如果栈S为空，则返回true，否则返回false。
    peek_top(S)： “窥视”栈顶数据，返回栈顶的数据项但不移除，栈不被修改。
    pop(*S, *e)：弹栈。删除栈S中栈顶元素，并用e返回其值。
    push(*S,e)：压栈。插入元素e为新的栈顶元素。
    stack_size(S)：返回回栈S的元素个数。
endADT

因为栈的事实就是线性表，所以存储方式也分为顺序和链式。

顺序存储栈实现

构建

#define OK      true
#define ERROR   false
typedef bool STATUS;
#define MAX_SIZE    100
typedef int Elem_Type;

typedef struct SQ_Stack
{
    Elem_Type data[MAX_SIZE];
    int top;
} SQ_Stack;
SQ_Stack stack;

初始化和清空

STATUS init_stack(SQ_Stack *s)
{
    s->top = -1;
    return OK;
}

STATUS clear_stack(SQ_Stack *s)
{
    for(int i = 0; i < MAX_SIZE; i++)
    {
        s->data[i] = 0;
    }
    s->top = -1;
    return OK;
}

判空和获取元素个数

bool stack_is_empty(SQ_Stack s)
{
    if(s.top == -1)
        return true;
    return false;
}

int stack_size(SQ_Stack s)
{
    return s.top + 1;
}

查看top元素

STATUS peek_top(SQ_Stack s, Elem_Type *e)
{
    if(s.top <= -1)
        return ERROR;
    *e = s.data[s.top];
    return OK;
}

pop

STATUS pop(SQ_Stack *s, Elem_Type *e)
{
    if(s->top <= -1)
        return ERROR;

    *e = s->data[s->top];
    (s->top)--;
    return OK;
}

push

STATUS push(SQ_Stack *s, Elem_Type e)
{
    if(s->top >= (MAX_SIZE - 1))
        return ERROR;

    (s->top)++;
    s->data[s->top] = e;
    return OK;
}

链式存储栈实现

构建

#define OK      true
#define ERROR   false
typedef bool STATUS;
typedef int Elem_Type;

typedef struct Node
{
    Elem_Type data;
    struct Node *prior;
}Node;

typedef struct CH_Stack
{
    Node *top;
    int size;
} CH_Stack;
CH_Stack stack;

初始化和清空

STATUS init_stack(CH_Stack *s)
{
    s->top = NULL;
    s->size = 0;
    return OK;
}

STATUS clear_stack(CH_Stack *s)
{
    Node *temp = NULL;
    while(s->top != NULL)
    {
        temp = s->top;
        s->top = s->top->prior;
        free(s->top);
    }
    s->size = 0;
    return OK;
}

判空和获取元素个数

bool stack_is_empty(CH_Stack s)
{
    if(s.size == 0)
        return true;
    return false;
}

int stack_size(CH_Stack s)
{
    return s.size;
}

查看top元素

STATUS peek_top(CH_Stack s, Elem_Type *e)
{
    if(s.size <= 0)
        return ERROR;
    *e = s.top->data;
    return OK;
}

pop

STATUS pop(CH_Stack *s, Elem_Type *e)
{
    if(s->size <= 0)
        return ERROR;

    Node *temp = s->top;
    *e = temp->data;
    s->top = s->top->prior;
    (s->size)--;
    free(temp);
    return OK;
}

push

STATUS push(CH_Stack *s, Elem_Type e)
{
    Node *temp = NULL;
    if(!(temp = (Node *)malloc(sizeof(Node))))
        return ERROR;

    temp->data = e;
    temp->prior = s->top;
    s->top = temp;
    (s->size)++;
    return OK;
}