栈与队列（详解）

学习自省

2649人浏览 · 2022-09-28 15:01:56

学习自省 · 2022-09-28 15:01:56 发布

日升时奋斗，日落时自省

一、栈

1.1栈的基本概念

栈：是一种特殊的线性表，栈只允许在固定的一端进行插入和删除元素操作，进行数据删除和插入时，一端是栈顶，另一端是栈低，栈中遵循元素先入后出

压栈：就是将数据放入栈中。

出栈：栈的删除操作叫做出栈。弹出栈

1.2栈的模拟实现

栈的底层实现时依靠顺序表也就是数组实现的，这里模拟实现也是数组构成的栈

栈入通过这张图比较好理解

栈出下图解释：

栈出并不是真的删除某个值，而是将有效值的个数减一。

问题？下次还会栈出吗，不会因为我们栈出有效栈的数据个数，下次push时就会将原来的数据覆盖

public class MyStack {
    public int[] elem; //建立当前数组 构建栈空间
    public int usedSize;   //计算当前栈中的个数
    public static final int DEFULT_SIZE=10;   //暂时给定栈中为10个空间
    public  MyStack(){
        this.elem=new int[DEFULT_SIZE];    //构造方法传值
    }

    public  int  push(int  val){   //入栈
        //1、入栈限制，栈是否满了
        //2、将传入的数据给数组，入栈结束
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);   //如果空间不够，进行扩容
        }
        this.elem[usedSize]=val;    //将只当前值直接给数组的最后一位
        usedSize++;                 //数组个数加一
        return val;                 //直接返回当前传入值就行了
    }
    private boolean isFull(){    //栈满的条件  有效数据个数与数组长度相等
        return this.usedSize==elem.length;
    }
    public int pop(){    //出栈
        //1、栈是否为空  为空就抛出异常
        //2、栈出数据，将当前数据存给一个变量
        if(Empty()){
            throw new EmptyWrongExpection("为空");
        }
        int ret=this.elem[usedSize-1];   //usedSize-1表示的最后一个数据
        usedSize--;  //这里是栈出所以要删除 有效个数减减
        return ret;
    }
    public boolean  Empty(){  //为空条件 数据个数为零
        return this.usedSize==0;
    }
    public int peek(){   //探 栈顶元素 与栈出相近
        //1、先判断是否为空  为空抛出异常
        //2、后来在进行当前值返回即可
        if(Empty()){
            throw new EmptyWrongExpection("为空");
        }
        return this.elem[this.usedSize-1];
    }
}

1.3栈的使用

模拟实现中，已经实现了栈出（push）、栈入（pop）、和探顶（peek）、检测栈空（empty）

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

调用数据库中的函数库中的栈

1.4栈的应用场景

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1

二、队列

2.1队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头

2.2模拟实现队列

队列在库函数中是有双向链表实现的，我们这里模拟实现就用单链表来实现

public class MyQueue {    //单链表实现队列  以尾插来入队，从头开始出队
    static class  ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;   //设置一个头结点
    public ListNode tail;   //设置一个尾结点
    public int usedSize;  //计算队列的个芜湖市
    public void offer(int val){    //插入队列，尾插
        ListNode node=new ListNode(val);
        if(head==null){   //队中没有东西的时候，直接尾插，要动用头和尾
            head=tail=node;
        }else{
            tail.next=node;  //没有特殊情况下，尾巴移动构成尾插
            tail=node;
        }
        usedSize++;   //当前是单链表实现的，所以对于
    }
    public int poll(){    //出队，头结点
        if(head==null){
            return -1;
        }
        int ret=head.val;
        head=head.next;
        if(head==null){  //特殊情况，当前只有一个的时候被覆盖掉了当前head就是null然而这时候tail也与head相同了，两个域都应该被置空
            tail=null;
        }
        usedSize--;
        return ret;
    }
    public int peek(){
        if(head==null){
            return -1;
        }
        return head.val;
    }
    public boolean empty(){
       return usedSize==0;
    }
    public int getUsedSize(){
        return  usedSize;
    }
}

2.3队列的使用

模拟队列中，实现了出队列，入队列，探队列头

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

2.4循环队列

循环队列有数组构成

public class MyQueue_Elem_Second {
    private int[] elem;
    private int usedSize;

    public int front;  //开头

    public int rear;   //末尾

    public MyQueue_Elem_Second(int k){
        elem=new int[k+1];     //为什么是k+1，使用数组循环队列就到导致有一个空间是空下来的
    }
    public boolean enQueue(int value) {   //入队
        if(isFull()){
            return  false;
        }
        elem[rear]=value;   //将当前传入值给数组的末尾
        rear=(rear+1)% elem.length;   //末尾以当前这种方法是为了，能够跳过7—》0的位置，构成循环
        return true;
    }
    public boolean isFull(){
        if((rear+1)% elem.length==front){   //判满的方法也是相同，当rear的下一个就是front  满
            return true;
        }
        return false;
    }
    public boolean deQueue() {     //出队
        if(isEmpty()){
            return false;
        }
        int ret=elem[front];
        front=(front+1)% elem.length;
        return true;
    }
    public boolean isEmpty(){   //判空如何判断  rear在开始与front在相同位置，只要头与尾相同为空
        if(rear ==front){
            return true;
        }
        return false;
    }
    public int Rear(){   //找当前尾位置的时候不能直接找，可能在循环处就找不到 rear-1
        if(isEmpty()){
            return -1;
        }
        int index=(rear+1)% elem.length==0? elem.length -1:rear-1;   //避免在循环处
        return elem[index];
    }
    public int Front(){   //为什么头位置不需要像位置一样麻烦
        if(isEmpty()){
            return -1;
        }
        return elem[front];   //本身的数据可以直接取，不需要
    }
}