当前位置:网站首页>Queue, two-way queue, and its application
Queue, two-way queue, and its application
2022-06-27 10:17:00 【Xiaaoke】
queue
characteristic : fifo FIFO ( similar , line up )
/** * queue * characteristic : fifo FIFO ( similar , line up ) * * enqueue(element(s)): Add one or more new items to the end of the queue * dequeue: Remove the first item from the queue , And return the * peek: Returns the first element in the queue * isEmpty: Determine whether it is null * size: Returns the length of the elements in the stack * clear: Clear the elements in the stack * toString: Array toString Method * * @class Queue */
class Queue{
constructor(){
this._count = 0;
this._lowestCount = 0;
this._items = {
};
}
isEmpty(){
return this._count - this._lowestCount === 0;
}
enqueue(...elem){
for(let i = 0; i < elem.length; i++){
this._items[this._count] = elem[i];
this._count ++;
}
}
dequeue(){
if(this.isEmpty()){
return undefined;
}
const result = this._items[this._lowestCount];
delete this._items[this._lowestCount];
this._lowestCount ++;
return result;
}
peek(){
if(this.isEmpty()){
return undefined;
}
return this._items[this._lowestCount];
}
size(){
return this._count - this._lowestCount;
}
clear(){
this._items = {
};
this._count = 0;
this._lowestCount = 0;
}
toString(){
if(this.isEmpty()){
return '';
}
let objString = `${
this._items[this._lowestCount]}`;
for(let i = this._lowestCount + 1; i < this._count; i++ )
objString = `${
objString},${
this._items[i]}`;
return objString;
}
}
// test
const queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('Joho');
queue.enqueue('Jack');
console.log(queue.toString()); // Joho,Jack
queue.enqueue('Camila');
console.log(queue.size()); // 3
console.log(queue.toString()); // Joho,Jack,Camila
console.log(queue.isEmpty()); // false
queue.dequeue();
queue.dequeue();
console.log(queue.toString()); // Camila
queue.enqueue('Joho','Joho','Camila');
console.log(queue.toString());
console.log(queue);
Queue application ( Beat the drum to spread the flowers )
// Beat the drum to spread the flowers
const hotPotato = (elementList, num) => {
const queue = new Queue();
const elimitatedList = [];
for(let i = 0; i < elementList.length; i++){
queue.enqueue(elementList[i]);
}
while(queue.size() > 1){
for(let i = 0; i < num; i++){
queue.enqueue(queue.dequeue());
}
elimitatedList.push(queue.dequeue());
}
return {
elimitated: elimitatedList,
winner: queue.dequeue()
}
}
const names = ['zhangsan', 'lisi', 'wangwu', 'zhaoliu'];
const result = hotPotato(names, 6);
result.elimitated.forEach(name => {
console.log(`${
name} It was eliminated in the drumming and flower passing `)
})
console.log(` The winner :${
result.winner}`)
The bidirectional queue
A combination of stacks and queues
/** * addFront: Add elements to the front of the queue * addBack: Add elements to the back end of the queue * removeFront: The front end of the queue removes the element * peekBack: The queue back end removes the element * isEmpty: Determine whether it is null * size: Returns the length of the elements in the stack * clear: Clear the elements in the stack * toString: Array toString Method * * @class Deque */
class Deque{
constructor(){
this._count = 0;
this._lowestCount = 0;
this._items = {
};
}
addFront(elem){
if(this.isEmpty()){
this.addBack(elem);
}else if(this._lowestCount > 0){
this._lowestCount --;
this._items[this._lowestCount] = elem;
}else {
for(let i = this._count; i > 0; i--){
this._items[i] = this._items[i-1];
}
this._count++;
this._lowestCount = 0;
this._items[0] = elem;
}
}
addBack(...elem){
for(let i = 0; i < elem.length; i++){
this._items[this._count] = elem[i];
this._count ++;
}
}
removeFront(){
if(this.isEmpty()){
return undefined;
}
const result = this._items[this._lowestCount];
delete this._items[this._lowestCount];
this._lowestCount ++;
return result;
}
removeBack(){
if(this.isEmpty()){
return undefined;
}
this._count --;
const result = this._items[this._count];
delete this._items[this._count];
return result;
}
peekFront(){
if(this.isEmpty()){
return undefined;
}
return this._items[this._lowestCount];
}
peekBack(){
if(this.isEmpty()){
return undefined;
}
return this._items[this._count - 1];
}
isEmpty(){
return this._count - this._lowestCount === 0;
}
size(){
return this._count - this._lowestCount;
}
clear(){
this._items = {
};
this._count = 0;
this._lowestCount = 0;
}
toString(){
if(this.isEmpty()){
return '';
}
let objString = `${
this._items[this._lowestCount]}`;
for(let i = this._lowestCount + 1; i < this._count; i++ )
objString = `${
objString},${
this._items[i]}`;
return objString;
}
}
const deque = new Deque();
console.log(deque.isEmpty()); // true
deque.addBack('john');
deque.addBack('jack');
console.log(deque.toString()); // john,jack
deque.addBack('camila');
console.log(deque.toString()); // john,jack,camila
console.log(deque.size()); // 3
console.log(deque.isEmpty()); // false
deque.removeFront();
console.log(deque.toString()); // jack,camila
deque.addFront('john');
console.log(deque.toString()); // john,jack,camila
Two way queue application ( Palindrome checker )
// Palindrome checker
const palindromeChecker = (aString) => {
if(aString === undefined || aString === null || (aString !== null && aString.length === 0)){
return false;
}
const deque = new Deque();
const lowerString = aString.toLocaleLowerCase().split(' ').join('');
let isEqual = true;
let fistChar, lastChat;
for(let i = 0; i < lowerString.length; i++){
deque.addBack(lowerString.charAt(i));
}
while(deque.size() > 1 && isEqual){
fistChar = deque.removeFront();
lastChat = deque.removeBack();
if(fistChar !== lastChat){
isEqual = false;
}
}
return isEqual;
}
console.log('a', palindromeChecker('a'))
console.log('abc', palindromeChecker('abc'))
console.log('aba', palindromeChecker('aba'))
// ''.split('').reverse().join('') === ''
边栏推荐
- 技术与业务同等重要,偏向任何一方都是错误
- 以后发现漏洞,禁止告诉中国!
- 上周热点回顾(6.20-6.26)
- leetcode:522. Longest special sequence II [greed + subsequence judgment]
- C language learning day_ 04
- On June 23, the video address of station B in the third episode of rust chat room
- Basic violin plot in R with plot
- C language learning day_ 06
- Mongodb cross host database copy and common commands
- Analysis of mobile ar implementation based on edge computing (Part 2)
猜你喜欢
2-4Kali下安装nessus
【HCIE-RS复习思维导图】- STP
2-4 installation of Nessus under Kali
[registration] infrastructure design: from architecture hot issues to industry changes | tf63
[200 opencv routines] 211 Draw vertical rectangle
以后发现漏洞,禁止告诉中国!
leetcode:522. 最长特殊序列 II【贪心 + 子序列判断】
你睡觉时大脑真在自动学习!首个人体实验证据来了:加速1-4倍重放,深度睡眠阶段效果最好...
Bluetooth health management device based on stm32
Error im002 when Oracle connects to MySQL
随机推荐
[从零开始学习FPGA编程-47]:视野篇 - 第三代半导体技术现状与发展趋势
Installation manuelle de MySQL par UBUNTU
详解各种光学仪器成像原理
导师邀请你继续跟他读博,你会不会立马答应?
2-4Kali下安装nessus
JS client storage
【TcaplusDB知识库】Tmonitor后台一键安装介绍(一)
R語言plotly可視化:可視化多個數據集歸一化直方圖(historgram)並在直方圖中添加密度曲線kde、設置不同的直方圖使用不同的分箱大小(bin size)、在直方圖的底部邊緣添加邊緣軸須圖
When does the mobile phone video roll off?
Technology is as important as business. It is wrong to favor either side
Mongodb cross host database copy and common commands
前馈-反馈控制系统设计(过程控制课程设计matlab/simulink)
Dimitt's law
【HCIE-RS复习思维导图】- STP
C语言学习-Day_05
C language learning day_ 04
Stop using system Currenttimemillis() takes too long to count. It's too low. Stopwatch is easy to use!
Basic violin plot in R with plot
Decompile the jar package and recompile it into a jar package after modification
【TcaplusDB知识库】Tmonitor后台一键安装介绍(二)