线性表 -- 栈和队列

线性表：数组，链表，字符串，栈，队列

元素按照一条直线排列，线性表这个结构中，一次添加单个元素

非线性结构：树，图

---

栈stack：后进先出的线性表，支持三个核心操作：入栈PUSH、出栈pop、返回栈顶元素peek

栈和队列是一个使用上更加严格的线性表。

动态数组、链表可以在任意位置进行插入和删除

水杯就是一个天然的栈结构，后进先出LIFO (last in first out)

栈的实际应用

Ps：1.无处不在的撤销操作undo,撤销本质就是一个栈的pop

2.浏览器的前进后退，A-B-C,此时留在c页面，看完C想反悔B，点击后退箭头相当于将C出栈，此时栈顶就是B

3.开发中程序的“调用栈”操作系统栈底层就是我们的栈实现,碰到return就是方法的出栈

---

栈也是一个线性表，底层既可以使用数组，也可以使用链表

基于数组实现的栈--顺序栈--数组尾部的添加和删除，时间复杂度是O(1)--栈顶就是数组末尾

基于链表实现的栈--链式栈--尾插和尾删

public class MyStack <E>{
    private int size;//当前栈的数据个数
   private List<E> data = new ArrayList<>(); //实际存储数据的动态数组
    
    //将value入栈
    public void push(E val){
        //默认尾插
        data.add(val);
        size++;
    }

    //弹出栈顶元素，返回栈顶的值，出栈，方法是E类型
    public E pop(){
       if(isEmpty()){
           //栈为空
           throw new NoSuchElementException("satck is empty!cannot pop!");
       }else{
           //删除栈顶元素
//           E val = data.remove(size -1);
//           size --;
//           return val;

           return data.remove(-- size);
       }
    }

    //返回栈顶元素
    public E peek(){
        if(isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size -1);
    }

    //当前的栈是否为空
    public boolean isEmpty(){
//        if(size == 0) return true;
//        return false;
        return size ==0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            //栈不为空
            sb.append(data.get(i));
            if (i != size - 1) {
                //此时栈还没到栈顶，还没走到数组末尾
                sb.append(", ");
            }
        }
        sb.append("] top");
        return sb.toString();
    }

    //系统自带
//    @Override
//    public String toString() {
//        return "MyStack{" +
//                "size=" + size +
//                ", data=" + data +
//                '}';
//    }
}

---

队列FIFO(first in first out)

队首出队，在队尾入队，先进先出的数据结构

生活中：银行食堂的排队

基于数组实现的队列 -- 顺序队列

基于链表实现的队列 -- 链式队列（由于队列是从队尾入队，队首出队，数组头部删除，因此用链表更好一些）

队列的子类比栈来说要复杂一些：

1.基础队列FIFO

2.基于优先级的队列  按照优先级大小出队

3.循环队列  基于数组实现的

4.双端队列 

无论哪种队列，都需要支持三个核心操作：入队offer、出队poll、返回队首元素peek

因此我们设计队列为接口。 

力扣20

public class MyQueue<E> implements Queue<E> {
    //不只是继承的接口要写泛型，这个继承的类也要写泛型

    //链表的每个节点
    //--------------------
    //这些部分都是内部类
    private class Node{
        E val;
        Node next;
        public Node(E val){
            this.val = val;
        }
    }
    //-------------------
    //当前队列的元素个数
    private int size;
    private Node head;
    private Node tail;
    //链表的队首和队尾

    @Override
    public void offer(E val) {
        //要插入的话，必须先有一个新的结点
        Node node  = new Node(val);
        if(head  == null){
            //此时链表为空
            head = tail = node;
        }else{
            tail.next = node;
            tail = node;
        }
        size ++;
    }

    @Override
    public E poll() {
        //出队，先进先出
      if(isEmpty()){
          throw new NoSuchElementException("queue is empty!cannot poll!");
      }
      E val = head.val;
      Node node = head;
      head = head.next;
      //将原来头结点脱钩
        node.next = null;
        size --;
        return val;
    }

    @Override
    public E peek() {
        //获取队首元素
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
       StringBuilder sb = new StringBuilder();
       sb.append("front[");
       //链表的遍历
        for (Node x = head;x != null; x = x.next) {
            sb.append(x.val);
            if(x.next != null){
                //链表还没走到尾部
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

---

循环队列：队列是一个环，逻辑上成环，物理上是线性表

head 指向当前队列的第一个元素下标

tail指向当前队列的最后一个元素的下一个位置

当tail走到数组末尾时，下一步再次返回数组头部

优点：1.比普通队列更省空间

2.出队时，直接将head引用向后移动即可，不需要再搬移元素。head = head+1

环形队列判空：head == tail

浪费一个空间，来区分数组是否已满。判满：tail = (tail+1)%data.length == head

head和tail不能简单地加一，要加一后对数组长度取模

tail = (tail+1)%data.length,让tail从末尾返回数组头部

head = (head+1) %data.length

如何获取到当前循环队列的最后一个元素的索引呢？

lastIndex = tail == 0? data.length - 1 :tail - 1