알고리즘 시리즈 - 자료구조 2

이번 포스트에서는 선형 자료구조 중 하나인 큐(Queue)에 대해서 다뤄보겠습니다.

큐 (Queue)

선형 자료구조 중 하나인 큐(Queue)는 FIFO(First In First Out, 선입선출) 구조의 자료구조로 LIFO(Last In First Out, 후입선출) 구조의 스택(Stack)과는 반대되는 개념이다. 현실속에서의 큐는 프린터의 출력처리 방식, 매표소 앞의 일렬로 선 대기열, OS의 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황ㅇ 이용된다.

구조

큐는 복수의 자료로 이루어져 있으며 복수의 자료가 삽입되어 추출되길 기다리고 있는 곳을 큐 라고 부르며 큐에 자료를 삽입하는 것을 Enqueue, 반대로 자료를 추출하는 것을 Dequeue 라고 하며 LIFO(후입선출)을 개념을 갖고 있다. 아래와 같은 구조를 갖고 있다.

• Front (Head): 데이터를 추출할 수 있는 위치
• Rear (Tail): 데이터를 삽입할 수 있는 위치
• Overflow (오버플로우): 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우
• Underflow (언더플로우): 큐가 비어 자료를 꺼낼 수 없는 경우

큐 기능 (메서드)

• enqueue(data): 삽입 / 큐의 Rear에 데이터를 삽입
• dequeue(): 추출 / 큐의 Front에서 데이터를 추출
• rear(): 조회 / 큐의 Rear에 데이터 값을 반환
• front(): 조회 / 큐의 Front에 데이터 값을 반환
• size(): 조회 / 큐의 데이터 개수 반환
• empty(): 조회 / 큐가 비었는지 Boolean을 반환
• toString(): 조회 / 큐의 모든 데이터를 문자열로 반환

구현

큐를 구현해보자. 큐를 구현하는 방법은 두 가지로, 한 가지는 Javascript의 Array(배열)와 Array의 메서드를 통해 구현하는 방법 그리고 나머지 한 가지는 Linked List와 같이 구현하는 방법으로 총 두가지 입니다. 이번 포스트에서는 두가지 방법 모두 사용해 구현해보겠습니다.

구현 순서는 아래와 같다.

1. Queue 객체 생성
2. 데이터 삽입 기능 (enqueue)
3. 데이터 조회 기능 (front, rear, size, empty, toString)
4. 데이터 추출 기능 (dequeue)

Javascript Array를 사용한 Queue 구현 방법

Queue 객체 생성

하나의 대기열이 될 Queue를 객체 생성방식으로 만들어보겠습니다.

function Queue () {
  this.queue = []
}

Queue는 복수의 data로 채워한 하나의 queue를 생성하는 생성자 함수로, 내부 property로 data를 담아둘 queue를 빈 Array([])를 할당한다. Javascript Array를 사용한 Queue 구현 방법에서는 Javascript Array와 메서드를 이용할 것이기 때문에 많은 property가 필요하지 않다.

Queue 메서드 구현

위에서 정의한 Queue 생성자 함수 내부에 구현해도 되지만 저는 prototype 속성을 사용한 객체 생성 방법으로 구현해보겠습니다.

데이터 삽입 기능

Queue.prototype.enqueue = function (data) {
  this.queue.push(data)
}

enqueue 메서드는 Queue 객체에 데이터를 삽입하는 메서드로 Javascript의 Array 메서드 중 push를 사용해 queue에 data를 삽입하는 기능을 구현했습니다.

데이터 조회 기능

이번에는 큐에 삽입한 데이터를 조회하는 기능을 구현해보겠습니다. 구현할 조회 메서드는 front, rear, size, empty, toString 입니다.

front 를 구현해보겠습니다.

Queue.prototype.front = function (data) {
  return !this.queue.length
    ? null
    : this.queue[this.queue.length - 1]
}

front 메서드는 Queue 객체에 삽입된 데이터 중 가장 오래된 데이터이자 가장 먼저 추출될 데이터에 대한 조회 기능입니다.

이번에는 rear 를 구현해보겠습니다.

Queue.prototype.rear = function (data) {
  return !this.queue.length
    ? null
    : this.queue[0]
}

rear 메서드는 Queue 객체에 삽입된 데이터 중 가장 최근 데이터에 대한 조회 기능입니다.

size 를 구현해보겠습니다.

Queue.prototype.size = function (data) {
  return this.queue.length
}

size 메서드는 Queue 객체에 삽입된 데이터의 개수를 반환하는 기능을 기능입니다.

empty 를 구현해보겠습니다.

Queue.prototype.empty = function (data) {
  return !this.queue.length
}

empty 메서드는 Queue 객체의 queue 가 비었는지 조회하는 기능입니다.

마지막으로 toString 를 구현해보겠습니다.

Queue.prototype.toString = function (data) {
  return !this.queue.length
    ? []
    : `[${this.queue.toString()}]`
}

toString 메서드는 Queue 객체의 queue 를 문자열로 출력하는 기능입니다.

데이터 추출 기능

Queue.prototype.dequeue = function (data) {
  this.queue.shift(data)
}

dequeue 메서드는 Queue 객체에 데이터를 추출하는 메서드로 Javascript의 Array 메서드 중 shift를 사용해 queue에 삽입된 data 중 가장 마지막에 삽입되었으며 가장 빨리 추출되어질 data를 추출하는 기능입니다.

Linked List 구현방법을 사용한 Queue 구현 방법

