자료구조 ] Queue

Linear Queue

정의

---

한쪽 끝(rear)에서는 삽입 연산만 이루어지며, 다른 한쪽 끝(front)에서는 삭제 연산만 이루어지는 유한 순서 리스트이다.

특징 / 특이사항

---

구조상 먼저 삽입된 item이 먼저 삭제가 이루어진다. ( FIFO )

용어

---

이름	설명
front(head)	데이터를 추출하는 위치
rear(tail)	데이터를 삽입할 수 있는 위치
overflow	큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우
enqueue	삽입
dequeue	추출

메서드 & 시간 복잡도

---

메서드 이름	메서드 설명	시간복잡도	시간복잡도 이유
enqueue(v)	큐에 값을 추가	O(1)
dequeue()	큐에서 값을 추출	O(n) / O(1)	배열로 구현하면 앞의 데이터가 추출된 후 나머지 데이터가 한 칸씩 앞으로 옮겨와야하므로 O(n) 시간 복잡도를 가진다. 연결리스트로 구현하면 O(1)의 복잡도를 가질 수 있다.
peek()	큐에서 값을 추출(제거 하지 않음)	O(1)
isEmpty()	현재 큐가 비어있는지 확인	O(1)
size()	현재 큐에 들어있는 데이터 원소의 수	O(1)

활용

---

데이터가 들어온 순서대로 처리해야 할 필요가 있을 때 이용한다.

ex ) 프로세스 관리

종류

---

1) Linear Queue (선형 큐)

• 기본적인 큐의 형태로 막대 모양으로 된 큐이다.
• dequeue를 할 때, 모든 데이터를 한 칸씩 앞으로 옮겨야 하는 문제점을 안고 있다.

 

2) Circular Queue (원형 큐)

• 선형 큐의 문제점을 보완하기 위해 나왔다.

Circular Queue

 

3) Priority Queue (우선순위 큐)

• 큐에서 dequeue 될 때, 우선순위에 맞게 나간다.
• 막대 모양으로 구현했을 때 성능이 저하되므로 일반적으로 힙(완전 이진트리) 모양으로 구현한다.
• [ 추후 추가 내용 넣을 예정 ]

 

---

Javascript Queue 구현 방법

---

1) 선형 큐 구현

     막대 모양을 배열을 통해 구현하거나, 연결 리스트 형태로 구현할 수 있다.

 

○ 배열 형태

배열의 기본 메서드를 이용하여 구현한다.

---

• shift() : array의 0번째 데이터를 반환한다.
  • 가장 queue 답게 사용할 수 있는 메서드이다. 하지만, 0번째 데이터가 반환되면서 나머지 값들이 앞으로 하나씩 옮기게 되므로 시간 복잡도가 O(n)이 됨을 기억하여 사용해야 한다.  

class Queue {
  constructor() {
	this.arr = [];
  }

  enqueue(value){
  	this.arr.push(value)
  }

  dequeue(){
  	return this.arr.shift();
  }	

}

 

• slice() : 원본 배열에서 [begin] ~ [end -1]까지의 요소의 얕은 복사본을 반환한다.
  • 배열의 첫 번째를 선택하여 반환하고, 남은 배열의 얕은 복사본을 할당한다.

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

// arr.slice([begin[, end]])

const enqueue = (value) => {
	arr.push(value)
}

const dequeue = () => {
	const data = arr[0];
    arr = arr.slice(1);
    return data;
}

 

• splice() : 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경한다. 삭제할 때 제거한 요소를 반환한다. 
  • 배열의 첫 번째를 삭제한 후 반환하면, 삭제되지 않는 요소만 남는다.

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];

// arr.splice(start[, deleteCount[, item1[, item2[, ...]]]])

const enqueue = (value) => {
  arr.push(value);
};

const dequeue = () => {
  return arr.splice(0, 1)[0];
};

○ Linked list(연결 리스트) 형태

클래스를 이용하여 구현한다. 

---

클래스 하나가 하나의 노드가 되어서 각각 데이터와 다음 데이터의 정보를 가지고 있는다. 

