不良人系列-复兴数据结构（栈和队列）

这篇文章介绍了不良人系列-复兴数据结构（栈和队列），分享给大家做个参考，收藏Java资料网收获更多编程知识

 个人主页：爱编程的小新☆ 

不良人经典语录：“相呴相济 玉汝于成 勿念 心安”

目录

一. 栈(stack)

1. 栈的概念

2. 栈的常见方法

3.栈的模拟实现

 ​编辑

二. 队列

1. 队列的概念

2. 队列的使用

 2.1 队列的常见方法

2.2 队列的模拟实现

 2.3 队列的分类

(1) 普通队列

(2) 循环队列 

 (3) 双端队列

 三. 栈和队列的优缺点

1. 栈的优缺点

 2. 队列的优缺点

---

一. 栈(stack)

栈是一种重要的数据结构，接下来我们来看看什么是栈

1. 栈的概念

栈是一种只能在一端进行插入和删除操作的特殊线性表，进行数据操作的一端称作栈顶，那么在另一端则称为栈底，它采用后进先出的原则存储数据，即最后插入的数据最先被取出。

栈的基本操作：

• 入栈/压栈/进栈（push）：将新的元素插入到栈顶
• 出栈（pop）：删除栈顶元素并返回其的值
• 查看栈顶元素（peek）：返回栈顶元素但是不删除它
• 判断栈是否为空：（isEmpty）：若栈为空返回true，否则返回false
• 获取栈的大小（size）：返回栈中元素的个数

 栈在生活中的例子：

比如我们的羽毛球桶，后放进的球会先被取出（统一往球头的方向出）； 

2. 栈的常见方法

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

public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();
        //将元素放入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack);//1,2,3,4,5
        System.out.println(stack.size());//栈中有效元素个数：5
        System.out.println(stack.peek());//栈顶元素：5
        stack.pop();//5出栈
        System.out.println(stack.isEmpty());//判断栈是否为空：false
    }

3.栈的模拟实现

从下图可以看见，Stack其实是继承了Vector，Vector和ArrayList类似都是基于数组实现的容器并且是动态的顺序表，但是不同的是：Vector是线程安全的数据结构

 

 线程安全和不安全的概念：

在多线程编程中，线程安全和线程不安全是两个重要的概念（这里了解一下即可）

• 线程安全：指的是一段代码或者一个数据结构在多线程环境中被多个线程同时访问或者操作时，还是能够正确的运行，不会出现数据不一致、错误结果、程序崩溃等问题
• 线程不安全：指的是一段代码或者一个数据结构在多线程环境中被多个线程同时访问或者操作时，可能出现数据竞争、数据不一致、错误结果、程序崩溃等问题，导致程序的行为不可预测。

 Stack的模拟实现：

public class Mystacks {
    public int []elem;//使用数组模拟实现栈
    public int usedsize;//有效元素的个数

    public Mystacks() {
        this.elem=new int[10];//默认栈的初始空间为10
    }
    
    public int size(){//获取栈中有效元素的个数
        return usedsize;
    }
    
    public void push(int value){//入栈
        //在入栈前我们需要判断一下栈是否满了，如果满了则需要进行扩容
        if(isFull()){
            //扩容
            this.elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedsize++]=value;
    }
    //该方法不对用户开放，设置为private权限即可
    private boolean isFull(){
        return usedsize==elem.length;
    }
    
    public int pop(){//删除栈顶元素，并返回
        //判断栈是否为空，为空则返回-1
        if(isEmpty()){
            return -1;
        }
        int val=elem[usedsize];
        usedsize--;
        return val;
    }
    
    public boolean isEmpty(){
        return usedsize==0;
    }
    
    public int peek(){//获取栈顶元素
        if(isEmpty()){
            throw new RuntimeException("栈为空，无法获取栈顶元素");
        }
        return elem[usedsize-1];
    }
}

 那么其实不止可以使用数组来实现栈，也可以使用链表来实现栈：

链式栈：使用链表来存储数据栈数据元素，每个节点包含数据域和指向下一个节点的指针域。其优点是可灵活扩展不存在栈溢出的问题，缺点是需要而外的指针空间，实现相对复杂

二. 队列

1. 队列的概念

队列也是一种特殊的线性表，它允许在表的一端进行插入操作，而在另一端进行删除操作，允许插入的一端称为队尾，允许删除的一端称为队头，元素按照先进先出的原则存储数据

 队列的基本操作：

• 入队（offer）：将元素添加到队尾
• 出队（poll）：从队头删除元素并返回值
• 查看队头元素（peek）：返回队头元素的值，但不改变队列的状态
• 判断队列是否为空（isEmpty）：若队列为空返回true，否则返回false
• 获取队列大小（size）：返回队列中元素的个数

 队列在生活中的例子：

就像一群小朋友在排队玩滑滑梯，先排队的人先玩滑滑梯，后排队的人后玩，遵循了我们队列的原则：先进先出，后进后出

