[Data Structure] 선형 - Queue(큐)

Queue (큐)

• 스택과 반대로 먼저 저장된 것이 제일 먼저 나온다. 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
• 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out) 또는 LILO(Last-In, Last-Out) 방식.

 

Ex) 큐 구현

javascript

닫기 줄바꿈

class Queue {
​​constructor() {
​​​​this.storage = {}; // 여기에 담는다.
​​​​this.front = 0;
​​​​this.rear = 0;
​​}

​​size() {
​​​​return Object.keys(this.storage).length;
​​}
‌
​​// 큐에 데이터를 추가 할 수 있어야 한다.
​​enqueue(element) {
​​​​this.storage[this.rear] = element;
​​​​this.rear += 1;
​​}
‌
​​// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 한다.
​​dequeue() {
​​​​// 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 한다.
​​​​if (Object.keys(this.storage).length === 0) {
​​​​​​return;
​​​​}

​​​​const result = this.storage[this.front];
​​​​delete this.storage[this.front];
​​​​this.front += 1;

​​​​return result;
​​}
}

적용

javascript

닫기 줄바꿈

const queueData = new Queue;
queueData.enqueue('a'); //'a'를 넣는다
queueData.enqueue('b'); //'b'를 넣는다
queueData.enqueue('c'); //'c'를 넣는다
console.log(queueData); // {storage: {…}, front: 0, rear: 3}
// storage: {0: "a", 1: "b", 2: "c"}
console.log(queueData.size()); // 큐의 길이는 3
queueData.dequeue(); // 콘솔에는 'a'가 찍힌다
console.log(queueData); // {storage: {…}, front: 1, rear: 3}
// storage: {1: "b", 2: "c"}
// 즉 먼저 삽입된 'a'가 빠진 것을 알 수 있다.