ES6 자료구조 큐(Queue) 구현하기, 우선순위 큐 만들고, 큐 두개로 스택 만들기

큐(Queue)구현하기

큐는 선입선출(FIFO) 자료구조다. 배열을 기반으로 큐를 구현했다.

포인트는 배열이라서 shift()메서드와 push()메서드가 있어서 구현이 훨씬 편리하다는 것이다.

class Queue{
  constructor(){
    this.dataStore= [];
  }
  toString(){
    let result = "";
    for(val of this.dataStore){
      result = result + val + "\n";
    }
    return result;
  }
  enqueue(element){
    this.dataStore.push(element);
  }
  dequeue(){
    return this.dataStore.shift();
  }
  front(){
    return this.dataStore[0];
  }
  back(){
    return this.dataStore[this.dataStore.length-1];
  }
  empty(){
    if(this.dataStore.length == 0){
      return true;
    }
    else{
      return false;
    }
  }
}
const q = new Queue();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.enqueue(4);
console.log(q.toString());//1,2,3,4
q.dequeue();//1
q.dequeue();//2
console.log(q.toString());//3,4

우선 순위 큐

환자 class를 만들고 심각도에 따라 code를 정해 먼저 우선순위를 받는 큐를 만들었다.

code는 숫자형태로 작은 숫자일수록 먼저 치료를 받아야하는 설계라고 가정한다.

class Queue{
  constructor(){
    this.dataStore= [];
  }
  toString(){
    let result = "";
    for(idx in this.dataStore){
      result += this.dataStore[idx].code + "," +this.dataStore[idx].name+"\n";
    }
    return result;
  }
  enqueue(element){
    this.dataStore.push(element);
  }
  //우선순위는 code값이 가장 작은 것이 높음.
  dequeue(){
    let entry = 0;
    for(idx in this.dataStore){
      if(this.dataStore[idx].code < this.dataStore[entry].code){
        entry = idx;
      }
    }
    return this.dataStore.splice(entry,1);
  }
  front(){
    return this.dataStore[0];
  }
  back(){
    return this.dataStore[this.dataStore.length-1];
  }
  empty(){
    if(this.dataStore.length == 0){
      return true;
    }
    else{
      return false;
    }
  }
}
class Patient{
  constructor(name, code){
    this.name = name;
    //환자 code를 보고 우선순위를 정함.
    this.code = code;
  }
}
const q = new Queue();
const a = new Patient("jeong",4);
q.enqueue(a);
const b = new Patient("blue",3);
q.enqueue(b);
const c = new Patient("black",5);
q.enqueue(c);
const d = new Patient("red",1);
q.enqueue(d);
console.log(q.toString());
console.log(q.dequeue());//red
console.log(q.toString());
console.log(q.dequeue());//blue
 
 
 

큐 두개로 스택 구현하기

class Queue{
  constructor(){
    this.dataStore= [];
  }
  toString(){
    let result = "";
    for(idx in this.dataStore){
      result = result + this.dataStore[idx] +"\n";
    }
    return result;
  } 
  get length(){
    return this.dataStore.length;
  }
  enqueue(element){
    this.dataStore.push(element);
  }
  dequeue(){
    return this.dataStore.shift();
  }
  peek(){
    console.log(this.dataStore[0]);
  }
  front(){
    return this.dataStore[0];
  }
  back(){
    return this.dataStore[this.dataStore.length-1];
  }
  empty(){
    if(this.dataStore.length == 0){
      return true;
    }
    else{
      return false;
    }
  }
}
class Stack{
  constructor(){
    this.queue1 = new Queue();
    this.queue2 = new Queue();
  }
  push(element){
    if(this.queue1.empty()){
      this.queue1.enqueue(element);
    }
    else{
      while(!this.queue1.empty()){
         this.queue2.enqueue(this.queue1.dequeue());
      }
      this.queue1.enqueue(element);
      while(!this.queue2.empty()){
        this.queue1.enqueue(this.queue2.dequeue());
      }
    }
  }
  pop(){
    return this.queue1.dequeue();
  }
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack.pop());//4
console.log(stack.pop());//3
console.log(stack.pop());//2
console.log(stack.pop());//1

큐 두개로 스택을 구현하는 방법은 여러가지지만 위의 예제는 메인큐와 서브큐로 나눠 구현하는 방법이다.

메인큐가 비어있을 때는 그냥 element를 넣으면 되고 다음 element가 들어올 때는 메인큐에 있는 모든 element를 서브큐로 옮긴다.

그 후에 비어있는 메인큐에 가장 최근에 들어온 element를 넣고 다시 서브큐에있는 모든 요소를 차례로 메인큐에 넣는 방법이다.

그렇게하면 pop()메서드에서는 단순하게 메인큐에서 dequeue()를 하면 자동적으로 LIFO구조로 출력한다.

* 참고로 2개의 큐로 스택을 구현하는 부분중 push()메서드에서 while문 대신 for문으로 작성했었다.

그런데 멍청하게 for(let i = 0; this.queue1.length; i++){...} 이렇게 작성했다.

잘 생각해보니 dequeue()하면서 length가 줄어드니까 그것이 반영되서 알고리즘대로 작동하지 않았던 것이다. 

참고 도서 : DataStructures and Algorithms with javascript