栈

浏览器的前进后退的功能思路

当访问页面a-b-c 点后退 可以访问 a b
当后退到a点击前进 可以看b c
但是 如果后退到b 点击了d 就不能访问c了

如何理解栈

盘子 从下往上叠 取的时候也是从上往下拿 不能从中间最后抽取
后者进 先出 前者进 后出
image.png

  • 操作体系
    • 操作受限的线性表
    • 只允许一端插入和删除数据

  • 功能特性

    • 数组和链表暴露了太多操作接口 操作灵活 但是不可控

      如何实现一个栈

  • 入栈

  • 出栈
  • 栈顶插入/删除数据

可以由数组或者链表实现

  • 顺序栈
  • 链式栈

顺序栈

  1. public class ArrayStack{
  2.     private String[] items;//栈数组
  3.     private int count;//栈中的个数
  4.     private int n;//栈大小
  5. public ArrayStack(int n){//初始化栈的大小
  6.     this.n = n;
  7.     this.items = new String[n];
  8.     this.count = 0;
  9. }
  10.     //入栈
  11.     public boolean push(String item){
  12.         //数组空间不够 直接返回fasle 入栈失败
  13.         if(count==n){return false;}
  14.         //将item放于下标为count的地方
  15.         items[count]=item;
  16.         ++count;
  17.         return true;
  18.     }
  19.     //出栈
  20.     public String pop()
  21.     {
  22.         if(count==null){
  23.          return null;//栈为空返回null   
  24.         }
  25.         String tmp = item[count-1];
  26.         count--;
  27.         return tmp;
  28.     }}

空间复杂度
只需要一个n的数组 而在入栈或者出栈只需要临时空间 素颜空间复杂度o(1)
时间复杂度
没有循环O(1)

支持动态扩容的顺序栈

  • 刚才数组实现的顺序栈
    • 不能够动态扩容
    • 需要在开头制定大小 超出则不可用]

栈/队列 - 图2
出栈

  • 因为出栈不涉及内存的搬运所以时间复杂度为O(1)

入栈

  • 当数组满了之后涉及动态扩容 需要搬动n个元素 所以为O(n)

    数组如何支持动态扩容

    数组空间不够的时候 重新申请一块更大的内存 将数组的数组拷贝过去

    栈在函数调用中的作用

    操作系统给每一线程分配了独立空间 被称为栈 用于存储函数调用存储的临时变量 ```java

int main() { int a = 1; int ret = 0; int res = 0; ret = add(3, 5); res = a + ret; printf(“%d”, res); reuturn 0; }

int add(int x, int y) { int sum = 0; sum = x + y; return sum; }

![image.png](https://cdn.nlark.com/yuque/0/2020/png/403990/1598584947070-bbd273b1-a49a-476e-95dd-8c02c3d58ec8.png#align=left&display=inline&height=152&margin=%5Bobject%20Object%5D&name=image.png&originHeight=304&originWidth=370&size=77865&status=done&style=none&width=185)依次进入栈
<a name="dZ9cr"></a>
## 栈在表达式求值中的应用
3+5*8-6

- 计算机是用两个栈实现
- 一个保存操作数
- 一个保存运算符
- 从左到右遍历 
   - 遇见数字 压入操作数栈
   - 遇见运算符 压入运算符栈 并且与栈顶元素比较 如果优先级高则压栈 
   - 低或者相同 从栈顶取出运算符 从操作数栈顶取两个操作数 计算 计算完结果压入操作数栈
<a name="ZHkRM"></a>
## 如何实现浏览器前进后退

- 使用两个栈X/.Y
- 首次浏览压入栈X 后退取出栈放于Y
- 前进从Y取给X
- 当X中没有数据则不能后退
- 当Y中没有数据说明页面不能前进
<a name="wH4BL"></a>
# 队列
<a name="IXJQS"></a>
## 队列在线程池等有限资源池中的应用
<a name="921fb"></a>
## 如何理解“队列”

- 先进先出
- 入队enqueue 放一个在队伍尾部
- 出队dequeue 取一个在队列头部
- 队列和栈都是操作受限的线性表结构
<a name="BDiAn"></a>
## 顺序队列和链式队列
```java
public class ArrayQueue{
  private Stirng[] items;
  private int n;
  private int head;
  private int tail;
  public ArrayQueue(int capacity){
 this.items = new String[capacity];
      this.n = capacity;
      this.head=0;
      this.tail=0;
  }
    //入队
    private Boolean enqueue(String item){
     if(tail = n) {
     return false;}
        //最后
    item[tail] = item;
    ++tail;
        return true;
    }
    //出队
    public String dequeue(){
        //没数据
     if(head == tail){return null;}   
    String ret = itmes[head];
        ++head;
        return ret;
    }
}

优化:由于数组的删除操作会导致数组的数据不连续 数据搬移
出队的时候不需要搬运数据 在入队的时候集中触发一次数据搬移
也就是说最开始进去出去都是会搬运内存的 而都是先进先出 都是最上面的先出去 所以我们
想出去的时候先把位置记住 而等到进去的时候直接把它放最后在把前面是移除

//入队
   private Boolean enqueue(String item){
     if(tail = n) {
     return false;}
        //最后
    item[tail] = item;
    ++tail;
        return true;
    }
//优化
   private Boolean enqueue(String item){
    if(tail==n){
    //队列末尾没位置
        if(head==0){
        // tail ==n && head==0，表示整个队列都占满了
            return false;
        }
        //数据搬移
        for(int i=head ; i<tail ;i++){
        item[i-item] = item[i];
        }
        //搬运完了 重新更新head tail
        tail - = head;
        head=0
    }
  items[tail] = item; ++tail; return true; }