2. 队列的使用

在Java中，Queue是一个接口，底层是通过链表来实现的，所以在实例化的时候必须实例化LinkedList的对象，因为LinkedList实现了Queue接口

 2.1 队列的常见方法

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

 public static void main(String[] args) {
        Queue<Integer> queue=new LinkedList<>();
        //入队列
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        System.out.println(queue);//1,2,3,4,5
        System.out.println(queue.size());//5
        System.out.println(queue.peek());//5
        queue.poll();//出队列
        System.out.println(queue);//2,3,4,5
        System.out.println("判断队列是否为空："+queue.isEmpty());
    }

2.2 队列的模拟实现

在模拟实现队列之前我们来思考一下，是采用单向链表来实现队列好还是双向链表来实现队列好？

实际上双向链表才是最优的选择：

使用单向链表：在插入新元素的时间复杂度为O(n)，因为我们需要遍历链表来找到最后一个元素的位置，此时的效率是没有双向链表好的

使用双向链表：在插入新元素和删除元素的时间复杂度都为O(1)，可以直接通过对头指针和队尾指针进行入队和出队的操作，效率较高

public class Myqueue {
    static class ListNode{//定义一个内部类来充当我们的节点
        public int value;
        public ListNode next;//存放下一个节点的地址
        public ListNode prev;//存放前一个节点的地址

        public ListNode(int value) {
            this.value = value;
        }
    }

    public ListNode head=null;
    public ListNode last=null;
    public int usedsize=0;

    public void offer(int val){
        //创建新的节点
        ListNode node=new ListNode(val);
        //判断队列是否为空,如果为空将新节点的地址赋值给头节点的地址
        //如果不为空，将新节点添加到队尾
        if(isEmpty()){
            head=node;//头节点是该节点
            last=node;//尾节点也是该节点
        }else{
            last.next=node;//将node的地址赋值给当前尾节点的下一个节点地址
            node.prev=last;//将当前尾节点的地址赋值给node节点的前一个节点地址
            last=node;//将尾节点指向新节点
        }
        usedsize++;//有效元素个数++
    }
    public boolean isEmpty(){//判断队列为不为空
        return usedsize==0;
    }

    public int poll(){//出队
        // 1. 队列为空
        // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
        // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        int val = 0;
        if(head == null){
            return -1;
        }else if(head == last){
            last = null;
            head = null;
        }else{
            val = head.value;
            head = head.next;
            head.prev = null;
        }
        --usedsize;//将有效元素--
        return val;//返回删除的值
    }
    
    public int peek(){//获取队尾元素
        if(head==null){
            return -1;
        }
        return head.value;
    }
    
    public int size(){//获取队列中有效元素的个数
        return usedsize;
    }

}

 2.3 队列的分类

(1) 普通队列

普通队列就是队列最基本的形式，我们模拟实现的就是普通队列，普通队列遵行先进先出的原则

(2) 循环队列 

循环队列是将队列存储空间的最后一个位置绕到第一个位置，从而形成一个环，依然遵循先进先出的原则进行操作：

循环队列的好处 ：

• 相较于普通队列，解决了顺序队列（底层用数组实现的队列）中可能出现的假溢出问题，提高了存储空间的利用率
• 入队和出队的时间复杂度均为O(1)，操作效率高

 (3) 双端队列

 三. 栈和队列的优缺点

1. 栈的优缺点

栈的优点：

• 操作简单高效：入栈和出栈操作的时间复杂度均为O(1)，能快速实现数据的插入和删除，在对时间要求严格的场景中表现出色。
• 空间利用率高：只需动态分配内存来存储栈中的元素，无需预留大量额外空间，内存管理高效。

栈的缺点：

• 数据访问受限：只能访问栈顶元素，若要访问其他元素，需先将栈顶元素依次出栈，操作不便且效率低。
• 功能相对单一：主要用于数据的暂存和特定顺序的处理，在复杂数据结构和算法中，单独使用栈可能无法满足需求，需与其他数据结构配合。

 2. 队列的优缺点

队列的优点：

• 先进先出顺序保证：严格按照先进先出原则处理数据，在模拟现实世界中的排队现象、任务调度等场景中，能确保数据处理的公平性和顺序性。
• 多端操作灵活：双端队列等特殊队列结构支持在两端进行插入和删除操作，为数据处理提供了更多灵活性，可适应不同应用场景需求。

队列的缺点：

• 出队操作效率问题：在某些实现方式中，出队操作可能涉及到元素的移动或指针的调整，时间复杂度可能较高，影响整体性能。
• 空间管理复杂：在动态分配内存的队列中，频繁的入队和出队操作可能导致内存碎片产生，影响内存空间的有效利用和管理。

---

 以上就是本期栈和队列的全部内容啦，在此感谢大家的观看！！！

文章来源:https://blog.csdn.net/2402_86304740/article/details/144517002
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！