DS线性表之栈的讲解和实现(4)

---

前言

  栈就是一个比较实用的数据结构了，且大致逻辑就是套用之前的两种线性表

  具体选择哪种呢？请看正文！

---

一、栈的概念及结构

  栈是指一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则（与我们后面要学的队列先进先出的思想刚好相反）

这里主要分享的是跟数据结构相关的栈，而不是指存储内存一块内存区域栈区，栈区是指CPU寄存器里的某个指针所指向的一片内存区域(存放函数的参数值，局部变量的值等)

栈有两种核心操作：压栈和入栈

• 压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶

所以我们可以发现，栈的入栈顺序只有一种，但是却可以有很多种出栈方式

题目：一个栈的入栈序列为ABCDE，则不可能的出栈序列为（ ）
A.ABCDE // 放一个拿一个
B.EDCBA // 全部放完后再连续拿五次
C.DCEBA
D.ECDBA
答案:D

二、关于实现栈的分析

  栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，实现起来也更容易，且我们在顺序表那里也说过了静态表实用价值不大，于是我们这里采用动态顺序表来实现栈

关于栈顶指针top

请注意，虽然这里说top是栈顶“指针”，其实并不是一个真正的指针，而是一个下标，只是起到指向作用，故采取这一称呼

我们可以注意到，栈顶有两种定义方式：

1. top为-1代表空，top为0代表一个元素
2. top为0代表空，top指向下一个元素下标

其实两种都行，只是对于后面的插入数据即入栈时候的操作有所差别：

在这里我才用第二种方式，令top一开始为0，即让top指向下一个元素的下标

关于结构体

typedef int StackDataType;
typedef struct Stack
{StackDataType* a;int top;int capacity;
}ST;

栈的初始化

除了验空外还是一样的置空指针，且让栈顶指针指向第一个位置，容量也设为0

void STInit(ST* pst)
{assert(pst);//指向一个有效的结构体pst->a = NULL;pst->top = pst->capacity = 0;
}

入栈

同前面一样，既然是往数组里塞东西，就必须要验证是否满栈
不一样的是，我们在这里验证是否满栈并没有单独封装成一个函数，这是因为我们只有在栈顶这一个地方进行入栈操作，其实就是尾插，因此不需要单独再实现一个函数

void STPush(ST* pst, StackDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;StackDataType* tmp = (StackDataType*)realloc(pst->a, sizeof(StackDataType)*newcapacity);if (tmp == NULL){perror("realloc fail!!!");return 1;}pst->capacity = newcapacity;pst->a = tmp;//保证安全返回}pst->a[pst->top] = x;//插入 pst->top++;//注意top的意义--之后里面为1没有给数值
}

出栈

注意栈顶指针是指向栈顶元素的下一个位置的下标，那我们不是将栈顶指针-1不就完成了出栈操作吗

其实就是尾删

void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);//top为0，则是为空pst->top--;//元素个数--
}

获取栈顶元素

注意栈顶指针是栈顶元素的下一个位置的下标，所以我们要减一才能得到正确的数据，但是不能自减！因为这里并没有出栈的操作

StackDataType STTOP(ST* pst)//得到栈顶元素
{assert(pst);return pst->a[pst->top-1];//这里减的话就会有问题
}

获取栈元素个数

乐，其实还是看栈顶指针top，因为是指向下一个元素的下标，下标又是从0开始，两者一结合，那么top其实就是元素个数

int STSize(ST* pst)
{assert(pst);return pst->top;
}

判断栈是否为空

栈为空，就是大小是否为0，结合上一个函数，我们可以很自然而然的写出

bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

栈的销毁

销毁，首先就是要回收Stack结构体里面的 STDataType* 指针所指向的内存并置空指针

void STDestroy(ST* pst)//销毁
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}

---

总结

  栈是我们学习的第一个实用数据结构，且我们在未来的学习会经常遇到它，请好好体会它“后进先出”的思想，想想可能会有哪些具体实用场景