스택(Stack)과 큐(Queue)의 개념 정리_(2) Queue

Queue(차례로 줄서기)를 나타내는 이미지

1. 큐(Queue)의 개념

• 큐는 은행에서 대기표를 받고 업무를 보기 위해 기다리는 줄과 같다.
  : 먼저 온 사람이 먼저 업무를 볼 수 있고, 나중에 온 사람은 제일 뒷 번호의 번호표를 받아 맨 마지막에 업무를 본다.
• 가장 먼저 삽입된 자료가 가장 먼저 삭제(출력)되는 구조적 특징을 가진다.
  : FIFO ( First In, First Out )  <-> LIFO(스택)
• rear는  큐에서 삽입이 발생하는 지점으로, 대기줄의 가장 뒷부분이다.
  front는 큐에서 삭제(출력)이 발생하는 지점으로, 대기줄의 가장 앞부분이다.
  : rear에서 일어나는 삽입연산을 '인큐(enQueue)', front에서 일어나는 삭제연산을 '디큐(dnQueue)'라고 한다.
• 자료를 삽입할 경우 rear(대기표의 숫자)를 증가시키고, 삭제 시 front(은행원이 부르는 현재순서의 번호)를 증가 시킨다.

2. 큐의 활용 예시

• 우선순위가 같은 작업의 예약
  : 프린트의 인쇄 대기열
• 은행에서의 대기표
• 콜센터에서의 고객 대기
• 너비우선탐색(BFS) 구현
• 캐시
• 롤에서의 게임 잡기

3. 큐를 객체와 함수로 구현해보기

큐에 들어오는 자료들을 모은 것을 하나의 객체(인덱스와 자료 값으로 구성)로 표현을 하고,
큐에 자료를 넣고, 빼는 것을 enQueue( ), dnQueue( ) 함수로 구현해볼 수 있다.

 

3-1. 큐의 생성

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

큐는 인덱스와 값으로 연결된 하나의 객체로 표현해 볼 수 있다. 

초기의 큐는 비어있으며, 즉 대기줄이 없는 경우, front와 rear의 값 모두 0을 가진다.

 

3.2 큐의 추가 (enQueue)

큐의 추가는 대기줄에 1명의 사람이 더 온 것과 같다.

enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }

큐에서 삽입연산이 실행되면
1)  rear를 주소값(인덱스)로 하고, 해당하는 주소에 받아온 자료를 추가한다.
2) rear가 가르키고 있는 인덱스주소를 1 증가시킨다. (다음사람의 번호표를 지정)

 

3.2 큐의 삭제 (Pop)

dequeue() {
  let dequeueValue = this.storage[this.front];
  if (this.size() <= 0) { // this.front === this.rear
    return undefined;
    } 
  else {
    delete this.storage[this.front];
    this.front += 1
    return dequeueValue;
    }
  }

큐에서 삭제연산이 실행될 경우 

1) front의 주소를 삭제하여, 해당 주소에 담겨있는 값을 포함하여 삭제하여 준다.
2) 이후 front의 값을 1 증가 시켜, 다음요소를 삭제(출력)할 준비를 한다. 

 

3.3. 클래스로 나타낸 큐의 코드

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return Object.keys(this.storage).length;
  }

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }

  dequeue() {
    let result = this.storage[this.front];
    if (this.size() <= 0) {
      return undefined;
    } else {
      delete this.storage[this.front];
      this.front += 1;
      return result;
    }
  }
}

 

 

4. 프로그래머스에서 큐에 관련된 문제 풀어보기

programmers.co.kr/learn/courses/30/lessons/42587

코딩테스트 연습 - 프린터

출처 및 참고

www.atoz-develop.tistory.com/

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시