数据结构：栈

谁借莪１个温暖的怀抱￠ 2021-12-07 12:07 406阅读 0赞

先来一张总体结构图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MTk4NDY3_size_16_color_FFFFFF_t_70][]

栈的实质其实还是线性表

# 栈的定义： #

那么栈究竟是什么呢！其实他就是一个只能在一端进行插入或者删除操作的线性表！！！记住两点，首先他只能在一端进行操作，其次他是一个线性表。

既然是只能在一端进行操作，那么肯定对这一端有特殊的名词。嘿嘿..

明显，我们能够操作的那一段叫**栈顶**，而不能操作的那一段叫**栈底**。

栈顶指针：和我们前面线性表的头指针一样，关于栈顶指针，只需要记住一点，它始终就是指向栈顶元素的，其他的你就别管那么多，别把自己绕进去了。

而通过栈的定义我们知道，只能在一端操作，那很明显，肯定是先进去的东西后出来，后进去的先出来，或者说谁最后进去，谁就最容易被拉出来宰了。而这个东西，实际上就是栈的**逻辑结构**

# 栈的物理结构： #

既然栈的本质是线性表，那栈肯定也有和线性表相同的地方呀！

## 顺序栈： ##

其实就是在线性表的顺序结构上改了改

在线性表的顺序表中，我们通常是用数组来表示的嘛，那这里其实是一个道理，我们同样可以用数组来表示，既然这样，那么数组的下标其实就相当于顺序栈每一个元素的逻辑地址，也就是说栈顶指针就是这个数组的下标，很显然，我们稍微想一下。当数组有一个元素的时候，它的下标应该是多少？很明显是0，那如果没有元素呢？这个时候我们就是做一个通用的认知，将栈顶指针的值改为-1，也就是说，当顺序栈为空的时候，栈顶指针的值就是-1.这个就是顺序栈的判空条件。那有空栈，自然也有满栈，因为还是数组，我们一定要搞清楚，数组的下标和实际数组中元素的个数是相差1的，所以当顺序栈满栈的时候，它的栈顶指针应该是数组的长度-1。

### 顺序栈的操作： ###

**判空操作：**

经过上面的解释，我们已经知道了顺序栈的判空条件，就是判断栈顶指针的值是否为-1.

**进栈操作：**

肯定是先判断是否已经满栈了，这个是没得说的，当没有满的时候，其实就是先把栈顶指针往下一个下标移动，然后就是把新的元素复制到这个下标位置上。这里注意一点就行了，当还没有插入数据的时候，栈顶指指向的是带插入位置的前一个位置，非常好理解，因为你还没有插入元素嘛，所以当前的栈顶元素肯定就是带插入位置的前一个位置的元素赛。而栈顶指针是指向栈顶元素的。

**出栈操作：**

首先也是要判断是否为空战，如果是空栈，那直接就没有元素可以出栈了呀。如果不是空栈，就将栈顶元素的值赋值给给一个变量，然后把栈顶指针下移一个角标就行了。

读取栈顶元素：

这个就更加简单了呀，反正就是取值嘛，先判断一下是否为空栈，如果不是，那直接取栈顶指针所指的那个下标的值呗。

# 共享栈： #

因为顺序栈的创建，是需要提前开辟好空间的，所以单独给每一个顺序栈都开辟空间，那肯定就比较浪费空间，所以我们可以把两个栈放到一起呀，怎么放呢?我们就这么干，分别在两端表示两个栈的栈底，也就是说，一个空间，我两个栈进栈的方向是相对着的，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MTk4NDY3_size_16_color_FFFFFF_t_70 1][]

看见没有，就是这个个玩意儿，这样一来，他们的空间是否就实现了共享？而且，因为入栈的方向是相对着的，所以他们可以各自填空对方的空白区域，这个就是我们所的共享栈。

很明显，因为是一个一个的元素添加，那么共享栈的满栈就是当两个栈顶指针挨着的时候就满栈了，比如top1在数组下标1这里，而top2在数组下标2这里。

# 链式栈：（链栈） #

想想看前面线性表的时候有什么？对！链表！也就是线性表的链式存储结构，那很明显了，因为栈就是一种受限制的线性表嘛，所以栈肯定也是有链式存储结构的，我们就叫做链栈。那么我们合计合计前面的想一下，其实在链栈中我们就是将栈顶指针当作头指针。很显然链栈一般是不存在满栈的情况的，因为都是通过动态分配的嘛，存放的是地址，只要知道地址信息就能把两个节点联系起来，如果一定是满栈了，那基本是计算机的内存都满载了。

另外注意一点，链栈的空栈判断条件是栈顶指针是否为null。对比一下前面的顺序栈，因为它使用的是数组，所以空栈是判断栈顶指针的值是否为-1。

### 链栈的操作： ###

**入栈操作：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MTk4NDY3_size_16_color_FFFFFF_t_70 2][]

我们看着这幅图，比如现在是需要把新的元素x入栈，记住栈的原则，只能在栈顶操作，那现在的逻辑代码应该是怎么样的。肯定是先给这个新的元素分配存储空间，然后怎么样呢？给它赋值，完成赋值之后就要进行真正的入栈操作了。先把x元素的后继指向栈顶元素c，然后再将栈顶指针指向新的元素x，因为这个时候栈顶元素就是x，而栈顶指定是指向x的。

**出栈操作：**

算法思想上和入栈操作没什么区别

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MTk4NDY3_size_16_color_FFFFFF_t_70]: /images/20211207/88e43bccb88c455d8720f6bd6959e4a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MTk4NDY3_size_16_color_FFFFFF_t_70 1]: /images/20211207/13f4b3bf8e434291818c9df6a46aa9d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MTk4NDY3_size_16_color_FFFFFF_t_70 2]: /images/20211207/de4348bf44e54c40b83db98ab72a6a55.png