Stack & Queue (2)

i do as i say·2020년 5월 1일

스택이 끝났으니.. 쿠에우에를 알아봅시다. 왜 자꾸 큐를 쿠에우에라고 하냐고요? 재미있는 게 재미있는 거 아니겠습니까? 공부는 즐거워야 재미있고, 재미있는 걸 하면 행복해지고, 인생의 궁극적인 목표는 행복이니까 공부를 즐겁게 합시다❣️

Queue 자료 구조란?

사전적 용어로는… ‘줄을 서다’가 되겠습니다. 참 정말, 직관적으로 잘 짓는 것 같아요. 이 자료 구조는 정말 줄을 서는 것처럼 되어 있거든요.
FIFO(first in first out) 피포 구조인 Queue는 선입선출입니다.

(큐는 Queue 딱 하나만 있는 게 아니라, 기출변형(??) 같은 원형 큐(Circular Queue), 우선순위 큐(Priority Queue)도 있는데요, 고것들까지 함께 알아봅니다. 일단은 기본적인 큐부터 알아봐요!)

비유를 하기에 앞서,
모 아이돌을 좋아했던 저는… 최애 언니를 보러 가기 위해서 매일 줄을 섰는데요, 그건 너무 머나먼 과거 이야기이고, 우리에게는 미진이가 있으니, 미진이 이야기로 다시 돌아가서 큐를 설명해 보려고 합니다.

우리의 일하는 모습을 많이 닮은(ㅠㅠ) 미진이는 편의점에 또 출근을 했습니다.
편의점에 출근하자마자 계산을 기다리는 사람들이 많이 있는 것 아니겠어요?

알바생 미진이는 서터레서를 가라앉히고 첫 번째 손님부터 차근차근 계산을 해서 보냅니다.

마지막 손님까지 계산을 끝냈다고 생각을 했는데, 뒤를 보니 아까와 같은 상황입니다.

이렇게, 들어온 순서대로 배출을 하는 것이 Queue입니다. 손님 1, 2, 3, 4, 5… 대기표랑 비슷하다고 생각하시면 됩니다.

편의점 그림이 계산대가 있어서 살짝 오해의 소지가 있으니, 위키에 있는 전문적인 사진을 가지고 왔습니다.

요것이 바로 큐입니다. 먼저 들어온 대로, 먼저 나간다.

큐를 이용한 예

프린트 대기열, 게임 대기열, 멜론 티켓팅 대기열 같은 게 있겠네요!

method of Queue

스택은 enqueue와 dequeue가 메인 기능입니다.

enqueue: 데이터를 스토리지에 넣음
dequeue : 데이터를 스토리지에서 빼냄
size: 스토리지의 크기를 나타냄
empty: 스토리지 안에 데이터의 유무를 나타냄
//요까지는 함수
front: 데이터의 제일 앞을 나타냄
rear: 데이터의 제일 뒤를 나타냄
//요기는 변수

큐도 이것보다 조금 더 많은, 여러 가지의 동작들이나 단어들이 있는데, 가장 중요하다고 생각하는 것을 몇 개 뽑아서 썼으니, 더 많은 정보를 원하신다면 여러 정보를 더 습득해 주세요!

pseudocode

큐 함수
-size
1. 스토리지 객체를 Object.keys를 사용하여 배열 메소드인 length를 사용할 수 있게 하고, 결괏값을 리턴한다.

-enqueue
1. 받은 데이터를 스토리지 객체에 넣는다.
2. rear를 +1 한다.
3. 스토리지 객체를 리턴한다.

-dequeue
1. 스토리지 객체에 있는 제일 앞 데이터를 빼내서 변수에 담는다. 빼낼 땐, front를 key 값으로 사용한다.
2. 스토리지 객체에 있는 제일 앞 데이터를 삭제한다.
3. front를 +1 한다. (객체를 빼냈기 때문에.)
4. 1 번의 변수를 리턴한다.

-empty
1. 만약 스토리지가 비어 있으면 true를, 비어 있지 않다면 false를 반환한다.

JS code

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++;
    
    return this.storage;
  }
    
  dequeue() {
    let curData = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    
    return curData;
  }
  
  size () {
    return Object.keys(this.storage).length;
  }
  
  empty() {
    if(Object.keys(this.storage).length === 0) return true;
    return false;
  }
}