[자료구조] 원형 큐(Circular Queue) 특징 및 메서드 구현 실습

❗️❗️ 자료구조 & 알고리즘 코드를 보면서 응? 왜 이렇게 되지? 뭐지? 하면서 강의를 계속 돌려본 건 원형 큐 강의가 역대급인 것 같다.. 정말 별것도 아닌걸 내가 모르고 있었다니..! 삽질하면서 알게 된 내용을 아래와 같이 정리하고자 한다^^!
이번 포스팅은 나를 너무너무 힘들게 했던 원형 큐 💛

 

 

🫠 원형 큐(Circular Queue)란?

> 원형 형태를 가지며, 큐의 대표적인 특징은 FIFO(First In First Out) 기반의 선형 자료 구조

> 첫 데이터를 가리키는 head와 가장 끝 데이터를 가리키는 tail을 갖고 있다.

 

 

 

🫠 원형 큐의 생성자 함수

> CircularQueue() : 초기 속성값 설정을 위한 생성자 함수

> array 의 기본값 : [](빈배열), size의 기본값 : 5

function CircularQueue(array = [], size = 5){
  this.array = array
  this.size = array.length > size ? array.length : size
  this.length = array.length
  this.head = 0 // head는 언제나 0부터 
  this.tail = array.length // tail은 가장 끝부터
}

✅ this.size의 경우, 배열의 길이와 크기 중 큰 값이 들어가도록 조건 삼항 연산자를 사용

 

 

 

🫠 원형 큐 메서드 구현

// getBuffer() : 객체 내 데이터 셋 반환
CircularQueue.prototype.getBuffer = function(){
  return this.array.slice()
}

// isEmpty() : 데이터 비어 있는지 확인
CircularQueue.prototype.isEmpty = function(){
  return this.length == 0
}

// isFull() : 데이터 꽉 차 있는지 확인 
CircularQueue.prototype.isFull = function(){
  return this.length == this.size
}


// ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ


// 객체 생성 및 메서드 실행 확인
let cqueue1 = new CircularQueue([1,2,3])
console.log(cqueue1)
/*
CircularQueue {
  array: [ 1, 2, 3 ],
  size: 5, // size를 따로 설정해주지 않았기에 기본값인 5가 들어감
  length: 3,
  head: 0,
  tail: 3
}
*/

console.log(cqueue1.isEmpty()) // false
console.log(cqueue1.isFull()) // false


let cqueue2 = new CircularQueue([1,2,3,4,5])
console.log(cqueue2.isFull()) // true

✅ 계속해서 지난 포스팅과 같은 메서드를 반복하기 때문에 따로 설명은 하지 x! (CircularQueue의 size 주석처리는 확인하자)

 

 

 

---

🫠 원형 큐에 데이터 추가 메서드 구현하기(enqueue) ⭐️⭐️⭐️

CircularQueue.prototype.enqueue = function(element){
  if(this.isFull()) return false // 만약 배열이 모두 찼다면 false return
  
  this.array[this.tail % this.size] = element 
  this.tail++
  this.length++

  return true
}

❗️ this.array[this.tail % this.size] = element 부분을 보자
처음에 저 식을 보자마자 잉? 저걸 왜 저기에.. 라는 생각을 했었는데, 이해하고 나니까 그냥 강사님이 너무 천재인 것 같다, 하하
내가 해맸던 부분은 바로 저 부분. 

👉🏻 배열에 공간이 남아, 데이터를 새로 추가할 경우(아래와 같이 예시를 들어보겠다.)
array = [1,2,3] (size : 5, length : 3, head : 0, tail : 3)
새로운 element '4' 추가 --> array[3 % 0]으로 인해 array[3]에 '4'추가 (tail++)
새로운 element '5' 추가 --> array[4 % 0]으로 인해 array[4]에 '5'추가

👉🏻 배열에 데이터가 꽉 찼다고 가정할 경우, 만약 가장 앞쪽 데이터 한 개를 삭제 후, 새로 추가하고 싶을 때
새로 추가된 element를 배열의 0번째에 넣기 위해 변경해줘야 하는데, 이를 this.tail % this.size로 해결할 수 있다.

array = [1,2,3,4,5] (size : 5, length : 5, head : 0, tail : 5)
새로운 element '6' 추가 --> 맨 위 if문에 의해 false가 되어 배열에 6을 추가하지 못한다.
가장 맨 앞 데이터 '1', '2'를 삭제 --> array = [<2 empty items>,3,4,5] (현재 size : 5, length : 3, head : 2, tail : 5)
this.tail = 5, this.size = 5, 새로운 element '6' 추가 --> array[5 % 5]에 의해 array[0]에 '6' 추가
this.tail = 6, this.size = 5, 새로운 element '7' 추가 --> array[6 % 5]에 의해 array[1]에 '7' 추가

 

 

 

🫠 원형 큐에 데이터 삭제 메서드 구현하기(dequeue) ⭐️⭐️⭐️

