salesforce零基础学习(七十七)队列的实现以及应用

 队列和栈简单的区别为栈是后进先出,队列是先进先出。队列也是特殊的线性表,所以队列也分为顺序存储结构和链式存储结构。本篇主要描述顺序存储结构。

我们先假定一个队列里有5个元素,当我们添加新元素时,添加到队列的最后一个位置,所以时间复杂度为O(1),当我们弹出元素时,需要将队列头部的元素弹出,并将后面的元素整体向前面平移,所以时间复杂度为O(n)。如果频繁的弹出,并且后面的元素向前面平移,这样对于性能还是影响挺大的,所以我们可以增加头指针,尾指针,不要求第一个元素必须在index为0的位置,只需要用头指针记录当前的头在哪里就好。

一.环形队列:

使用两个指针操作步骤为:

1.当在队尾添加元素情况下,队尾的指针+1,如下图,队列中添加a1,a2,a3,a4四个元素。此时队首front指针指向0,队尾rear指针指向4;

2.将队首元素进行弹出,此时队首指针front指向1,队尾指向4;

3.将元素a5添加到队尾,此时队尾指针指向到了内存长度的外面,但是下标为0还是有空缺的地方,这种情况称为假溢出。

为了避免假溢出这种情况,我们的做法为当队列满了以后,从头开始继续存储队列,直到队列满,即上图的情况下,a5进入队列以后,队尾rear指针指向下标0.

此时针对队列的空或者满的判断,可以通过队首指针和队尾指针来判断:

1.判断队列为空的条件为:front = rear,即首指针等于尾指针;

2.因为队尾可以从头开始,所以rear可以大于front,也有可能rear小于front。当队列满时,我们修改其条件保留一个元素空间。也就是说,队列满时,数组中还有一个空闲单元。这样我们可以通过下面的表达式来判断队列已满:(rear+1) % QueueSize = front.上图中当添加完a5以后,队列中只剩下一个空闲单元我们就假定此队列已满。

3.获取当前队列的元素个数:(rear - front + QueueSize)% QueueSize

二.代码实现

代码中封装了实现队列的基本方法,判断队列是否为空,是否是满的队列,添加元素,弹出元素等。其中针对添加元素,需要考虑队列是否已经满的情况,对于弹出元素,需要考虑队列是否为空队列的情况。

 1 public with sharing class Queue {
 2     //数据集
 3     private Object[] datas{get;set;}
 4     //栈最大容量
 5     private Integer maxSize{get;set;}
 6     //队头的位置指针
 7     private Integer front{get;set;}
 8     //队尾的位置指针
 9     private Integer rear{get;set;}
10 
11     public Queue() {
12         this(10);
13     }
14 
15     public Queue(Integer queueSize) {
16         datas = new Object[queueSize];
17         maxSize = queueSize;
18         front = 0;
19         rear = 0;
20     }
21 
22     //添加元素到队列尾部,如果添加成功返回true,添加失败返回false
23     public Boolean add(Object obj) {
24         if(datas == null) {
25             throw new QueueException('队列未初始化');
26         }
27         if(full()) {
28             throw new QueueException('队列已满');
29         }
30         datas[rear] = obj;
31         rear = Math.mod(rear + 1, maxSize);
32         //队列
33         return true;
34     }
35 
36     //返回队列头的元素,不弹出头元素
37     public Object peek() {
38         if(datas == null) {
39             throw new QueueException('队列未初始化');
40         }
41         return datas[front];
42     }
43 
44     //弹出头元素
45     public Object poll() {
46         if(datas == null) {
47             throw new QueueException('队列未初始化');
48         }
49 
50         if(empty()) {
51             throw new QueueException('队列为空!');
52         }
53 
54         Object returnObj = datas[front];
55         datas[front] = null;
56         front = Math.mod((front + 1),maxSize);
57         return returnObj;
58     }
59 
60     public Boolean empty() {
61         return front == rear;
62     }
63 
64     public Boolean full() {
65         return front == Math.mod(rear + 1, maxSize);
66     }
67 
68     public Integer size() {
69         return Math.mod(rear - front + maxSize ,maxSize);
70     }
71 
72     override public String toString() {
73         List<Object> objList = new List<Object>();
74         Integer tempRear;
75         if(rear < front) {
76             tempRear = rear + maxSize;
77         } else {
78             tempRear = rear;
79         }
80         for(Integer i = front;i<=tempRear;i++) {
81             if(datas[Math.mod(i, maxSize)] != null) {
82                 objList.add(datas[Math.mod(i, maxSize)]);
83             }
84         }
85         return String.join(objList, ',');
86     }
87 
88 
89     public class QueueException extends Exception{
90 
91     }
92 }