dequeue()를 진행할 때 O(1)의 시간 복잡도를 가질 수 있다. 

class Node {
  constructor(value) {
    this.data = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.last = null;
    this.length = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (this.length === 0) {
      this.head = newNode;
    } else {
      this.last.next = newNode;
    }
    this.last = newNode;
    this.length += 1;
  }

  dequeue() {
    if (!this.head) {
      return null;
    }

    const data = this.head.data;
    this.head = this.head.next;
    this.length -= 1;

    return data;
  }

  peek() {
    return this.head.data;
  }

  isEmpty() {
    return !this.head;
  }

  size() {
    return this.length;
  }
}

 

---

2) 원형 큐 구현

     막대 모양을 배열을 통해 구현하거나, 연결 리스트 형태로 구현할 수 있다.

     연결리스트 형태는 막대 모양에서도 앞으로 한 칸씩 옮겨야 하는 문제점이 없으므로 배열형태만 기술한다.

 

○ 배열 형태 

배열의 사이즈를 지정한 후, 배열의 크기가 넘어가는 데이터는 들어갈 수 없도록 구현한다.

---

구현 시 고려해야 할 점

1 ]  정해진 배열 사이즈 안에서만 데이터가 들어오고 나갈 수 있도록, 나머지 연산자를 이용하여 index를 계산한다.

ex > 정수를 6으로 나누면 나머지는 항상 0 ~ 5이다. 

                정수  :  0  1  2  3  4  5  6  7  8  9  10  11  12  13...
------------------------------------------------------------------------------- 
6으로 나눈 나머지 : 0  1   2  3  4  5  0  1  2  3  4    5    6    7

2 ] dequeue 없이 계속 enqueue 만 해 나갈 경우(데이터가 full로 차 있을 때), rear과 front가 만나게 된다.

    이 상태는 원형 큐가 비어있을 경우를 뜻할 때와 같으므로, 이를 해결하기 위해 배열 사이즈를 1크게 만들어 끝에 하나의 빈칸을 만들어 구현한다. 

ex > 크기가 5인 queue를 만들 때 

[ '1', '2', '3', '4', '5', null ]

 

class CircularQueue {
	_size = 0;
	_data = null;
	_front = 0;
	_rear = 0;

	constructor(size = 0) {
		this._size = size + 1;
		this._data = new Array(this._size).fill(null);
	}

	isEmpty() {
		return this._rear === this._front;
	}

	isFull() {
		return (this._rear + 1) % this._size === this._front;
	}

	enqueue(v) {
		if (this.isFull()) {
			console.log("Failed enqueue. It's full");
			return;
		}
		this._data[this._rear] = v;
		this._rear = (this._rear + 1) % this._size;
	}

	dequeue() {
		if (this.isEmpty()) {
			console.log("Failed dequeue. It's empty");
			return;
		}
		const v = this._data[this._front];
		this._data[this._front] = null;
		this._front = (this._front + 1) % this._size;
		return v;
	}

	peek() {
		return this._data[this._front];
	}

	size() {
		return this._rear > this._front 
                 ? this._rear - this._front 
                 : this._size - (this._front - this._rear);
	}
}

 

코드 실행결과 : 데이터의 마지막은 null을 가진 채로 원처럼 회전하며 데이터가 채워져 간다.

const cq = new CircularQueue(5);
cq.enqueue('1');
cq.enqueue('2');
cq.enqueue('3');
cq.enqueue('4');
cq.enqueue('5');
cq.enqueue('6');
cq.enqueue('7');

 

const cq = new CircularQueue(5);
cq.enqueue('1');
cq.enqueue('2');
cq.enqueue('3');
cq.enqueue('4');
cq.enqueue('5');
console.log('value: ', cq.dequeue());
console.log('value: ', cq.dequeue());

 

const cq = new CircularQueue(5);
cq.enqueue('1');
cq.enqueue('2');
cq.enqueue('3');
cq.enqueue('4');
cq.enqueue('5');
console.log('value: ', cq.dequeue());
console.log('value: ', cq.dequeue());
cq.enqueue('7');
cq.enqueue('8');
cq.enqueue('9');