登录  /  注册
首页 > Java > java教程 > 正文

一文带你认识Java栈和队列

WBOY
发布: 2022-06-24 12:45:06
转载
1855人浏览过

本篇文章给大家带来了关于java的相关知识,其中主要整理了栈和队列的相关问题,包括了栈和队列的定义、应用、实现和操作等等内容,下面一起来看一下,希望对大家有帮助。

一文带你认识Java栈和队列

推荐学习:《java视频教程

在学习栈和队列 之前,先了解一下什么是线性表:一次保存单个同类型的元素,多个元素之间逻辑上连续,比如数组,链表,字符串,栈和队列
栈和队列其实操作受限的线性表,数组也罢,链表也罢,既可以在头部插入和删除,也能在尾部插入和删除,但是栈和队列只能在一端插入,在一端删除

一、栈

1.定义

只能在一端插入元素,也只能在这一端删除元素(栈顶),可以把栈看作一个“水杯”,只能从一端添加元素,也只能从一段删除元素,而且,先进入水杯的水在杯底,后进入水杯的水在杯顶,往出倒水的时候,也是倒出的杯顶的水,栈也是一样,先入栈的元素在栈底,后入栈的元素在栈顶,所以先入栈的元素后出,后入栈的元素先出,这也是栈的特性“先进后出,后进先出”Last In First Out(LIFO),取出元素和添加元素只能在栈顶。
将1 2 3 4 5,一次放入栈中
在这里插入图片描述

2.栈的应用

1.无处不在的undo(撤销)操作

在任何一个编辑器中输错一个内容后,使用Ctrl + z就返回到了输入的内容;
在任何一个浏览器中点击后退操作
在这里插入图片描述
都是栈的这个结构的应用
1.使用编辑器使用撤销操作,一次输入就把内容压入栈中,再输入就就再压入栈中,发现一次输入错误,就使用撤销操作,把当前栈顶的错误内容弹出,那么当前栈顶的内容就是上次输入的内容。
2.浏览网页其实也是相同原理的,就像打开百度 -> 打开csdn -> 打开创作中心,也是使用栈这个结构,先把百度网页压入栈中 ,然后csdn网页压入栈中,然后创作中心网页压入栈中,想要返回到csdn主页,按下后头箭头,就把当前栈顶的创作中心网页弹出,取出csdn主页。

2.操作系统栈

程序再执行的过程中,从A函数调用B函数,从B函数调用C函数,调用结束,返回执行时,如何得知从哪继续开始执行呢,背后也是栈这个结构

3.栈的实现

基于链表实现的栈 – 链式栈
基于数组实现的栈 – 顺序栈(使用较多)
定义一个基于动态数组实现的栈

//基于动态数组实现的顺序栈public class MyStack<e> {
    //记录当前栈的元素个数
    private int size;
    //实际存储数据的动态数组,此时在栈中只能在数组的尾部添加和删除元素
    private List<e> data = new ArrayList();
    }</e></e>
登录后复制

4.栈的操作

1.向栈中添加一个元素
只能在栈顶添加

 /**
     * 向当前栈中添加元素 -- &gt;压栈操作
     * @param val
     */
    public void push(E val){
        data.add(val);
        size++;
    }
登录后复制

2.当前从栈顶弹出一个元素

