Stack & Queue (3)

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

우리는 미진이를 통해서 스택과 큐를 알아보았어요. 나름 재미있었다고 생각을 했는데... 읽으시는 분들은 아니었을까요? 흑흑.

스택과 큐를 공부하면서 많은 도움을 받았던 유튜브 링크까지 드립니다. 요기에 큐까지 있으니까 관심 있으신 분들은 함 봐 보세요!

선형 Queue의 단점

우리가 배웠던 큐, 그러니까, 일직선으로 있는 선형 큐 같은 경우에는 단점이 좀 있는데요.

자바스크립트 같은 경우엔.. 배열로 큐를 구현한다고 했을 때, 인덱스 0인 요소를 빼 버리면 바로 뒤에 있는 요소가 0이 되잖아요? 그래서 큐를 돌릴 때 딱히 문제가 되지 않아요.

그런데, 이제, JS가 아닌 다른 언어들은 배열의 크기가 정해져 있기 때문에, 큐가 다 차게 되면 데이터를 더 추가할 수 없고(할 수는 있지만 시간이 너무 오래 걸리기도 해요), 빼낸 메모리들의 빈 공간을 사용할 수가 없어서 메모리가 쓸데없이 사용이 되기도 합니다. 그리고 계속 뒤로 밀리는 시스템이기 때문에, 할 때마다 데이터들을 앞으로 한 칸씩 당기게 되면 우리는 해피 코딩을 할 수 없게 될 거예요.

그래서 이를 보완한 점이 환형 큐, Circular Queue입니다.

원형 큐? 환형 큐? Circular Queue?

선형 큐의 문제점을 보완하기 위한 자료 구조로, 큐의 처음(front)과 끝(rear)가 붙어 있는 모습인데요. 그 모습이, 음, 저는 그냥 도넛 같았습니다.

요롷게 생긴 친구인데, 이왕 도넛 같다고 한 거, 도라에몽의 암기 빵처럼 만들어 봅니다.

7과 0이 붙어 있는 거 보이시죠? 이렇게 큐를 동그랗게 말았는데요, 보시는 것처럼 원형 큐는 크기의 제한을 두어야 됩니다.

큐의 흐름이 어떻게 되나요?

흐름을 설명하기 전에 알아두어야 할 게 있습니다.

원형 큐 중 인덱스 하나는 공백으로 남겨야 한다.
제일 처음 시작하는 인덱스를 공백으로 남겨 놓고 그 다음 인덱스부터 데이터 삽입이 이뤄지는데요, 우선삽입 후 데이터를 빼내는 것이기 때문에 그런 것도 있고, 큐의 포화 상태 여부를 판단하기 위해서도 필요합니다.
'front와 rear가 같이 있다면 공백으로 하자'라는 약속을 해 놓았기 때문에 항상 dequeue로 공백을 유지해야 하는 front의 자리는 empty로 남겨 놓습니다.

enqueue(이하 인큐)를 사용하여 데이터를 넣었습니다.
rear를 단순히 +1을 해 준 게 아니라, 약간 특별한 수식으로 넣어 줬는데요.
rear = (rear + 1) % size입니다. 큐의 사이즈를 나누었죠? 이는 원형 큐이기 때문이에요. 큐 사이즈의 나머지로 연산을 함으로써 계속 빙빙 돌 수 있게 만드는 원리입니다.

계속 데이터를 넣어 볼게요.

딸기잼(data)을 7번까지 발랐고, 이제는 0번까지 다 채우고 싶은데 그게 안 되네요. 왜일까요? rear = (rear + 1) % size 이 수식을 썼을 때도 0이 나와서, 당연히 들어가야 되는데...

앞서 말했지만, front는 큐의 포화 상태를 위해서라도 항상 공백이어야 합니다. 큐의 공백이 딱 한 개 남았기 때문에 포화 상태로 인식하고, 데이터를 더 넣지 않습니다.

자, dequeue(이하 데큐)를 사용해서 데이터를 빼 봅시다.

(혹시 진짜 식빵에 바른 토핑만 긁어서 드시는 분 계신가요? 제가 식당 일 할 때 진짜 이런 분 계셔서, 아직도 뇌리에 남네요.)

데큐를 4번 실행한 결과입니다. front는 4에 가 있구요. 물론 front도 rear와 마찬가지로 front = (front + 1) % size를 작성해서 큐의 사이즈 안에서 놀아나게 합니다. 공백이 많이 늘었네요? 데이터를 더 넣을 수 있겠어요.

이런 식으로 데이터는 빠져나가고, 들어오는 과정을 거칩니다.

method of Circular Queue

환형 큐로 오면서 몇 가지 추가가 된 게 있어 보이네요!

enqueue
dequeue
size
front
rear
까지는 같은데,
isempty : 큐가 비어 있는지 확인
isfull : 큐가 꽉 찼는지 확인
이게 꼭 필요해 보입니다.

Pseudocode

enqueue

isfull을 이용하여 스토리지에 공간 확인
만약에 공간이 없다면 스토리지에 공간이 없다는 콘솔 로그 띄움
만약에 공간이 있다면 데이터 삽입
3-1. 스토리지 객체에 rear = (rear + 1) % size의 인덱스에 데이터 넣음
스토리지 리턴

dequeue

isempty를 이용하여 스토리지 공백 확인
만약에 공백이라면 스토리지가 공백이라는 콘솔 로그 띄움
만약에 공백이 아니라면 데이터를 뺌
3-1. 스토리지 객체에 front = (front + 1) % size 인덱스에 담긴 데이터를 반환함.

isempty

rear와 front의 수가 같다면 true, 아니라면 false를 반환

isfull

rear = (rear + 1) % size를 했을 때 front 값이 나온다면 true를 반환 아니라면 false를 반환

size (함수가 아닌 변수)
front
rear

JS code

class Oqueue {
  constructor () {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
    this.size = 7; //임의로 작게 설정
  }
  
  isFull() {
    return (this.rear + 1) % this.size === this.front;
  }
  
  isEmpty() {
    return this.rear === this.front
  }
  
  enqueue(element) {
    if(this.isFull()) return 'storage에 공간이 없습니다.'
    else {
      this.storage[this.rear = (this.rear + 1) % this.size] = element;
      return this.storage;
    }
  }
    
  dequeue() {
    if(this.isEmpty()) return 'storage에 데이터가 없습니다.'
    else {
      let curData = this.storage[this.front = (this.front + 1) % this.size];
      delete this.storage[this.front % this.size]
      return curData;
    }
  }
}