Java 栈与队列超详细分析讲解

目录
  • 一、栈(Stack)
    • 1、什么是栈?
    • 2、栈的常见方法
    • 3、自己实现一个栈(底层用一个数组实现)
  • 二、队列(Queue)
    • 1、什么是队列?
    • 2、队列的常见方法
    • 3、队列的实现(单链表实现)
    • 4、循环队列

一、栈(Stack)

1、什么是栈?

栈其实就是一种数据结构 - 先进后出(先入栈的数据后出来,最先入栈的数据会被压入栈底)

什么是java虚拟机栈?

java虚拟机栈只是JVM当中的一块内存,该内存一般用来存放 例如:局部变量当调用函数时,我们会为函数开辟一块内存,叫做 栈帧,在 java虚拟机栈中开辟,具体如下。

常见考点:不可能的出栈顺序

这道题该怎么分析呢?

首先我们知道,出栈时拿到的第一个元素为4,那么4必须入栈,因为入栈的顺序是 1 2 3 4 5 6,所以4要入栈,1 2 3 得先入栈。(通过后面分析得知,该出栈序列正确)

2、栈的常见方法

方法 作用
E push(E item) 放入元素
E pop() 获取栈顶元素并弹出
E peek() 获取栈顶元素
boolean isEmpty() 判断栈是否为空(父类Vector的方法)

3、自己实现一个栈(底层用一个数组实现)

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[4];
    }

    // 放入元素
    public void push(int val) {
        if(isFull()) {
            // 如果放满了,二倍扩容
            this.elem = Arrays.copyOf(elem,2 * elem.length);
        }
        this.elem[this.usedSize++] = val;
    }
    // 获取栈顶元素并弹出
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空!");
        }
        usedSize--;
        return elem[usedSize];
    }
    // 获取栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空!");
        }
        return elem[usedSize-1];
    }
    // 是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    // 是否满了
    public boolean isFull() {
        return elem.length == usedSize;
    }
}

二、队列(Queue)

1、什么是队列?

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

入队列:进行插入操作的一端称为队尾

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

2、队列的常见方法

// 普通队列
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);// 队尾入
int top = queue.peek();// 获取队头元素
queue.poll();// 弹出队尾元素并返回

// 双端队列
Deque<Integer> deque = new LinkedList<>();
deque.offer(1);// 默认队尾入
deque.offerFirst(2);// 队头入
deque.offerLast(3);// 队尾入

deque.peekFirst();// 获取队头元素
deque.peekLast();// 获取队尾元素

deque.pollFirst();// 弹出队头元素并返回
deque.pollLast();// 弹出队尾元素并返回

3、队列的实现(单链表实现)

/**
 * 每个节点
 */
class Node{
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}
public class MyQueue {
    public Node head;
    public Node tail;

    /**
     * 插入元素 -- 尾插法
     * @param val
     */
    public void offer(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            tail = node;
        }else {
            tail.next = node;
            tail = tail.next;
        }
    }

    /**
     * 出队列
     */
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空!");
        }
        int val = head.val;
        head = head.next;
        return val;
    }

    /**
     * 获取队头元素
     */
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("队列为空!");
        }
        return head.val;
    }

    // 队列是否为空
    public boolean isEmpty() {
        return head == null;
    }
}

4、循环队列

当考虑用数组来实现一个队列, 很容易想到以下结构:

当我们连续从该队头中弹出元素时,就可以发现问题了

可以看到此时数组并没有满,但是当我们再次插入元素时,队尾却插入不了了,这时候我们可以想到将该数组看成是循环的数组,结构如下。

可以看出,当 front 和 rear 相遇时,队列可能的情况有两种,要么为空,要么是满的状态。那么队列什么时候为空,什么时候是满的呢?

我们有两种方法:

1、设置usedSize 当usedSize和数组长度相等时为满,等于0 则为空。

2、设置标志位 设 flag = true,每放一个元素,将 flag 置为 false,每有一个元素出队列,则将 flag 置为 true。当 front 和 rear 相遇时,flag为 true 则是空的,反之则是满的。

public class MyCircularQueue {
    public int[] elem;
    public int front;// 队头下标
    public int rear;// 队尾下标
    boolean flag = true;// 是否为空

    public MyCircularQueue(int k) {
        elem = new int[k];
    }

