[자료구조] 큐(Queue) 최적화 메서드 구현하기(enqueue() & dequeue())

🫠 지난 시간에 큐(Queue)에 대해서 간단하게 메서드를 구현해 보고, 실습을 하였는데 지난 시간 구현한 메서드보다 더 최적화된 메서드를 이번 시간에 정리하고자 한다. index 즉, 위치값을 이용한 메서드를 구현하여 코드가 실행되는 시간을 조금이라도 줄여보자!

 

❗️ 지난 시간에 작성한 큐(Queue) 메서드 확인 ⬇️⬇️⬇️

https://cyjcyj.tistory.com/110

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

 

 

 

 

🫠 큐 최적화 생성자 함수 구현 Queue()

> 방식 개선 : enqueue & dequeue 방식을 push & shift에서 index로 변경 

> shift는 O(n), index는 O(1) 

> 속도 개선 👍🏻

// Queue() : 생성자 함수로 초기 데이터 설정
function Queue(array) {
  this.array = array ? array : []
  this.tail = array ? array.length : 0
  this.head = 0 // head는 항상 0번째
}


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


// isEmpty() : 객체 내 데이터 o/x
Queue.prototype.isEmpty = function(){
  return this.array.length === 0
}

✅ Queue 생성자 함수 코드에서 head와 tail을 추가하였다.
> head : index에 따라 계속해서 옆으로 이동하며 dequeue 역할을 할 예정
> tail : 맨 끝 데이터의 역할을 하기 때문에 push와 같음

✅ Queue 생성자 함수 중 tail의 경우, 만약 배열이 있다면 배열의 길이 값을 할당하여, 가장 마지막 값을 넣어줌
✅ 나머지 getBuffer() & isEmpty()는 지난 시간 작성한 코드와 같다.

 

 

 

🫠 큐 최적화 메서드 구현 enqueue() & dequeue()

// enqueue() : 데이터 추가
Queue.prototype.enqueue = function(element){
  // return this.array.push(element)
  return (this.array[this.tail++] = element)
}


// dequeue() : 데이터 삭제
Queue.prototype.dequeue = function(){
  // return this.array.shift()
  if(this.tail === this.head) return undefined

  let element = this.array[this.head] // 삭제할 맨 앞 데이터를 element에 넣어줌
  delete this.array[this.head++] // 해당 데이터가 있는 공간은 삭제하고, this.head를 다음으로 넘김
  return element // 삭제한 element를 반환
}

✅ enqueue() 메서드에서 // return 주석처리는 지난 시간 작성한 코드에 해당한다.(비교를 위해 주석처리)
👉🏻 배열의 가장 끝 위치를 담고 있는 this.tail에 새로운 데이터 element 값을 넣어준다.
👉🏻 [this.tail++]을 통해 this.tail의 위치값을 다음으로 넘김(+1 증가)

✅ dequeue() 메서드에서 // return 주석처리는 지난 시간 작성한 코드에 해당한다.(비교를 위해 주석처리)
👉🏻 if(this.tail === this.head)일 경우는 배열 내 데이터가 없다는 뜻이므로 삭제할 데이터가 없으니 undefined return
👉🏻 [this.head++]를 통해 this.head의 위치값을 다음으로 넘김(+1 증가)

 

 

 

❗️ 큐 최적화 메서드를 통해 확인해보자

// 새로운 Queue 생성자 함수 사용
let queue1 = new Queue([1,2])
console.log(queue1) // Queue { array: [ 1, 2 ], tail: 2, head: 0 }


// head & tail 확인
queue1.enqueue(3) 
queue1.enqueue(4)
console.log(queue1) //Queue { array: [ 1, 2, 3, 4 ], tail: 4, head: 0 }


// dequeue를 통해 나온 head & tail 결과값 확인
console.log(queue1.dequeue()) // 1
console.log(queue1) // Queue { array: [ <1 empty item>, 2, 3, 4 ], tail: 4, head: 1 }

✅ 주석 처리 1번) 기존 Queue 생성자 함수와는 다르게, tail과 head가 추가된 것을 확인할 수 있다.
✅ 주석 처리 2번) enqeue() 메서드를 통해 현재 tail이 맨 끝 데이터 4인 것을 확인할 수 있다.
✅ 주석 처리 3번) dequeue()를 통해 가장 앞 데이터 '1'이 삭제된 것을 확인할 수 있고, head가 ++ 되어 0 -> 1로 증가된 것을 확인할 수 있다.