数据结构Queue

​ 栈和队列其实是相同的,只是名字不一样 入栈换成了入队(enqueue),出栈换成了出队(dequeue)。语义 是不同的。入队操作向队尾添加元素,而出队操作从 队首移除元素。

​ 现在,队列的链表表示中 我们需要维护两个指针引用。一个是链表中的第一个 元素,另一个是链表最后一个元素。插入的时候我们在 链表末端添加元素,而不是在链表头。移除元素的时候 不变,依然从链表头取出元素。那么这就是出队操作的实现 和栈的出栈操作的代码是一样的。保存元素,前进指针 指向下一个节点,这样就删除了第一个节点,然后返回该元素。一模一样 添加节点,或者入队操作时,向链表添加新节点。我们要把它放在链表末端 这样它就是最后一个出队的元素。首先 要做的是保存指向最后一个节点的指针,因为我们需要 将它指向下一个节点的指针从null变为新的节点。然后给 链表末端创建新的节点并对其属性赋值,将旧的指针 从null变为指向新节点。

​ 那么用数组实现呢?用可调大小的数组实现并不难 。我们维护两个指针,分别指向队列中的 第一个元素和队尾,即下一个元素要加入的地方 那么对于入队操作在tail指向的地方加入新元素,出队操作移除 head指向的元素。棘手的地方是一旦指针的位置超过了数组 的容量,必须重置指针回到0,这里需要多写一些代码 而且和栈一样实现数据结构的时候你需要加上调整容量的方法 。下面给出完整的实现。

package Queue;

/**
 * 同 Stack 我们遇到的问题就是调整队列大小的问题,以及处理碎片空间的问题
 * 调整大小我们依然使用倍增法,碎片空间就涉及到了循环队列的处理方法
 */
public class QueueArray {
    private int[] arr;
    private int head = 0;
    private int tail = 0;

    public QueueArray() {
        arr = new int[20];
    }

    private void resize(int size) {
        int[] temp = new int[size];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        arr = temp;
    }

    public boolean isEmpty() {
        return head == tail;
    }

    public void enqueue(int num) {
        if (isFull()) {
            resize(arr.length * 2);
        }
        tail = (++tail) % arr.length;
        arr[tail] = num;
    }

    public int dequeue() {
        return arr[++head % arr.length];
    }

    public boolean isFull() {
        return (tail + 1) % arr.length == head;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

c语言基础学习08_关于内存管理的复习

============================================================================= 对于...

9810
来自专栏专注 Java 基础分享

虚拟机字节码执行引擎

所谓的「虚拟机字节码执行引擎」其实就是 JVM 根据 Class 文件中给出的字节码指令,基于栈解释器的一种执行机制。通俗点来说,也就是 JVM 解析字节码指令...

26940
来自专栏java学习

Java基础总结大全(1)

一、基础知识: 1、JVM、JRE和JDK的区别: JVM(Java Virtual Machine):java虚拟机,用于保证java的跨平台的特性。 ...

448110
来自专栏java学习

Java基础总结大全(1)

一、基础知识: 1、JVM、JRE和JDK的区别: JVM(Java Virtual Machine):java虚拟机,用于保证java的跨平台的特性。 ...

37950
来自专栏liulun

Nim教程【十五】【完结】

模版 模版是Nim语言中的抽象语法树,它是一种简单的替换机制,在编译期被处理 这个特性使Nim语言可以和C语言很好的运行在一起 像调用一个方法一样调用一个模版 ...

24580
来自专栏逆向技术

C++反汇编第二讲,不同作用域下的构造和析构的识别

               C++反汇编第二讲,不同作用域下的构造和析构的识别 目录大纲:   1.全局(静态)对象的识别,(全局静态全局一样的,都是编译期间...

210100
来自专栏数据结构与算法

15:Challenge 11(主席树裸题)

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

366130
来自专栏个人分享

JVM 类型的生命周期学习

Java虚拟机通过装载、连接和初始化一个JAVA类型,使该类型可以被正在运行的JAVA程序所使用,其中,装载就是把二进制形式的JAVA类型读入JAVA虚拟机中;...

9730
来自专栏nnngu

Java面试题库及答案解析

1、面向对象编程(OOP)有哪些优点? 代码开发模块化,更易维护和修改。 代码复用。 增强代码的可靠性和灵活性。 增加代码的可理解性。 2、面向对象编程有哪些特...

35950
来自专栏magicsoar

C语言和go语言之间的交互 - C语言中使用go语言,使用的go语言又使用了c语言

一、go语言中使用C语言 go代码中使用C代码,在go语言的函数块中,以注释的方式写入C代码,然后紧跟import “C” 即可在go代码中使用C函数 ? 代码...

380100

扫码关注云+社区

领取腾讯云代金券