数据结构与算法---3（栈和队列）

深碍√TFBOYSˉ_ 2022-03-06 02:54 279阅读 0赞

# 栈 #

**栈是仅限于在表尾进行插入和删除操作的线性表**

我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素的栈称为空栈，栈又称为后进先出的线性表

理解栈需要注意以下几点：

*  首先它是一个线性表，也就是说，栈具有线性关系，即前驱后继关系；只不过他是一种特殊的线性表而已
 *  定义中说的实在线性表的表尾进行插入和删除操作，这个表尾不是指的栈底，而是栈顶
 *  栈的插入操作，叫做压栈、入栈；栈的删除操作，叫做出栈，也叫弹栈

## 进栈出栈的变化形式 ##

最先进栈的元素未必是最先出栈的元素，原因如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70][]

从这个简单的例子可以看到，只是三个元素就有五种变化，如果元素的数量更多，其实出栈的变化将会更多

## 栈的顺序存储结构及实现 ##

利用顺序存储方式实现的栈称为顺序栈，类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的一维数组来实现；栈底位置可以设置在数组的任一个端点，而栈顶随着插入和删除而变化的

栈的顺序存储结构----进栈：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 1][]

出栈：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 2][]

## 栈的链式存储结构及实现 ##

链栈就是将栈顶指针放在链表的头部，代替原来的头指针，这样的话就不需要头结点了

进栈：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 3][]

出栈：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 4][]

# 队列 #

栈是一种先进后出的数据结构，而在实际问题中还经常使用一种先进先出的数据结构；即插入在表的一端进行，删除在表的另一端进行，这种数据结构叫做队列；允许插入的一端叫做队尾，允许删除的那一端叫做队头；队列也是一种运算受限的线性表

## 顺序存储结构 ##

对于队列来说，插如操作我们只需要在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)

删除操作我们要从队头进行删除，删除完成之后依次把队列中的元素向前移动一个位置

第二种方法：

我们设置两个指针；front指向队头，rear指向队尾，当front和rear指向同一个位置的时候，判为空

插入操作只需将队尾指针rear向后移动一个位置，删除操作只需将front向后移动一个位置；但是这样会出现一个问题，如果队列已经满了，我们将front指针向后移动一个位置，这样其实队列中还有一个位置，但是我们已经没法进行插入操作了，这也就是‘假溢出’

## 循环队列 ##

为了解决这种问题，我们可以采用循环队列进行解决；循环队列就是将rear在队尾满的时候下一次插入指向下标为0的位置，这样的话就可以真正使用队列的资源

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 5][]

## 队列的链式存储结构及实现 ##

**队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把他简称为链队列**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 6][]**

入队：

其实就是在尾部插入结点，然后把尾指针转移到新插入的结点上去

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 7][]

出队：

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需要将rear指向头结点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 8][]

总结：

*  链式栈的栈顶应该在链头，插入和删除的操作都在链头进行
 *  循环队列要注意队空条件和队满条件，而对于链式队列，需要特别注意的是出队仅对队头指针操作，当只有一个元素的时候
 *  递归实质上是通过栈来实现函数调用，只不过是调用自身而已
 *  使用循环队列的时候必须 有一个固定的长度，所以就会有存储元素个数和空间浪费的问题，而链队列不存在这个问题，尽管它需要指针域，会产生一些空间上的开销，但是可以接受，在空间上，链队列更加灵活；总的来说，在可以确定队列的长度的情况下，建议使用循环队列，如果你无法预估队列的长度的时候，建议使用链队列

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70]: /images/20220306/2cb64dd8d1af4dd68dd8ed73666067c2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 1]: /images/20220306/a118275952a4483d8e582e8bc442b687.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 2]: /images/20220306/8ab57a0753b448ecaa5de115f03b481c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 3]: /images/20220306/3f2ca4527b0a4849b11e06fed1b31f32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 4]: /images/20220306/10f712f1e7ac4ec3ad5a58c4e0e39212.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 5]: /images/20220306/01440983e9634af483dea7f56f6377ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 6]: /images/20220306/18467fd91918408ab58222e5c6bc4794.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 7]: /images/20220306/3f126856b33c475a856440652a47aa67.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 8]: /images/20220306/32a5a7f3b771434b91c4a69f651b3f77.png