当前位置:网站首页>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('') === ''
原网站

版权声明
本文为[Xiaaoke]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/178/202206270914371350.html