首先，题目都是出自leetcode的探索里的初级算法的课程。
嘿嘿，有心想学的请自行前往学习，光看是没用的。
队列：先入先出的数据结构
show code
// "static void main" must be defined in a public class.
// java的入口函数 static void main 必须定义在一个public类里
// 队列实体
class MyQueue {
// store elements
// 存储队列内容的List
private List<Integer> data;
// a pointer to indicate the start position
// 指向头结点的标识
private int p_start;
// 队列实体的构造函数，初始化list和p_start
public MyQueue() {
data = new ArrayList<Integer>();
p_start = 0;
}
/** Insert an element into the queue. Return true if the operation is successful. */
// 类中方法，添加一个元素。添加方法:data.add()，list的add方法向数组后面添加一个元素
public boolean enQueue(int x) {
data.add(x);
return true;
};
/** Delete an element from the queue. Return true if the operation is successful. */
// 移除一个元素
// 首先通过isEmpty()方法，如果首元素大于等于list长度，判断队列为空
// 对于队列，p_start指向队尾元素时=length-1，当最后一个元素出列，p_start=length。>=为一种保险的写法，我并未想出>的情景
// 如果队列非空，p_start自加。
// 这里有个问题，list并未移除任何元素。以p_start元素判断队列是否清空。
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
// 是否可以在这里加入list的移除
// list.remove(p_start);
p_start++;
return true;
}
/** Get the front item from the queue. */
// 获取队列的首元素
public int Front() {
return data.get(p_start);
}
/** Checks whether the queue is empty or not. */
// 判断队列是否为空
public boolean isEmpty() {
return p_start >= data.size();
}
};
public class Main {
public static void main(String[] args) {
// 初始化队列
MyQueue q = new MyQueue();
q.enQueue(5);
q.enQueue(3);
// 队列不为空，输出首元素,这里应该输出5
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
// 移除5
q.deQueue();
// 输出3
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
// 移除3
q.deQueue();
// if(false)
// p_start = 2
// data => [5,3]
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
}
}
由此引出一个更高效的算法——循环队列。
// 循环队列——使用固定大小的数组和两个指针来指示起始位置和结束位置。目的是重用我们之前提到的被浪费的存储。
// 思路：首先关键点有：
// 1、front和rear指针移动
// 问题：对于指定长度的数组，当我们的下标移动的时候必然会遇到下标越界，此时理论上讲超过数组范围的下标应该移动到0号索引处
// 解决方法：进行移动的时候,（front + 1） % queue.length就可获得正确的下标，rear同理
// 2、队空与队满的判断（思路是使用一个实际存储长度标识 size来参考判断）
// 因为我们用size做判断符号且数组长度加一以防止下标指向空指针
// 所以判空 size == 0；判满 size == length - 1。
// 3、入队和出队操作
// 入队操作
// 入队-》判断队满-》入参赋值-》rear后移-》size++
// 出队操作
// 出队-》判断队空-》front后移-》size--
// 4、返回队首和队尾索引
// 队首很简单：queue[front] 也可以 front == rear
// 队尾很奇怪： queue[rear]会在某些情况下失效，举个栗子：[1,2,3,null],length = 4,front = 0,rear = 3,size = 3,此时的rear-1;[1,2,3,4],length = 3,front = 1,rear = 0,size = 3,此时的rear - 1 = -1,显然是不行的，此时队尾应该是4，所以使用（rear-1 + length） % length;
class MyCircularQueue {
private int [] queue;
private int front;
private int rear;
// 记录实际队列长度的数值
private int size;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
queue = new int [k + 1];
front = 0;
rear = 0;
size = 0;
}
/** Insert an element into the cir3W2WXcular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
// 尾元素进1，如果超出数组长度，取mod（求余）
queue[rear] = value;
rear = (rear + 1) % queue.length;
size++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty()) {
return false;
}
// front移动，可不变更
front = (front + 1) % queue.length;
size--;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (isEmpty()) return -1;
return queue[front];
}
/** Get the last item from the queue. */
public int Rear() {
if (isEmpty()) return -1;
return queue[(rear - 1 + queue.length) % queue.length];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return size == 0;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return size == queue.length - 1;
}
}
应用：
题目（数据流中的移动平均值）：
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。
测试用例：
MovingAverage m = new MovingAverage(3); // size = 3
m.next(1) // 1 [1] average = 1/1
m.next(10) // (1 + 10) / 2 [1,10] average = (1+10)/2
m.next(3) // (1 + 10 + 3) / 3 [1,10,3] average = (1+10+3)/2
m.next(5) // (10 + 3 + 5) / 3 [10,3,5] average = (10+3+5)/2
若依次得到测定值(X1,X2,X3,...,Xn)时，按顺序取一定个数所做的全部算术平均值。 例如(X1+X2+X3)/3,(X2+X3+X4)/3,(X3+X4+X5)/3,(X4+X5+X6)/3...等是移动平均值。
// 刚开始看这道题的时候，我去，我题目都没看懂。。。
// 后来百度了下移动平均数,然后又找了个题解看了下实现过程
class MovingAverage {
// 这是初始化的窗口大小
int size = 0;
// 申明一个队列，使用LinkedList初始化，这是collection中的队列
Queue<Integer> queue;
// 使用sum提前记录总数，方便取平均数
// 注意这里最好定义为double类型，如果是整数不注意就会精度丢失
double sum = 0;
/** Initialize your data structure here. */
public MovingAverage(int size) {
this.size = size;
// 初始化队列
queue = new LinkedList<>();
}
public double next(int val) {
// 入队
queue.offer(val);
// 求和
sum += val;
// 如果超出屏幕
if (queue.size() > size) {
Integer head = queue.poll();
sum -= head;
}
// 如果queue小于size ，取queue的长度
return sum / queue.size();
}
}
面对过现实才知道自己多渺小
我毕业也半年了，一个专升本文凭又因为自己的胆怯、随遇而安的性格错过了校招，进了学长的一个公司。忙忙碌碌、松松垮垮，经历了一个多月的高强度加班，也经历了松懈的下班玩游戏、看小说、上班划水。慢慢的自己也感觉到着急，回顾了自己的所学：android半吊子（垃圾码农水准）、java半吊子（码农水准）、vue半吊子（垃圾码农水准）、flutter初学者（码农都算不上）。毕业一个月的时候，隔三差五的突然想学些什么，学了个把天又置之脑后。我的自制力本来垃圾，又没一个目标，浑浑噩噩下来一事无成。我不想这样直到我失去冲劲、失去追求前进的力气。我现在在这定个目标：以java工程师的身份进到阿里，或许这是个永远吃不到的萝卜，至少我有了明确的前进目标。——2020-3-12（感觉我心理这个日期已经出问题了。。。）
后面如果有实际使用队列的情景就加载下方——2020-3-12
我突然发现我之前的内心好像出问题了，我完全不用这么纠结，以进某厂为目标有什么意思？在写CRUD的路上，我觉得最求技术就行，了解感兴趣的技术，了解想知道的知识，追求完成作品的乐趣，他不香么？结果不是必然，探索永无止境。——2020-3-31