이번에는 Linked List와 같은 구조로 다수의 data와 data로 채워진 Queue를 구현해보겠습니다. 구현할 메서드는 미리 정해둔 메서드 입니다.

Data

function Data (val) {
  this.value = val
  this.next = null
}

Data는 큐의 요소인 데이터를 생성하는 생성자 함수로, 내부 property로 data 본인의 값인 value와 다음 data를 참조하기 위한 link를 갖는다.

Queue 객체 생성

큐를 생성할 Queue 생성자 함수를 정의하고, 위에서 정의한 구조와 메서드를 구현하기 위해 필요한 property를 정의했습니다.

function Queue () {
  this.count = 0
  this.head = null
  this.tail = null
}

Queue 메서드 구현

위에서 정의한 Queue 생성자 함수 내부에 구현해도 되지만 저는 prototype 속성을 사용한 객체 생성 방법으로 구현해보겠습니다.

데이터 삽입 기능

큐에 데이터를 생성 및 삽입하는 기능을 구현했습니다.

Queue.prototype.enqueue = function (data) {
  let newData = new Data(data)
  if (!this.head) {
    this.head = newData
  } else {
    let current = this.head

    while(current.next)  {
      current = current.next
    }
    current.next = newData
  }
  this.tail = newData
  this.count++
  return newData
}

var queue = new Queue // 큐 객체 생성
queue.enqueue(20) // 데이터 생성 및 추가
queue.enqueue(10)
queue.enqueue(18)

console.log(queue)

enqueue 메서드는 큐에 데이터를 삽입하는 메서드로, 새로운 data를 추가하면 기존 head 데이터에 next가 할당되거나 tail 데이터가 갱신되는 것으로, line 3 ~ line 14 코드와 같이 head의 데이터 할당여부에 따라 처리되는 방식이 다르며 head가 지정되어 있다면 새로운 data가 추가되기전 마지막 data의 data.next에 새로운 데이터를 할당해주고 마지막에 this.tail에 생성된 data를 할당해준다.

위와 같이 구현한 queue를 출력하면 아래와 같습니다.

데이터 조회 기능

이번에는 큐에 삽입한 데이터를 조회하는 기능을 구현해보겠습니다. 구현할 조회 메서드는 front, rear, size, empty, toString 입니다.

front 메서드를 구현해보겠습니다.

Queue.prototype.front = function () {
  return this.head.value
}

front 메서드는 큐 데이터열에서 가장 앞에 있는 즉, 가장 먼저 추출되며 삽입된지 가장 오래된 데이터가 무엇인지 조회하는 메서드 입니다. head property는 데이터를 삽입할때 할당되므로 추가적인 loop 문을 통해 조회를 할 필요가 없습니다.

rear 메서드를 구현해보겠습니다.

Queue.prototype.rear = function () {
  return this.tail.value
}

rear 메서드는 큐 데이터열에서 가장 뒤에 있는 즉, 현재 데이터열에서 가장 나중에 추출되며 삽입된지 가장 최신의 데이터가 무엇인지 조회하는 메서드 입니다. tail property는 데이터를 삽입할때마다 갱신되므로 추가적인 loop 문을 통해 조회를 할 필요가 없습니다.

size 메서드를 구현해보겠습니다.

Queue.prototype.size = function () {
  return this.count
}

size 메서드는 큐 데이터열의 크기를 반환하는 메서드로, 큐에 신규 data를 삽입할때마다 갱신되기 때문에 추가적인 loop 문을 통해 조회를 할 필요가 없습니다.

empty 메서드를 구현해보겠습니다.

Queue.prototype.empty = function () {
  return !this.count
}

size 메서드는 큐 데이터열이 비었는지 Boolean 값을 반환하는 메서드로, Queue 생성자 함수의 size property를 사용하면 됩니다.

toString 메서드를 구현해보겠습니다.

Queue.prototype.toString = function () {
  let line = []
  let current = this.head
  if (!current) {
    return ''
  } else {
    while (current.next) {
      line.push(current.value)
      current = current.next
    }
    return line.toString()
  }
}

toString 메서드는 큐에 삽입된 데이터열을 문자열로 출력하는 메서드로, head의 여부에 따라 반환되는 로직을 분리했습니다.

데이터 추출 기능

마지막으로 큐의 데이터 추출 기능인 dequeue 메서드를 구현해보겠습니다.

Queue.prototype.dequeue = function () {
  let front = this.head
  this.head = front.next

  let current = this.head
  while (current.next) {
    current = current.next
  }

  this.tail = current
  this.count--
  return front
}

dequeue 메서드는 큐의 front에 해당되는 데이터를 출력하는 메서드로, Queue 생성자 함수 내에 저장된 head property를 반환하고 this.head.next에 할당된 value를 this.head로 갱신해준 후 this.tail property 또한 갱신했습니다.

마치며

이번 포스트에서는 알고리즘 시리즈의 자료구조 포스팅 중 두번째로, 큐(Queue)의 정의와 구조 및 메서드에 공부해봤습니다. 그리고 정의한 구조와 메서드를 구현해봤습니다. 다음 포스트에서는 링크드 리스트, 큐와 같이 선형 자료구조 중 하나인 스택에 대해서 공부해보겠습니다.

참조

• Queue
• 큐 (자료 구조)
• 시리즈:수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초
• 강의노트 20. 자료구조 - queue(큐)
• 자료구조(큐, queue)
• (JavaScript) 자바스크립트 큐(Queue, FIFO) 자료구조 구현
• [자바스크립트] Queue 큐 클래스
• Queue, Stack, Linked List 정리
• 큐, 스택, 트리