CircularQueue.prototype.dequeue = function(){
  if(this.isEmpty()) return undefined; // 빈배열이라면 undefined return

  let element = this.array[this.head % this.size] // array를 삭제하기 전 element라는 임시 공간에 미리 넣어둠
  delete this.array[this.head % this.size]
  this.head++ 
  this.length--

  return element // 삭제된 element 반환
}

❗️let element = this.array[this.head % this.size] 부분을 보자
enqueue에서 한참을 해맸더니, dequeue는 바로 이해했음! (아래와 같이 예시를 들어보겠다.)

array = [1,2,3,4,5] (size : 5, length : 5, head : 0, tail : 5)
'1'을 삭제하고 싶은 경우 --> array[0 % 5]로 인해 array[0]의 element 삭제 (head++)
(💡 추가 설명 : [0%5] = 0, [1%5] = 1, [2%5] = 2, ... 즉, 나누지 못하는 값은 그대로 array[index]로 들어옴)
'2'를 삭제하고 싶은 경우 --> array[1 % 5]로 인해 array[1]의 elemnet 삭제

결과 : array[<2 empty items>, 3, 4, 5]

 

 

 

🫠 자 이제 한 번 데이터를 추가 해보자.. 

// 객체 생성
let cqueue3 = new CircularQueue([1,2,3,4])
console.log(cqueue3)
/*
CircularQueue {
  array: [ 1, 2, 3, 4 ],
  size: 5,
  length: 4,
  head: 0,
  tail: 4
}
*/


// 데이터 추가
cqueue3.enqueue(5)
cqueue3.enqueue(6) // isFull이기 때문에, enqueue(6)은 false로 배열에 추가되지 x
console.log(cqueue3)
/*
CircularQueue {
  array: [ 1, 2, 3, 4, 5 ],
  size: 5,
  length: 5,
  head: 0,
  tail: 5
}
*/

✅ 배열이 꽉 찼기 때문에 '6'은 추가되지 않은 것을 확인할 수 있다.

 

 

 

🫠 삭제도 해보자..

// 데이터 삭제
console.log(cqueue3.dequeue()) // 1 삭제 
console.log(cqueue3.dequeue()) // 2 삭제 
console.log(cqueue3)
/*
CirculatorQueue {
  array: [ <2 empty items>, 3, 4, 5 ],
  size: 5,
  length: 3,
  head: 2,
  tail: 5
}
*/


// 사이즈가 2 비어있는 상태에서 6, 7을 추가하면?
cqueue3.enqueue(6)
cqueue3.enqueue(7)
console.log(cqueue3)
/*
CirculatorQueue {
  array: [ 6, 7, 3, 4, 5 ],
  size: 5,
  length: 5,
  head: 2,
  tail: 7
}
*/

✅ '6', '7'이 array[0], array[1]에 추가된 것을 확인할 수 있다.

 

 

 

---

💡 여기서 잠깐!

 > 만약 계속해서 tail과 head를 ++하면 숫자가 너무 커지기 때문에 아래와 같은 코드로 작성하는 것이 더 현명하니, 확인 ✅

// enqueue() : 데이터 추가
CircularQueue.prototype.enqueue = function(element){
  if(this.isFull()) return false 
  
  this.array[this.tail] = element
  this.tail = (this.tail + 1) % this.size // +1 해주자마자 연산자로 나눔
  this.length++

  return true
}


// dequeue() : 데이터 삭제
CircularQueue.prototype.dequeue = function(){
  if(this.isEmpty()) return undefined;

  let element = this.array[this.head % this.size]
  delete this.array[this.head]
  this.head = (this.head + 1) % this.size // +1 해주자마자 연산자로 나눔
  this.length-- 

  return element
}

✅ tail과 head에 ++이 아닌 +1을 해준 후, 바로 연산자로 나누면 숫자가 커지는 것을 막을 수 있다!

 

 

 

🫠 새로 작성한 enqueue()와 dequeue()도 실습해 보자

// 객체 생성
let cqueue3 = new CircularQueue([1,2,3])
console.log(cqueue3)
/*
CircularQueue {
  array: [ 1, 2, 3 ],
  size: 5,
  length: 3,
  head: 0,
  tail: 3
}
*/


// 데이터 추가
cqueue3.enqueue(4)
cqueue3.enqueue(5) 
console.log(cqueue3)
/*
CircularQueue {
  array: [ 1, 2, 3, 4, 5 ],
  size: 5,
  length: 5,
  head: 0,
  tail: 0 // tail이 5가 아닌, 0이 된 것을 확인
}
*/


// 데이터 삭제
console.log(cqueue3.dequeue()) // 1 삭제 
console.log(cqueue3.dequeue()) // 2 삭제 
console.log(cqueue3.dequeue()) // 3 삭제 
console.log(cqueue3.dequeue()) // 4 삭제 
console.log(cqueue3.dequeue()) // 5 삭제 
console.log(cqueue3)
/*
CircularQueue {
  array: [ <5 empty items> ],
  size: 5,
  length: 0,
  head: 0, // head는 1->2->3->4->0 으로 변경
  tail: 0
}
*/

✅ 주석처리 되어 있는 head와 tail 부분을 위에 enqueue() & dequeue() 코드와 확인하여 차이를 보자!