/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @return
     */
    public E pop(){
        if (isEmpty()){
            //栈为空无法弹出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //在数组末尾删除元素
        E val = data.get(size - 1);
        data.remove(size - 1);
        size --;
        return val;
    }
登录后复制

3.查看当前栈顶元素,但不弹出

/**
     * 查看当前栈顶元素值,不弹出该元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size - 1);
    }
登录后复制

二、队列

1.定义

队列:先进先出(FIFO)的数据结构i,元素只能从队尾添加到队列中,也只能从队首出队列,元素的出队顺序和入队顺序保持一致
将1 2 3 4 5依次入队
在这里插入图片描述

2.队列的应用

现实生活中,各种各样的“排队”操作

3.队列的实现

基于数组实现的队列 – 顺序队列
基于链表实现的队列 – 链式队列
出队操作只能在队列的头部进行,若采用数组实现的队列,每次出队一个元素就得搬移剩下的所有元素向前移动一个单位,此时采用链表实现的队列更适合队列的结构,删除元素只需要删除头结点,添加元素在链表的尾部添加

public interface Queue<e> {
    //入队操作
    void offer(E val);
    //出队操作
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();}</e>
登录后复制

对于栈来说队列的实现子类是比较多的,比如
FIFO队列
双端队列
循环队列
优先级队列
不管哪个队列都要实现

4.FIFO队列

1.定义一个FIFO队列

// An highlighted blockvar foo = 'bar';
登录后复制

2.向队列中添加一个元素

public void offer(E val) {
        Node<e> node = new Node(val);
        if (head == null){
            head = tail = node;
        }else{
            //链表的尾插
            tail.next = node;
            tail = node;
        }
        size++;
    }</e>
登录后复制

3.从当前队首出队一个元素

 public E poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        //头删
        E val = head.val;
        Node<e> node = head;
        head = head.next;
        node.next = node = null;
        size--;
        return val;
    }</e>
登录后复制

4.查看当前队列的队首元素

public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }
登录后复制

5.循环队列

1.定义:基本上都是使用固定长度的数组来实现,数组在实现队时,若从数组头部删除元素需要频繁的移动后面的元素,效率比较低;出队和入队操作,使用两个引用,一个head,一个tail,添加元素在数组的尾部添加,删除元素只需要移动head引用指向的地址即可(逻辑删除)
2.应用:操作系统的生产消费者模型,MySQL数据库的InnoDB存储引擎的redo日志
3.循环队列就是使用长度固定的数组来实现,数组头部就是队首(head),数组的尾部就是队尾(tail),数组[head…tail)时循环队列的有效元素
head永远指向循环队列的第一个元素
tai永远指向循环队列有效元素的后一个位置
在这里插入图片描述
此时循环队列的有效元素就为7 9 1两个元素
循环队列出队一个元素,就只用让head引用向后移动一个位置
在这里插入图片描述
此时循环队列的有效元素就只有9 和 1 两个元素了
再出队一个元素,但此时head引用已经走到末尾了,所谓循环队列就是当head或者tail引用走到数组末尾时,再向后移动就是返回数组头部的操作,循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作,当有新的元素添加到队列中就会覆盖掉原来的元素,就只需要将tail索引位置覆盖上新的元素,再让tail再向后移动

当队列为空时,head == tail

在这里插入图片描述

当队列已“满”时,head == tail

在这里插入图片描述
循环队列需要注意的关键点
1.因此当head 和 tail相等时,没法区分此时循环队列已满,还是为空,因此在循环队列中,若(tail + 1) % n == head就认为循环队列已满
在这里插入图片描述
此时循环队列就已经满了,在循环队列中就会浪费一个空间,判断队列是否已满
2.head和tail的移动不能简单的 + 1,使用取模操作,取数组长度
tail = (tail + 1) % n
head = (head + 1) % n
对数组长度取模的本质:
当head和tai走到数组最后一个索引位置时,下一次要返回数组头部,就必须用 + 1对数组长度取模
3.head == tail时,认为队列为空

6.循环队列的操作

1.定义一个循环队列

//基于整形的循环队列public class LoopQueue implements Queue<integer> {
    //定长数组
    private Integer[] data;
    //指向队首元素
    int head;
    //指向队尾元素的下一个元素
    int tail;
    public LoopQueue(int size){
        data = new Integer[size + 1];
    }}</integer>
登录后复制

2.向循环队列中添加一个元素

@Override    public void offer(Integer val) {
       if (isFull()){
           throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
       }
       data[tail] = val;
       tail = (tail + 1) % data.length;
    }
登录后复制

3.从循环队列中出队一个元素

 @Override    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }
登录后复制

4.查看当前循环队列队首元素

 @Override    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek!");
        }
        return data[head];
    }
登录后复制

5.判断当前循环队列是否为空

 @Override    public boolean isEmpty() {
        return head == tail;
    }
登录后复制

6.判断当前循环队列是否已满

 public boolean isFull(){
        return (tail + 1) % data.length == head;
    }
登录后复制

7.toString方法

public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最后一个有效元素的索引
        int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lsatIndex){
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }
登录后复制

7.双端队列

双端队列:Deque是Queue的子接口,这个队列既可以尾插,头出;也可以头插,尾出
在这里插入图片描述
双端队列的一个常用子类就是LinkedList,不管使用栈还是队列,都可以统一使用双端队列接口
1.现在需要一个栈
在这里插入图片描述
2.现在需要一个队列
在这里插入图片描述

推荐学习:《java视频教程

以上就是一文带你认识Java栈和队列的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:CSDN网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号