数据结构之队列
特殊的线性表,只允许在表的前端删除,表的后端插入(先进先出)
设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
- MyCircularQueue(k): 构造器,设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空,返回 -1 。
- Rear: 获取队尾元素。如果队列为空,返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
示例:
MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false,队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
提示:
所有的值都在 0 至 1000 的范围内;
操作数将在 1 至 1000 的范围内;
请不要使用内置的队列库。
注意添加数据时队尾指针要求余this.max,获取队尾数据时要队尾指针减一,并且如果指针减一小于0,即为数组最后一位
export default class MyCircularQueue {
constructor (k) {
// 保存数据长度为k的数据结构
this.list=Array(k)
// 队首的指针
this.front=0
// 队尾的指针
this.rear=0
// 队列的长度
this.max=k
}
enQueue (num) {
if(this.isFull()){
return false
}else{
this.list[this.rear]=num
this.rear=(this.rear+1)%this.max
return true
}
}
deQueue () {
let v=this.list[this.front]
this.list[this.front]=''
this.front=(this.front+1)%this.max
return v
}
isEmpty () {
return this.front===this.rear&&!this.list[this.front]
}
isFull () {
return this.front===this.rear&&!!this.list[this.front]
}
Front () {
return this.list[this.front]
}
Rear () {
let rear=this.rear-1
return this.list[rear<0?this.max-1:rear]
}
}
class MycircularQueue{
constructor(len){
this.list=new Array(len);
this.front=0;
this.rear=0;
this.max=len;
}
Front(){
return this.list.length?this.list(this.front):-1;
}
Rear(){
let rear=this.rear-1;
return this.list[rear<0?this.max-1:rear]
}
enQueue(value){
if(this.isFull()){
return false;
}else{
this.list[this.rear]=value;
this.rear=(this.rear+1)%this.max;
return true;
}
}
deQueue(){
if(this.list.length>0){
this.list[this.front]="";
this.front++;
return true;
}else{
return false;
}
}
isEmpty(){
return this.front===this.rear&&!this.list[this.front]
}
isFull(){
return this.front===this.rear&&this.list[this.front]
}
}
任务调度器
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。
然而,两个相同种类的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 1:
输入: tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2
输出: 8
执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
注:
任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。
任务多的优先执行即可
export default (tasks, n) => {
let q = ''
let Q = {}
// 每种任务的数量
tasks.forEach(item => {
if (Q[item]) {
Q[item]++
} else {
Q[item] = 1
}
})
while (1) {
let keys = Object.keys(Q)
if (!keys[0]) {
break
}
// n+1为一组
let tmp = []
for (let i = 0; i <= n; i++) {
let max = 0
let key
let pos
// 从所有的任务中找到未处理数最大的,优先安排
keys.forEach((item, idx) => {
if (Q[item] > max) {
max = Q[item]
key = item
pos = idx
}
})
if (key) {
tmp.push(key)
keys.splice(pos, 1)
Q[key]--;
if (Q[key] < 1) {
delete Q[key]
}
} else {
break
}
}
q += tmp.join('').padEnd(n + 1, '-')
}
// A--A--A--
q = q.replace(/-+$/g, '')
return q.length
}