栈和队列先进先出和后进先出的数据结构
栈和队列是常用的数据结构，它们分别以先进先出（FIFO）和后进先出（LIFO）的方式来组织和管理数据。在许多编程语言中，栈和队列被广泛应用于解决各种问题。本文将从定义、特点、应用和实现这几个方面来介绍栈和队列。
一、定义
栈（Stack）是一种只允许在固定一端进行插入和删除操作的线性数据结构。这一端被称为栈顶，而另一端被称为栈底。栈的特点是先进后出。
队列（Queue）是一种先进先出的线性数据结构，允许在一端进行插入操作，而在另一端进行删除操作。插入操作在队列的尾部进行，删除操作则在队列的头部进行。
二、特点
2.1 栈的特点
（1）插入和删除操作只能在栈顶进行，保证数据的顺序。
（2）栈是一种后进先出（LIFO）的数据结构，也就是最后插入的元素最先被删除。
（3）栈只能在栈顶进行插入和删除操作，不允许在中间或者底部进行操作。
2.2 队列的特点 （1）插入操作只能在队列的尾部进行，保证数据的顺序。
（2）删除操作只能在队列的头部进行，始终删除最先插入的元素。
（3）队列是一种先进先出（FIFO）的数据结构，也就是最先插入的元素最早被删除。
三、应用
3.1 栈的应用
（1）函数调用和递归：栈被用于保存函数调用时的局部变量和返回地址。
（2）表达式求值：使用栈来实现中缀表达式转换为后缀表达式，然后计算结果。
（3）括号匹配：通过栈检查括号是否配对合法。
（4）浏览器的前进和后退：把浏览器的访问记录保存在栈中，方便前进和后退操作。
3.2 队列的应用
（1）任务调度：使用队列管理任务，在现有任务执行完毕后按照先后顺序执行新任务。
（2）缓存管理：常用的缓存淘汰策略是先进先出，即最早进入缓存的数据最早被淘汰。 （3）消息队列：实现进程间的异步通信，提高系统的并发性和可扩展性。
（4）打印队列：打印任务按照先后顺序排队执行，保证打印的顺序。
四、实现
栈和队列可以通过数组或链表来实现。使用数组实现的栈和队列称为顺序栈和顺序队列，而使用链表实现的栈和队列称为链式栈和链式队列。
第05周03--3.1栈和队列的定义和特点1--3.1.2队列的定义和特点
3.1.2队列的定义和特点
队列（queue）是一种先进先出（Frist in frist out）FIFO的线性表。在表的一段插入（表尾），在另一端（表头）删除。
← a1 a2 a3 …… an ←
↑
队头
【删除】 ← Q ← ↑
队尾
【插入】
类似于排队买票：先到的先买先离开，后到的人只能在最后排着【插队没素质】
队列的相关概念
1. 定义：只能在表的一段进行插入运算，在表的另一端进行删除运算的线性表（头删尾差）
2. 逻辑结构：与线性表相同，仍为一对一的关系
3. 存储结构：顺序队或链队，以循环顺序队列更为常见
4. 运算规则：只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则
5. 实现方式：关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同
栈与队列，各有异同。
⾸先是两者的定义：
栈也称为堆栈，是⼀种线性表。
栈的特性： 最先放⼊栈中的内容最后被拿出来，最后放⼊栈中的内容最先被拿出来， 被称为先进后出、后进先出。
队列也是⼀种特殊的线性表。不同于栈所服从的先进后出的原则，队列的原则是先进先出。
队列在队头做删除操作,在队尾做插⼊操作。
然后是两者的异同点
不同点：
1.删除数据元素的位置不同，栈的删除操作在表尾进⾏，队列的删除操作在表头进⾏。
2.队列先进先出，栈先进后出。
3.顺序栈能够实现多栈空间共享，⽽顺序队列不能。
4.遍历数据速度不同。
栈只能从头部取数据，也就最先放⼊的需要遍历整个栈最后才能取出来。
队列则不同，它基于地址指针进⾏遍历，⽽且可以从头或尾部开始遍历⽆需开辟临时空间，速度要快的多。
相同点：
1.都是。
2.插⼊操作都是限定在表尾进⾏。
3.都可以通过顺序结构和链式结构实现。
4.插⼊与删除的时间复杂度与空间复杂度上两者均相同。
再然后便是两者的表⽰和操作的实现
栈表⽰和操作的实现：
#include
#define MAXSIZE 100//基础容量
using namespace std;
typedef struct
{
SElemType *top;//栈顶指针
SElemType *base;//栈底指针
int stacksize;//栈可⽤最⼤容量
}SqStack;
Status InitStack(SqStack &S)//初始化栈
{
S.base=new SElemType[MAXSIZE];
if(!s.base) exit(OVERFLOW);//内存分配失败
S.top=s.base;
S.stacksize=MAXSIZE;
}
Status Push(SqStack &S,SElemType e)//把元素e压⼊栈顶
{
if(S.top-S.base==S.stacksize) return ERROR;//栈满
*S.top++=e;//栈顶指针+1
队列，栈，堆栈，数组，链表特点与区别
1. 队列可以看成是有2个口的集合一个口叫队头一个叫队尾，只能在对头进行删除操作，在队尾做插入。根据这样的操作。队列特点是先进先出
2.堆栈可以看成是有1个口的集合，这个口叫栈顶。插入和删除操作只能在栈顶操作。根据这样的操作。堆栈的特点是是后进先出.
3.链表是一种存储方式，它可以在非连续的内存空间里面存储一个集合的元素。
4.和它对应的是数组，数组要在连续的空间里存储集合的元素
队列、栈是线性数据结构的典型代表，而数组、链表是常用的两种数据存储结构；队列和栈均可以用数组或链表的存储方式实现它的功能
数组与链表：
数组属于顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同（直接访问数组下标）；链表属于数据的链接存储，由于每个
元素的存储位置是保存在它的前驱或后继结点中的，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到自己，访问任一元素的时间与该元素结点在链接
存储中的位置有关。链表和数组是常用的两种数据存储结构，都能用来保存特定类型的数据。
1.占用的内存空间
链表存放的内存空间可以是连续的，也可以是不连续的，数组则是连续的一段内存空间。一般情况下存放相同多的数据数组占用较小的内存，而链表还需要存放其前驱和后继的空间。
2.长度的可变性
链表的长度是按实际需要可以伸缩的，而数组的长度是在定义时要给定的，如果存放的数据个数超过了数组的初始大小，则会出现溢出现象。
3.对数据的访问
链表方便数据的移动而访问数据比较麻烦；数组访问数据很快捷而移动数据比较麻烦。链表和数组的差异决定了它们的不同使用场景，如果需要很多对数据的访问，则适合使用数组；如果需要对数据进行很多移位操作，则设和使用链表。
堆和栈有什么区别：
1. 栈具有数据结构中栈的特点，后进先出，所有存放在它里面的数据都是生命周期很明确（当然要求它不能存放太久，占有的空间确定而且占用空间小），能够快速反应的！所有在Java中它存放的是8个基本数据类型和引用变量的，用完就马上销毁
