2、堆栈（Stack）

后进先出的数据结构

一、堆栈的抽象数据类型描述

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

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

二、栈的顺序存储实现

1.定义

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

#define MaxSize <储存数据元素的最大个数>
typedef struct SNode *Stack;//定义SNode的结构指针可以用Stack
struct SNode {
    ElementType Data[MaxSize];//一维数组
    int Top;//记录栈顶元素
};

Stack PtrS 既定义了一个指向SNode 的结构体指针PtrS

2.操作

(1)入栈操作(Push)

Top值加一，存储元素item在栈顶

void Push(Stack PtrS, ElementType item) {
    if (PtrS->Top == MaxSize-1) {//堆栈全部放满了
        printf("堆栈满");
        return;
    } else {    //堆栈未满，执行入栈操作
        PtrS->Data[++(PtrS->Top)] = item;//Top值先增加，然后存储
        return;
    }
}

(2)出栈操作(Pop)

将元素弹出,Top值减一

ElementType Pop(Stack PtrS) {
    if(PtrS->Top == -1) {//堆栈为空
        printf("堆栈空");
        return ERROR;//ERROR是ElementType的特殊值，表示错误。
    } else 
        return (PtrS->Data[(PtrS->Top)--]) //先把栈顶元素返回，再将Top减一
}

三、栈的链式存储实现

1.定义

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

typedef struct SNode *Stack;
struct SNode {
    ElementType Data;//当前数据
    struct SNode* Next;//指向下一个Snode的指针
};

2.操作

(1)堆栈初始化（CreateStack）

构建一个堆栈的头结点，返回指针

Stack CreateStack() {
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

(2)判断堆栈是否为空（IsEmpty）

判断堆栈S是否为空,若为空函数返回1，否则返回0

int IsEmpty(Stack S) {
    return (S->Next == NULL);//若后面没节点，则为空
}

(3)将元素item压入堆栈 (Push)

先创建一个新结点的结构指针TmpCell，分配空间，然后将数据赋值为item，Next指针赋值为原先的S的Next指针。再将S的Next指针指向TmpCell。

void Push(ElementType item, Stack S) {
    Stack TmpCell;
    TmpCell = (Stack) malloc(sizeof(struct SNode));
    TmpCell->Data = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

(4)删除并返回堆栈S的栈顶元素 (Pop)

先暂存当前结点(S) ，将FirstCell赋值为S的Next指针，再将S的Next指针赋值为下一个的地址，既让S的Next指针直接指向第二个结点。然后将FirstCell内的数据取出并释放动态分配的内存，返回该数据。

ElementType Pop(Stack S) {
    Stack FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)) {//若为空
        printf("堆栈空");
        return NULL;
    } else {
        FirstCell = S->Next;//先把指向下一个结点的指针存起来
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Data;
        free(FirstCell);
        return TopElem;
    }
}

四、堆栈应用（表达式求值）

中缀表达式如何转换为后缀表达式？ 从头到尾读取中缀表达式的每个对象，对不同对象按照不同情况处理

1. 运算数：直接输出。

2. 左括号：压入堆栈。

3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）

4. 运算符：优先级大于栈顶运算符时，将其压入栈中；优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出，再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级位置，然后将该运算符压入栈中。

5. 若各对象处理完毕，则将堆栈中存留的运算符一并输出。

堆栈的其他应用：函数调用与递归实现、深度优先搜索、回溯算法等……