三.测试举例:

1.队列超出内存情况:初始化一个长度为5的队列,因为队列满的时候,会空出一个元素空间,所以说实际可以添加进队列的长度为4,当添加eee的时候会报错,因为队列已满。

Queue q = new Queue(5);
q.add('aaa');
q.add('bbb');
q.add('ccc');
q.add('ddd');
q.add('eee');
System.debug(LoggingLevel.INFO, '*** q: ' + q);

2.正常使用添加弹出效果,每次弹出是弹出队首指针对应的元素

Queue q = new Queue(5);
q.add('aaa');
q.add('bbb');
q.add('ccc');
q.add('ddd');
String result = (String)q.poll();
System.debug(LoggingLevel.INFO, '*** result: ' + result);
System.debug(LoggingLevel.INFO, '*** : ' + 'aaa'.equals(result));
q.add('eee');
System.debug(LoggingLevel.INFO, '*** q: ' + q);

总结:环形队列适用于已经知道需要分配多大内存的情况,如果不知道需要分配多少内存的情况,可以使用队列的链形结构。队列在程序中经常使用,比如场景为排队等的场景,如果有此种先进先出的场景,优先选择队列来实现。此篇只是简单的构造一下队列的模型,很多地方需要完善,有需要或者感兴趣的自行完善一下。篇中有错误的地方欢迎指出,有问题欢迎留言。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏架构说

Leetcode 200 Number of Islands 岛的个数

1. 遍历每一个结点,如果某结点是陆地且未访问过,岛数目加1,修改未访问标志位,然后把该点放入队列中,以备扩展岛屿使用,进入2 2. 队列不为空时,取出点,然...

29630
来自专栏androidBlog

Android 常用正则表达式

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/de...

25510
来自专栏Python小屋

Python函数中单独一个星号或斜线作为形参的含义

在函数定义时,位于*parameter或单独一个星号*之后的所有参数都只能以关键参数的形式进行传值,不接收其他任何形式的传值。 >>> def demo(a, ...

39260
来自专栏Java技术栈

JDK8新特性之Stream流

是什么是Stream流 java.util.stream.Stream Stream流和传统的IO流,它们都叫流,却是两个完全不一样的概念和东西。 流可以简单的...

30360
来自专栏calvin

【nodejs】让nodejs像后端mvc框架(asp.net mvc)一样处理请求--参数自动映射篇(6/8)

路由、action的扫描、发现、注册搞定之后,后来我发现在我们的action里面获取参数往往都是通过request对象来一个一个获取。同样的一行代码我们不厌其烦...

12420
来自专栏技术专栏

彻底搞懂jdk动态代理并自己动手写一个动态代理

我们都知道牛逼轰轰的Spring AOP的实现的一种方式是使用JDK的动态代理(另一种是cglib,后面会介绍),大部分人也会用jdk的动态代理,不过没有研究过...

25920
来自专栏绿巨人专栏

TypeScript中的怪语法

12630
来自专栏ACM算法日常

UVA11988:悲剧文本(模拟链表)

You’re typing a long text with a broken keyboard. Well it’s not so badly broken....

9110
来自专栏海纳周报

synchronized关键字的语义

上一篇文章,我们讲到,如果发生了多个线程共同访问一个全局变量的时候,就会发生各种意料之外的情况。其实现实生活中有很多这样的例子。我举一个例子。 一群人都要过河,...

38270
来自专栏听雨堂

获得定长字符串

        C#中的字符串是Unicode编码,length是Unicode的Char的个数。所以,假如一个字符串中中英文混杂,又想获得一个固定宽度的字符串...

25160

扫码关注云+社区

领取腾讯云代金券