栈和队列---

栈

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

栈的实现（动态）首先，这是一个线性表实现的，所以我们有两个选择：顺序表，也就是数组实现；或者链表实现。

栈的实现 —— 数组好还是链表好？

其实我们栈的插入和删除相当于尾插尾删用数组的唯一缺陷就是不够的时候要增容用单链表就不太好了：尾插尾删要找尾如果不找尾，用尾指针记录尾结点。但是即便这样，我们也要找到前一个，所以要不就使用双链表实现。如果一定想使用单链表，把把栈顶栈底反一下，用头插，不要用尾插即可所以用单链表也是ok的

如果用尾作栈顶，那么用双链表好

如果要用单链表实现，那么就用让头作栈顶总和各方面的要素，使用数组（顺序表）实现是最合适的。

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头。只一端入数据，没必要用双向循环链表，使用单链表。

队列的应用场景

1、排队，保持绝对的公平性

2、广度优先遍历 BFS