前言

再接学习、实现和练习完顺序表、链表等数据结构后今天我们来学习另外2种常用的数据结构但特殊的线性表——栈和队列

一、栈

1、栈的相关的定义

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素（同端操作）操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，如使用链表（当然用循环链表也可以，但是没有数组来的舒服）尾插的时间复杂较大（每次都需要遍历整个链表）

标题栈顶和栈底如何维护栈

如何进栈和出栈

   栈的实现（源代码）

https://gitee.com/daylight-star/leetcode/tree/master/%E6%A0%88%E7%9A%84%E5%AE%9E%E7%8E%B0/%E6%A0%88%E7%9A%84%E5%AE%9E%E7%8E%B0

二、队列

2.1队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据（异端操作）操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

队列示意图

2.2队列的实现

队列的实现（源代码）

https://gitee.com/daylight-star/leetcode/tree/master/%E9%98%9F%E5%88%97%E7%9A%84%E5%AE%9E%E7%8E%B0/%E9%98%9F%E5%88%97%E7%9A%84%E5%AE%9E%E7%8E%B0

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。（主要原因是队列是头删尾插，可在外部定义一个用于保存头尾指针的结构体，用于维护该链表）

3.循环队列

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现

该结构实现时主要的难题为如何区分是队空还是队满，主要有以下2种解决方法

1.在定义保存头和尾的结构体中，再加一项长度size，用来随时观察其长度

2.在开辟该结构时，将其空间多开辟一个空间，如头尾相同时则为空，尾的下一个为头是则为满

该方法也是使用最常见的方法

 3.栈和队列面试题

1. 括号匹配问题。

有效的括号 - 力扣（LeetCode）

https://leetcode.cn/problems/valid-parentheses/ 2. 用队列实现栈。

队列实现栈- 力扣（LeetCode）

https://leetcode.cn/problems/implement-stack-using-queues/ 3. 用栈实现队列。

栈实现队列.. - 力扣（LeetCode）

https://leetcode.cn/problems/implement-queue-using-stacks/ 4. 设计循环队列。

循环队列- 力扣（LeetCode）

https://leetcode.cn/problems/design-circular-queue/