一、什么是堆栈

堆栈（Stack）具有一定操作约束的线性表，它只能在一端（栈顶，Top）做插入数据（入栈，Push）、删除数据（出栈，Pop）。它具有 后入先出（Last In First Out，简称 LIFO）的特点。

堆栈的抽象数据类型描述：

类型名称：堆栈（Stack）
数据对象集：一个有 0 个或多个元素的有穷线性表
操作集：长度为 MaxSize 的堆栈 S ∈ Stack，堆栈元素 item ∈ ElementType

Stack CreateStack(int MaxSize);         // 生成空堆栈，其最大长度为MaxSize
int IsFull(Stack S,int MaxSize);        // 判断堆栈S是否已满
void Push(Stack S,ElementType item);    // 将元素item压入堆栈
int isEmpty(Stack S);                   // 判断堆栈S是否为空
ElementType Pop(Stack S);               // 删除并返回栈顶元素

二、堆栈的顺序存储实现

栈的顺序存储结构通常由一个 一维数组 和一个记录栈顶元素位置的变量组成。

#define MaxSize         // 存储数据元素的最大个数
struct SNode
{
    ElementType Data[MaxSize];
    int top;
};

typedef struct SNode *Stack;

【1】、入栈（Push）

void Push(Stack PtrS, ElementType item)
{
    if(PtrS->Top == MaxSize-1)
    {
        printf("堆栈已经满了\n");
        return;
    }
    else
    {
        PtrS->Data[++(PtrS->Top)] = item;
        return;
    }
}

【2】、出栈（Pop）

ElementType Pop(Stack PtrS)
{
    if(PtrS->Top == -1)
    {
        printf("堆栈已经空了\n");
        return ERROR;
    }
    else
    {
        return (PtrS->Data[(PtrS->Top)--]);
    }
}

如果我们想用一个数组实现两个堆栈，要求最大地利用数组空间，使用只有有空间入栈操作就可以成功。那我们应该如何实现呢？我们可以使这两个栈分别从数组的 两头开始向中间生长；当两个栈的 栈顶指针相遇 时，表示两个栈都满了。

#define MaxSize                 // 存储数据元素的最大个数
struct DStack
{
    ElenmentType Data[MaxSize];
    int Top1;                   // 堆栈1的栈顶指针
    int Top2;                   // 堆栈2的栈顶指针
}S;

S.Top1 = -1;
S.Top2 = MaxSize;

void Push(struct DStack *PtrS,ElementType item,int Tag)
{
    // Tag作为区分两个堆栈的标志，取值1和2

    if(PtrS->Top2 - PtrS->Top1 == 1)                // 堆栈已满
    {
        printf("堆栈已满\n");
        return;
    }

    if(Tag == 1)                                    // 对第一个堆栈操作
    {
        PtrS->Data[++(PtrS->Top1)] = item;
    }
    else                                            // 对第二个堆栈操作
    {
        PtrS->Data[--(PtrS->Top2)] = item;
    }
}

ElementType Pop(struct DStack *PtrS,int Tag)
{
    // Tag作为区分两个堆栈的标志，取值1和2
    if(Tag == 1)                                    // 对第一个堆栈操作
    {
        if(PtrS->Top == -1)
        {
            printf("堆栈1已空\n");                  // 堆栈1已空
            return NULL;
        }
        else
        {
            return PtrS->Data[(PtrS->Top1)--];
        }
    }
    else                                            // 对第二个堆栈操作
    {
        if(PtrS->Top2 == MaxSize)                   // 堆栈2已空
        {
            printf("堆栈2已空\n");
            return NULL;
        }
        else
        {
            return PtrS->Data[(PtrS->Top2)++];
        }
    }
}

三、堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。栈顶指针 Top 应该链表的头部。

struct SNode
{
    ElementType Data;
    struct SNode *Next;
};

typedef struct SNode *Stack;

【1】、创建一个链栈

Stack CreateStack()
{
    // 构建一个堆栈的头节点，返回指针
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return s;
}

【2】、判断链接是否为空

int IsEmpty(Stack S)
{
    // 判断堆栈S是否为空，若为空函数返回整数1，否则返回0
    return (S->Next == NULL);
}

【3】、入栈（Push）

void Push(ElementType item,Stack S)
{
    // 将元素item压入堆栈S
    struct  SNode *TemCell;
    TemCell = (struct SNode *)malloc(sizeof(struct SNode));
    TemCell->Data = item;
    TemCell->Next = S->Nest;                    // 待插入的结点指向原第一个结点
    S->Next = TemCell;                          // 将头结点指向新插入的元素
}

【4】、出栈（Pop）

ElementType Pop(Stack S)
{
    // 删除并返回堆栈S的栈顶指针
    struct SNode *FirstCell;
    ElementType TopElem;

    if(IsEmpty(S))
    {
        printf("堆栈已空\n");
        return NULL;
    }
    else
    {
        FirstCell = S->Next;            // 将链表的第一结点赋值给FirstCell
        S->Next = FirstCell->Next;      // 头结点指向链表的第二个元素
        TopElem = FirstCell->Data;      // 获取原第一个结点的数据值
        free(FirstCell);                // 释放被删除的结点
        return TopElem;
    }
}

四、堆栈的应用

堆栈的用途十分广泛，例如：函数调用及递归实现、表达式求值、深度优先搜索、回溯算法等。

计算机中如何对表达式进行求值的呢？算数表达式由 运算数 和 运算符号 两类对象组成，不同运算符号的优先级也不一样。

中缀表达式：运算符号位于两个运算数之间，如：a + b * c - d / e
后缀表达式：运算符号位于两个运算数之后，如：abc *+ de /-

那我们如何将中缀表达式转换为后缀表达式，然后进行求值呢？经过观察发现：（1）、运算数相对顺序不变；（2）、运算符号顺序发生改变，我们需要存储“等待中”的运算符号，然后要将当前运算符号与“等待中”的最后一个运算符号比较；

将中缀表达式转换为后缀表达式的流程如下：从头到尾读取中缀表达式的每个对象，对不同的对象按不同的情况处理：

运算数：直接输出；
左括号：压入堆栈；
右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈。不输出）；
运算符：
- 若优先级大于栈顶运算符时，则把它压栈；
- 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；在比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
若各对下个处理完毕，则把堆栈中存留的运算符一并输出；