栈与队列理解-阿里云开发者社区

栈与队列理解

2024-05-09 13

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 栈与队列理解

🙋 栈的概念

栈其实本质就是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的元素要遵循后进先出，先进后出的原则。

👇 栈的实现（顺序表实现）

👉判断栈是否为空

public class Mystack {
    private int[] array = new int[50];
    private int size = 0;
    //判断是否为空
    public boolean isEmpty(){
        return size==0;
    }
}

👉 返回栈的长度

public class Mystack {
    private int[] array = new int[50];
    private int size = 0;
    public int size(){
        return size;
    }
}

✨进栈

public class Mystack {
      private int[] array = new int[50];
      private int size = 0;
      //进栈
    public void push(int val){
        array[size]=val;
        size++;
    }
}

✨出栈

public class Mystack {
      private int[] array = new int[50];
      private int size = 0;
    //出栈
    public int  pop(){
        if (!isEmpty()){
            int temp = array[size];
            size--;
            return temp; 
        }else {
           throw new RuntimeException("空栈");
        }
    }
}

⭐️获取栈顶元素

public class Mystack {
      private int[] array = new int[50];
      private int size = 0;
    //获取栈顶元素
      public int peek(){
        if (!isEmpty()){
            return array[size-1];
        }else{
           throw new RuntimeException("空栈");
        }
    }
}

🙋队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出.

入队列：进行插入操作的一端称为队尾（Tail/Rear）

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

👇 队列的实现(链表实现)

队列中的判断是否为空与获取队列的长度是与栈一样的，这里就不在进行重复的书写

✨入队列

class node{
    public node next;
    public int val;
    public node(int val){
        this.val=val;
    }
}
public class Myqueue {
    public node head;
    private node tail;
    private int size;
    //判断是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    //获取队列的长度
    public int size(){
        return size;
    }
    //入队列
    public void enquene(int val){
        node cur = new node(val);
        if (head==null){
            head=cur;
        }else{
            tail.next=cur;
        }
        tail=cur;
        size++;
    }
}

✨出队列

    //出队列
    public int dequene(){
        if (size==0){
            throw new RuntimeException("空队列");
        }
        node oldhead = head;
        head=head.next;
        if(head==null){
            tail=null;//如果头结点为空，那么尾节点也是不能有任何指向的
        }
        size--;
        return oldhead.val;
    }

⭐️获取队列头元素

 //获取队列头元素
    public int peek(){
        if (size==0){
            throw new RuntimeException("空队列");
        }
        return head.val;
    }

🌱 总结

无论是栈还是队列，其实主要就是要掌握它们底层的数据结构，链表以及顺序表才是关键。另外这些知识基本的原理，下一步预计就是得去刷些栈与队列的习题进行巩固。