栈和队列的创建

栈和队列的区别：
?? ?栈：栈类似于只有一个口的容器，先进入的元素只能后出，最后进去的元素在栈顶，可以最先出栈
?? ?栈的出栈入栈相反，
?? ?入栈顺序|ABC|
?? ?出栈顺序|CBA|
?? ?栈顶为操作端，栈底为封口
?? ?LIFO--last in first out
?? ?先入后出
?? ?java中提供栈Stack方法
?? ?push();入栈 ? ?pop();出栈 ? peek();查看栈顶元素
? ? getSize();内存 ? ? boolean isEmpty()判断为空
?? ?

栈的基本方法：

1.入栈? ? ?2.出栈? ? 3.查看栈顶元素? ? ?4.删除元素? ?5.查看是否为空? ? 6.查看栈的容量

public class ArrStack<T> implements Stack<T> {

    private MyArr data;//容器
    int size;//栈中实际存放元素个数
//用crtl+i实现接口的重写
    public ArrStack(){
        this.data=new MyArr<>(100);
        this.size=0;
    }
    @Override
    public boolean isEmpty() {
        if(size==0)
        {return true;}
        return false;
    }

    @Override
    public int getSize() {
        return 0;
    }

    @Override
    public void push(T ele){

    }

    @Override
    public T pop() {
       if(isEmpty()){
           return null;
       }
       this.size--;
       return (T) this.data.removeFromLast();
    }

    @Override
    public T peek() {
        return null;
    }

?? ?
?? ?
?? ?队列：
?? ?只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
?? ?入队列：进行插入操作的一端称为 队尾 ? ??
?? ?出队列：进行删除操作的一端称为 队头
?? ?先进先出，队尾插入数据，队头删除数据

队列的基本方法：

1.入队? ? ?2.出队? ?3.查看队首元素? 4.查看是否为空? ? 5.查看队列元素个数

public interface Queue_I<T> {
    //入队
    void offer(T ele);
    //出队
    T pool();
    //查看队首元素
    T peek();
    //队列中元素的个数
    int getSize();
    //队列是否为空
    boolean isEmpty();
}

      private T[] value;    //保存数据
        int size;   //实际存放个数
        int capacity;   //容积

        private int head;
        private int tail;



        //判断数组是否为空
        public boolean IsEmpty(){
            if(this.head==this.tail){
                return true;
            }else{
                return false;
            }
        }

        //向数组中添加元素
        public void add(T data){
            //扩容
            if((this.tail+1)%this.capacity==this.head){   //如果数组满了就重新设置容积
                resize((this.capacity-1)*2+1);  //先把容积变为原先的容积，再×2，加1是循环队列队满时有一个空
            }
            this.value[this.tail]=data;
            //因为是循环的，当队尾指到最后了就需要重新回到第一个位置继续加
            this.tail=(this.tail+1)%this.capacity;
            this.size++;
        }

        //移除队首元素
        public T remove(){
            //缩容
            if(this.size<=this.capacity/4&&this.capacity/2>0){
                resize((this.capacity-1)/2+1);  //与扩容同理
            }
            if(IsEmpty()){
                return null;
            }else{
                T e=this.value[head];
                this.value[head]=null;
                //head指向末尾时需要重新循环到开头，所以如下
                this.head=(this.head+1)%this.capacity;
                this.size--;
                return e;
            }
        }

        //重新给容积
        private void resize(int newcapacity){
            //由于数组的容积都是不变的所以需要新建一个数组
            T [] newvalue=(T[])(new Object[newcapacity]);
            //转移数组
            for (int i = 0; i < this.size; i++) {
                newvalue[i]=this.value[(this.head+i)%this.capacity];    //给新数组赋值，此时capacity还没有变，所以%this.capacity
            }
            //改变容器，数组
            this.value=newvalue;
            this.capacity=newcapacity;
            this.head=0;    //从头开始
            this.tail=this.size;    //尾指针指向最后一个元素的下一个位置也就是size
        }