C语言数据结构与算法——栈（1）

Dear 丶 2022-12-17 02:23 258阅读 0赞

**栈的定义**：  
作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一段进行。（一般在表尾进行）  
如下表：  
表中**允许插入、删除擦欧总的一端称为栈顶（Top）；**  
表的**另一端被称为栈底（Bottom）**。  
![在这里插入图片描述][20201021152047504.png_pic_center]  
当栈中没有元素时称为**空栈**。  
栈的**插入**操作称为**进栈**或**入栈**。  
栈的**删除**操作称为**出栈**或**退栈**。

**栈的特点：后进先出（LIFO）**  
栈的存储结构;**顺序存储**和**链式存储**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]  
顺序栈的C原因呢描述：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]  
栈的基本操作：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 9]

**双端栈**  
双端栈就是栈的两边各有自己的栈顶和栈尾。分别可以在两端进行进栈和出战操作。  
注意：  
双端栈的两端是它的栈底，它是不变的！！！

**双端栈的特点**：  
**后进先出（LIFO）  
先进后出（FILO）**  
注意：  
当程序里边有多个栈时，首先讨论两个栈的共享空间问题。

不确定哪个栈已经达到最大空间，有可能会出现其中的一个栈满，并且发生了溢出但是其余的栈都还是空闲的或只是使用了一部分存储空间的情况。

如果在空间有限的情况下，怎么样充分利用？  
如下：

两栈共享技术——双端栈  
主要利用了“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间【M】，将两个栈的栈底分别放在一维数组的两端，分别是0 ， M-1。  
![在这里插入图片描述][20201021145130746.png_pic_center]  
两个栈是相对的！！！

两栈共享数据结构的定义：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 10]  
对双端栈操作应注意：  
![在这里插入图片描述][20201021145352716.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 11]  
**双端栈的初始化：**  
![在这里插入图片描述][20201021145600761.png_pic_center]  
**双端栈的进栈**：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 12]  
**双端栈的出栈：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 13]

**多个栈共享空间：**  
![在这里插入图片描述][20201021145933776.png_pic_center]  
但是这种方法的不好之处在于，如果我们想往其中的一个栈中插入一个元素，则后面所有的栈都要往后移动来空出一个位置，这样一来，元素移动量较大，这样是比较浪费时间的！！

要避免栈上溢出更好的方法是使用链式存储结构，让多个栈共享所有可用存储空间——链栈。  
明天继续！！！

[20201021152047504.png_pic_center]: /images/20221123/1f35b33ad0594b77aedabc99f0563f66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/a466f53b1d814ca7b4656ef69c2eb1b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/5f4adc5040c54e29be525bb8d49f35d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/46e87f68cae7447884312016671d927a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/383fcd85604343c19d3babf5aa41f1d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/a9c41ae5e3f3479fb387ea3d8c71d47a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/0dc540cc5dd74ff8829e32690d1e9fae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/ee680ece3dcc4de18eb82921062533f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/1ba931c75ec1483d89cf1159b0625a8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/0c2c110f4c4d436cbf882a4a40838acf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/d7249d836e644c5798569010e9cdb1ac.png
[20201021145130746.png_pic_center]: /images/20221123/edeb4c8ae1ac4b1c8ffda7982ee95311.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/2354e00dd16142088d8061cc7537d149.png
[20201021145352716.png_pic_center]: /images/20221123/72fc9ab306174eb0926789d34525d9d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/f90bd8e3c8cc4625a9af06f3a574b72d.png
[20201021145600761.png_pic_center]: /images/20221123/b7a0119a066242179147b56b718bd62c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221123/933285576cb64587a9098ad34f3b5573.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221123/e828bbea39814150a211a44ecd4ee8cc.png
[20201021145933776.png_pic_center]: /images/20221123/780f7692bb1d444bace12b7c495ff7c7.png