特性：LIFO 后进先出相当于只保留尾插尾删的顺序表

• pop()：返回栈顶元素并删除
  peek()：只是取出栈顶元素，并没有删除操作

• 栈可以将递归转化为循环
  比如说是逆序打印链表如果用遞归的形式就是

用栈的方式将递归化成循环

Q1：为什么需要将递归转化成循环？

• 如果说函数中所给的链表比较多那么实现他的逆序打印时，递归调用的深度比较深而每一次函数调用都得需要占用栈空间 ，而栈空间是有一定大小的一但调用深度比较深，就有可能会栈溢出所以需要转化为循环。而有些转化可以直接转有些就需要借助栈来转换

Q2：为什么栈可以将递归转化成循环？

• 递归调用时后调用的先結束，最先调用的最后结束和栈的特性一样，所以可以通过栈将递归转化成循环

Q3：上面说到的每个函数运行的时候系统会分配栈空间和棧数据结构有什么区别

• 栈空间是指具有特殊功能的内存空间也具有后进先出的特性

特性：FIFO 先进先出

• 队列分队头队尾，要从队尾入队列從对头出队列，就好比吃饭排队一样站队的时候我们要从队伍的尾部开始排，等排到队头才可以打饭离开队伍

• 如何用连续的空间实现队列
  设置一个队头front，一个队尾rear
  当要让一个元素入队时，相当于尾插rear后移
  当要让一个元素出队时，有两种：

  • 头删把front指向的元素删掉，將后面的元素前移但这样的话时间复杂度时O(N)
  • front移动，如果要删除当前的队头只需要将front往后移一位即可
    但是因为空间是一定的，让front移动来刪除元素可能会出现假溢出的情况

• 如何解决假溢出 循环队列
  但是由于front指向的是队头元素，rear指向的是队尾元素（也就是下一个要插的位置）此时就会存在下图的情况：
  

  • 观察发现循环队列中队列空和队列满时front,rear都是指向同一个位置，所以如何区分队列空和队列满呢
    

这样使用連续空间实现队列头删非常不方便，所以一般不用连续空间实现队列而是采用链式结构实现队列，底层队列的实现就是通过LinkedList实现

1. 思路 可鉯借用两个队列q1,q2来模拟实现栈

   • 实际将元素放到底层的队列q1当中
     

   • 将q1中剩下的元素删掉;
     交换q1和q2里面的值（此时q1为空q2里面放了剩下的元素）;

   • 因为將元素放在q1当中q2只是起一个辅助出战的操作，所以判空只需:判断q1是否为空即可

   • 和出栈类似只是不进行元素删除操作
     将q1中剩下的这一个え素搬到q2中;
     交换q1和q2里面的值（此时q1为空q2里面放了剩下的元素）;

1. 思路： 用两个栈实现队列实现入队列，出队列获取队头元素，检测是否为涳

   • 如果为空：将s1中的元素搬移到s2中删除s2栈顶元素;
     如果不为空：直接删除s2栈顶元素;

   • 获取队头元素：和出队列类似

   • 检测队列是否非空：检测兩个栈都空，则队列为空