[JavaScript] Queue - Linear Queue(선형 큐)

Queue의 개념

  큐는 FIFO(Frist In First Out)의 특징을 가지고 있다. 우리나라 말로 선입선출이라고 한다. 예를 들어 마트, 편의점 또는 가게 등에서 처음 들어온 물건을 가장 먼저 파는 것 같은 형태이다. 먼저 진열된 유통기한이 가까운 제품을 먼저 팔거나 가게, 콘서트 등에서 줄을 서고 있는 고객들을 연상시키면 될 것 같다.

 

Queue

 

 

Linear Queue(선형 큐) 구현

  선형 큐란 것은 배열의 공간에 들어간 데이터가 고정되어 데이터를 빼내더라도 초기화하지 않으면 원래 데이터가 있던 배열자리에 더이상 다른 것이 들어갈 수 없는 형태의 Queue이다.

 

1. class 생성자로 뼈대 만들기

class queueType {
  constructor(size) {
      this.maxSize = size;
      this.front = -1;
      this.rear = -1;
      this.array = [];
  }
}

 

 

2. Linear Queue에 필요한 메서드들 만들기

 

queueIn()

queueIn(item) {
      if(this.rear !== this.maxSize -1 ) {
          this.array[++this.rear] = item;
      }else {
          console.log(new Error("Queue is full"));
      }
  }

 

queueOue()

queueOut() {
      if(this.front === this.rear) {
          console.log(new Error("Queue is empty"))
      }else {
          ++this.front;
          return this.array[this.front];
      }
  }

 

print()

print() {
      let str = "";
      for(let i = 0; i < this.maxSize ; i++) {
          if(this.front >= i || i > this.rear) {
              str += " | "
          }else {
              str += `${this.array[i]} | `;
          }
      }
      console.log(str);
  }

 

 

3. 전체 코드

class queueType {
  constructor(size) {
      this.maxSize = size;
      this.front = -1;
      this.rear = -1;
      this.array = [];
  }
  queueIn(item) {
      if(this.rear !== this.maxSize -1 ) {
          this.array[++this.rear] = item;
      }else {
          console.log(new Error("Queue is full"));
      }
  }

  queueOut() {
      if(this.front === this.rear) {
          console.log(new Error("Queue is empty"))
      }else {
          ++this.front;
          return this.array[this.front];
      }
  }
  
  print() {
      let str = "";
      for(let i = 0; i < this.maxSize ; i++) {
          if(this.front >= i || i > this.rear) {
              str += " | "
          }else {
              str += `${this.array[i]} | `;
          }
      }
      console.log(str);
  }
}

let queue = new queueType(6);
queue.queueIn(1);
queue.queueIn(2);
queue.queueIn(3);
queue.queueIn(4);
queue.print();    // 1 | 2 | 3 | 4 |  |  |
queue.queueOut();
queue.queueOut();
queue.queueOut();
queue.queueIn(5);
queue.queueIn(6);
queue.print();    //  |  |  | 4 | 5 | 6 |

마지막 부분에서 print() 메서드로 결과를 찍어보았을 때 처음 들어간 1, 2, 3을 아웃시키고 5, 6을 넣으면 새로운 자리에 들어가는 것을 볼 수 있다.