数据结构学习笔记＜2＞堆栈

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

类型名：堆栈（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. 若各对象处理完毕，则将堆栈中存留的运算符一并输出。#

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