数据结构-循环队列和循环双端队列的多角度实现

2024-04-22 23:36

本文主要是介绍数据结构-循环队列和循环双端队列的多角度实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

      • 1. 循环队列的数组形式实现
      • 2. 循环队列的链表实现
      • 3. 循环双端队列的数组形式实现
      • 4. 循环双端队列的链表实现

在力扣的题面如下
在这里插入图片描述
在这里插入图片描述

1. 循环队列的数组形式实现

其实循环队列的数组形式只有下面要注意的点,只要掌握了下面的这几点,代码层面上就没有什么问题了

用数组模拟的思路跟循环单向队列是完全一致的,要记住下面的几个点

  • 1 . first 指向的是头元素的下标 , last 指向的是尾元素的下一个位置的下标
  • 2 . 在申请数组空间的时候要多申请一个空间的目的是,讲判断空与判断满的条件区分开
  • 判断空就是 first == last 判断满就是 "first的下一个" == last;
    
  • 3 . 在循环队列里面,如何++,如何–?
  • ++ : (first + 1) % len  ;  (last + 1) % len;
    
  • -- : (first - 1 + len) % len  ;  (last - 1 + len) % len
    
  • 4 . 元素的个数 size == (last - fist + len) % len;

下面是数组形式的实现代码

class MyCircularQueue {int[] elementData;int first;int last;public MyCircularQueue(int k) {elementData = new int[k + 1];}public boolean enQueue(int value) {if(isFull()){return false;}elementData[last] = value;last = (last + 1)%  elementData.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}first = (first + 1)%elementData.length;return true;}public int Front() {if(isEmpty()){return -1;}return elementData[first];}public int Rear() {if(isEmpty()){return  -1;}int index = last == 0 ? elementData.length - 1 : last -1;return elementData[index];}public boolean isEmpty() {return last == first;}public boolean isFull() {return first == (last + 1)  % elementData.length;}
}/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue obj = new MyCircularQueue(k);* boolean param_1 = obj.enQueue(value);* boolean param_2 = obj.deQueue();* int param_3 = obj.Front();* int param_4 = obj.Rear();* boolean param_5 = obj.isEmpty();* boolean param_6 = obj.isFull();*/

2. 循环队列的链表实现

鉴于单链表的尾巴节点每次都要寻找,所以为了简便,我们采用双向链表进行模拟,注意,这里我们对于链表节点的定义就是我们LinkedList中的源码形式,有空可以去看看我们LinkedList的底层源码,这里其实就是多了个size来标记我们的链表节点数量
代码实现如下


/*** 尝试用双向链表来模拟循环队列*/
public class CircleQueue {/*** 下面是根据原代码模拟的定义的节点类* @param <T>*/static class Node<T> {public T item;public Node<T> prev;public Node<T> next;public Node (Node<T> prev,T item,Node<T> next) {this.prev = prev;this.item = item;this.next = next;}}/*** 下面是所需要的基本结构*/private Node first;private Node last;private int size;private int capacity;public CircleQueue(int k) {this.size = 0;first = last = null;capacity = k;}public boolean enQueue(int value) {if(isFull()){return false;}Node<Integer> node = new Node<>(null,value,null);if(first == null && last == null){first = node;last = node;}else{last.next = node;node.prev = last;last = node;}this.size++;return true;}public boolean deQueue() {if(isEmpty()){return false;}if(last == first){last = first = null;}else{first = first.next;first.prev.next = null;first.prev.item = null;}this.size--;return true;}public int Front() {if(isEmpty()){return -1;}return (int)first.item;}public int Rear() {if(isEmpty()){return -1;}return (int)last.item;}public boolean isEmpty() {return first == null && last == null;}public boolean isFull() {return this.size == this.capacity;}
}

3. 循环双端队列的数组形式实现

用数组实现队列源码层面是我们的ArrayDeque这个类完成的,这里不再多说了,和我们的1.用数组实现循环队列是一致的

/*** 首先尝试是数组来模拟循环双端队列* 其次我们再用双向链表来尝试模拟一下循环双端队列* 用数组模拟的思路跟循环单向队列是完全一致的,要记住下面的几个点* 1 . first 指向的是头元素的下标 , last 指向的是尾元素的下一个位置的下标* 2 . 在申请数组空间的时候要多申请一个空间的目的是,讲判断空与判断满的条件区分开*     判断空就是 first == last 判断满就是 "first的下一个" == last;* 3 . 在循环队列里面,如何++,如何--?*     ++ : (first + 1) % len  ;  (last + 1) % len;*     -- : (first - 1 + len) % len  ;  (last - 1 + len) % len* 4 . size == (last - fist + len) % len;*/
class MyCircularDeque {int[] elementData;int first;int last;public MyCircularDeque(int k) {elementData = new int[k + 1];first = last = 0;}public boolean insertFront(int value) {if(isFull()){return false;}first = (first - 1 + elementData.length) % elementData.length;elementData[first] = value;return true;}public boolean insertLast(int value) {if(isFull()){return false;}elementData[last] = value;last = (last + 1) % elementData.length;return true;}public boolean deleteFront() {if(isEmpty()){return false;}first = (first + 1) % elementData.length;return true;}public boolean deleteLast() {if(isEmpty()){return false;}last = (last - 1 + elementData.length) % elementData.length;return true;}public int getFront() {if(isEmpty()){return -1;}return elementData[first];}public int getRear() {if(isEmpty()){return -1;}return elementData[(last - 1 + elementData.length) % elementData.length];}public boolean isEmpty() {return first == last;}public boolean isFull() {return (last + 1) % elementData.length == first;}
}

4. 循环双端队列的链表实现

其实就是比2.多了一个addFirst,和 removeLast
代码实现如下


/*** 下面我们尝试使用双向链表来模拟我们的循环双端队列*/
class MyCircularDequeUseLinkedList {static class Node<T> {Node<T> prev;T item;Node<T> next;public Node(Node<T> prev,T item,Node<T> next){this.prev = prev;this.item = item;this.next = next;}}private int size;private int capacity;private Node first;private Node last;public MyCircularDequeUseLinkedList(int k) {this.size = 0;last = first = null;this.capacity = k;}public boolean insertFront(int value) {if(isFull()){return false;}Node<Integer> node = new Node<>(null,value,null);if(isEmpty()){first = last = node;}else{node.next = first;first.prev = node;first = node;}size++;return true;}public boolean insertLast(int value) {if(isFull()){return false;}Node<Integer> node = new Node<>(null,value,null);if(isEmpty()){first = last = node;}else{last.next = node;node.prev = last;last = node;}size++;return true;}public boolean deleteFront() {if(isEmpty()){return false;}if(first == last){last = first = null;}else{first = first.next;first.prev.next = null;first.prev.item = null;first.prev = null;}size--;return true;}public boolean deleteLast() {if(isEmpty()){return false;}if(last == first){first = last = null;}else{last = last.prev;last.next.prev = null;last.next.item = null;last.next = null;}size--;return true;}public int getFront() {if(isEmpty()){return -1;}return (int)first.item;}public int getRear() {if(isEmpty()){return -1;}return (int)last.item;}public boolean isEmpty() {return first == null && last == null;}public boolean isFull() {return this.size == this.capacity;}
}

为什么不用单链表实现的原因其实是单链表每次想尾插都要走到最后一个位置,时间复杂度太高,有兴趣的话也可以自己模拟一下试试

这篇关于数据结构-循环队列和循环双端队列的多角度实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/927176

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P