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

🫠 선형자료구조 - 큐(Queue)는 이름은 참 귀엽지만, 구조는 귀엽지 않은.. (그냥 느낌상.. 🥺)
큐에 대해서 아래와 같이 정리해보고자 한다. 

 

 

 

---

🫠 큐(Queue)란?

- 대표적인 특징 : FIFO(First In First Out) 가장 먼저 들어온 순서대로 가장 먼저 나온다.

- 큐를 사용하는 대표적인 예시) 줄 서기(기다린 순으로 들어가는 것)

 

 

🫠 큐의 생성자 함수 및 메서드를 구현해 보자 ①

// Queue() : 생성자 함수로 초기 데이터 설정
function Queue(array) {
  this.array = array ? array : []
}

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

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

✅ Queue 생성자 함수는 매개변수로 array(배열)를 받고, 만약 들어온 array가 없을 경우, 빈 배열([])을 반환하도록 한다.
✅ getBuffer() 메서드는 slice()를 사용하여 데이터 복사를 하도록 작성하였다.
✅ 객체 내 데이터가 있는지 배열의 길이로 확인하는 isEmpty() 메서드를 작성하였다.

 

 

 

❗️ 메서드 사용 결과

// 객체 생성
let queue1 = new Queue([1,2,3])
console.log(queue1) // Queue { array: [ 1, 2, 3 ] }

// 데이터 복사 확인 
let data = queue1.getBuffer()
console.log(data) // [ 1, 2, 3 ]
console.log(queue1 === data) // false

// 빈배열인지 확인
console.log(queue1.isEmpty()) // false

// Queue의 메서드 확인
console.log(Object.getOwnPropertyDescriptors(Queue.prototype))
/*
{
  constructor: {
    value: [Function: Queue],
    writable: true,
    enumerable: false,
    configurable: true
  },
  getBuffer: {
    value: [Function (anonymous)],
    writable: true,
    enumerable: true,
    configurable: true
  },
  isEmpty: {
    value: [Function (anonymous)],
    writable: true,
    enumerable: true,
    configurable: true
  }
}
*/

✅ // 데이터 복사 확인 --> data는 getBuffer()를 통해 값 복사를 하여 생성하였지만, queue1과 같지 않음을 확인할 수 있다.
✅ // Queue의 메서드 확인 --> Queue의 메서드로 getBuffer()와 isEmpty()가 있는 것을 확인할 수 있다.

 

 

 

---

❗️ 스택(Stack)과 큐(Queue)는 확연하게 다른데, 이는 LIFO (Last In First Out)인 스택과  FIFO(First In First Out)인 큐의 특징을 말할 수 있다. 이에 따라 스택의 pop()과 큐의 dequeue()의 차이점을 볼 수 있다.

 

⬇️ 스택 메서드 확인 ⬇️

https://cyjcyj.tistory.com/106

[자료구조] 스택(Stack) push(), pop(), peek(), size() 메서드 구현

 

🫠 큐의 생성자 함수 및 메서드를 구현해 보자 ②

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

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

let queue2 = new Queue([1,2])
console.log(queue2) // Queue { array: [ 1, 2 ] }

queue2.enqueue(3)
queue2.enqueue(4)
console.log(queue2) // Queue { array: [ 1, 2, 3, 4 ] }

console.log(queue2.dequeue()) // 1
console.log(queue2) // Queue { array: [ 2, 3, 4 ] }

✅ // 데이터 추가 --> 스택과 큐의 데이터 추가 메서드는 코드가 같다. (똑같이 뒤에서부터 push)
✅ // 데이터 삭제 --> 큐는 앞에서부터 삭제하기 때문에 스택과는 다르게 shift()를 사용하여 작성하였다. 
✅ 마지막 주석처리를 보면, console.log(queue2.dequeue())를 통해 맨 앞 데이터인 '1'이 삭제된 것을 볼 수 있다.

 

 

 

🫠 큐의 생성자 함수 및 메서드를 구현해 보자 ③

// front() : 가장 첫 데이터 반환
Queue.prototype.front = function(){
  return this.array.length === 0 ? undefined : this.array[0]
}

// size() : 큐 내 데이터 개수 확인
Queue.prototype.size = function(){
  return this.array.length
}

// clear() : 큐 초기화
Queue.prototype.clear = function(){
  this.array = []
}

let queue3 = new Queue([1,2,3,4])

queue3.dequeue() // 맨 앞 1 제거
console.log(queue3.front()) // 2 (즉, 1제거해서 2가 나옴)
console.log(queue3) // Queue { array: [ 2, 3, 4 ] }

console.log(queue3.size()) // 3

queue3.clear()
console.log(queue3) // Queue { array: [] }
console.log(queue3.size()) // 0

✅ front()를 통해 만약 배열이 있을 경우, 배열의 가장 첫 번째 Index의 값을 반환하고, 없을 경우, undefined를 반환하도록 작성하였다.
✅ clear()를 통해 큐를 초기화하는 메서드를 작성하였다. 
✅ 마지막 주석 처리 확인해 보자.