    // 向循环队列插入一个元素。如果成功插入则返回真。
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
//            throw new RuntimeException("队列已满!");
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        flag = false;
        return true;
    }

    // 从循环队列中删除一个元素。如果成功删除则返回真。
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
//            throw new RuntimeException("队列为空!");
        }
        front = (front + 1) % elem.length;
        flag = true;
        return true;
    }

    // 从队首获取元素。如果队列为空,返回 -1 。
    public int Front() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException("队列为空!");
        }
        return elem[front];
    }
    // 获取队尾元素。如果队列为空,返回 -1 。
    public int Rear() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException("队列为空!");
        }
        // 如果是0下标,拿最后一个元素
        if (rear == 0) {
            return elem[elem.length-1];
        }else {
            return elem[rear - 1];
        }
    }

    // 检查循环队列是否为空。
    public boolean isEmpty() {
        if (rear == front && flag){
            return true;
        }
        return false;
    }
    // 检查循环队列是否已满。
    public boolean isFull() {
        if (rear == front && !flag){
            return true;
        }
        return false;
    }
}

到此这篇关于Java 栈与队列超详细分析讲解的文章就介绍到这了,更多相关Java 栈与队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java数据结构之栈与队列实例详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现  4,实现mystack 二,队列 1,概念  2,队列的实现  3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页.   很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的

  • java 数据结构之栈与队列

    java 数据结构之栈与队列 一:对列 队列是一种先进先出的数据结构 实现代码: package Queue; /* * 使用java构建队列,并模拟实现队列的入队和出对方法 */ public class Queue { //队列类 private int maxSize; //定义队列的长度 private int[] arrQueue; //队列 private int rear; //定义队列的尾指针 private int front; //定义队列的头指针 private int e

  • Java 栈与队列实战真题训练

    目录 1.实现循环队列 (1)数组下标实现循环 (2)区分队列的满与空 2.队列实现栈 3.栈实现队列 4.实现最小栈 1.实现循环队列 [OJ链接] 循环队列一般通过数组实现.我们需要解决几个问题. (1)数组下标实现循环 a.下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length.通俗一点,就是如果我们的数组大小为8,下标走到了7,再往后如何回到0,我们可以(index+1)%8来实现. b.下标最前再

  • Java深入了解数据结构之栈与队列的详解

    目录 一,栈 1,概念 2,栈的操作 3,栈的实现 ①入栈 ②出栈 ③获取栈顶元素 ④判断栈是否为空 4,实现mystack 二,队列 1,概念 2,队列的实现 ①入队 ②出队 ③获取队首元素 3,实现myqueue 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的

  • Java 栈与队列超详细分析讲解

    目录 一.栈(Stack) 1.什么是栈? 2.栈的常见方法 3.自己实现一个栈(底层用一个数组实现) 二.队列(Queue) 1.什么是队列? 2.队列的常见方法 3.队列的实现(单链表实现) 4.循环队列 一.栈(Stack) 1.什么是栈? 栈其实就是一种数据结构 - 先进后出(先入栈的数据后出来,最先入栈的数据会被压入栈底) 什么是java虚拟机栈? java虚拟机栈只是JVM当中的一块内存,该内存一般用来存放 例如:局部变量当调用函数时,我们会为函数开辟一块内存,叫做 栈帧,在 jav

  • Java超详细分析讲解哈希表

    目录 哈希表概念 哈希函数的构造 平均数取中法 折叠法 保留余数法 哈希冲突问题以及解决方法 开放地址法 再哈希函数法 公共溢出区法 链式地址法 哈希表的填充因子 代码实现 哈希函数 添加数据 删除数据 判断哈希表是否为空 遍历哈希表 获得哈希表已存键值对个数 哈希表概念 散列表,又称为哈希表(Hash table),采用散列技术将记录存储在一块连续的存储空间中. 在散列表中,我们通过某个函数f,使得存储位置 = f(关键字),这样我们可以不需要比较关键字就可获得需要的记录的存储位置. 散列技术

  • Java超详细分析讲解final关键字的用法

    目录 基本介绍 final细节01 final细节02 基本介绍 final 可以修饰类.属性.方法和局部变量. 在某些情况下,程序员可能有以下需求,就会使用到final: Base Sub 类 1)当不希望类被继承时,可以用final修饰. 2)当不希望父类的某个方法被子类覆盖/重写(override)时,可以用final关键字 修饰.[案例演示:访问修饰符 final 返回类型方法名] 3)当不希望类的的某个属性的值被修改,可以用final修饰.[案例演示: public final dou

  • C++超详细分析讲解内联函数

    目录 宏函数(带参数的宏)的缺点 inline修饰的函数就是内联函数 内联函数的特点 宏函数和内联函数的区别 宏函数(带参数的宏)的缺点 第一个问题:宏函数看起来像一个函数调用,但是会有隐藏一些难以发现的问题. 例如: #define FUN(x, y) (x * y) printf("%d", add(3, 3 + 2)) //3 * 3 + 2 = 11 以上情况可以通过加 “()” 解决: #define FUN(x, y) (x * y) printf("%d&quo

  • Java CopyOnWriteArrayList源码超详细分析

    目录 一.概述 二.类图 三.核心方法 1.add() 2.set() 3.remove() 4.get() 5.size() 四.总结 一.概述 CopyOnWriteArrayList是基于写时复制技术实现的,适用于读多写少场景下的线程安全的并发容器.读操作永远不会加锁,读读.读写都不会冲突,只有写写需要等待.写操作时,为了不影响其它线程的读取,它会进行一次自我复制,待数据写入完成后再替换array数组.array数组是被volatile修饰的,它被修改后可以被其他线程立刻发现. publi

  • C++ Boost Foreach超详细分析讲解

    目录 一.说明 二.示例代码 2.1 最简单的代码 2.2 使用BOOST_FOREACH与BOOST_REVERSE_FOREACH 三.BOOST_FOREACH特点和应用范围 四.遍历循环控制 一.说明 Boost.Foreach Boost.Foreach 提供了一个宏来模拟 C++11 中基于范围的 for 循环.您可以使用在 boost/foreach.hpp 中定义的宏 BOOST_FOREACH 来迭代序列而不使用迭代器.如果你的开发环境支持C++11,可以忽略Boost.For

  • Java依赖注入容器超详细全面讲解

    目录 一.依赖注入Dependency Injection 二.解析 2.1 典型的配置文件 2.2 配置文件所对应的Java类 2.3 定义解析器 三.bean工厂(根据bean定义创建bean对象) 四.DI容器(上下文) 4.1 容器接口 4.2 XML容器 五.使用DI容器 一.依赖注入Dependency Injection DI容器底层最基本的设计思路就是基于工厂模式. DI容器的核心功能:配置解析.对象创建.对象声明周期. 完整的代码:Dependency Injection. 二

  • Java数组队列及环形数组队列超详细讲解

    目录 一.队列 1.基本介绍 2.示意图 3.队列的特点 二.数组模拟队列 1.数组队列初始化 2.判断方法 3.增删改查的方法 4.注意 三.数组模拟环形队列 1.初始化 2.判断方法 3.增删改查的方法 一.队列 1.基本介绍 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头. 2.示意图 3.队列的特点 先进先出: 在队列中插入一

  • 非常适合新手学生的Java线程池超详细分析

    目录 线程池的好处 创建线程池的五种方式 缓存线程池CachedThreadPool 固定容量线程池FixedThreadPool 单个线程池SingleThreadExecutor 定时任务线程池ScheduledThreadPool ThreadPoolExecutor创建线程池(十分推荐) ThreadPoolExecutor的七个参数详解 workQueue handler 如何触发拒绝策略和线程池扩容? 线程池的好处 可以实现线程的复用,避免重新创建线程和销毁线程.创建线程和销毁线程对

  • Java超详细分析垃圾回收机制

    目录 前言 垃圾回收概述 内存溢出和内存泄漏 垃圾回收算法 标记阶段 STW(Stop-the-World) 回收阶段 标记-清除算法 复制算法 标记-压缩算法 三种算法的比较 总结 前言 在前面我们对类加载, 运行时数据区 ,执行引擎等作了详细的介绍 , 这节我们来看另一重点 : 垃圾回收. 垃圾回收概述 垃圾回收是java的招牌能力 ,极大的提高了开发效率, java是自动化的垃圾回收, 其他语言有的则需要程序员手动回收 , 那么什么是垃圾呢? 垃圾是指在运行程序中没有任何引用指向的对象,这

随机推荐