<div id="readability-page-1" class="page"><div><h3 id="1-adtabstract-data-type-or-추상-자료형">1. ADT(Abstract Data Type) or 추상 자료형</h3>
<blockquote>
데이터의 구체적인 구현 방식은 생략하고 데이터의 추상적 형태와 다루는 방법만 정한 것이다.
</blockquote>
<ul>
<li>큐(Queue), 스택(Stack), 트리(Tree)</li>
</ul>
 
<hr>
 
<h3 id="2-큐queue--bfs--우선순위-큐">2. 큐(Queue) :: BFS &amp; 우선순위 큐</h3>
<blockquote>
데이터를 넣을 수 있는 선형 자료형이다.
FIFO(First In First Out) 먼저 넣은 데이터가 먼저 나온다.
</blockquote>
<ul>
<li>head - dequeue 했을 때 출력 (front, first)</li>
<li>tail - enqueue 했을 때 입력 (rear, back, last)</li>
<li>enqueue - 데이터 넣음 <code>arr.push(item)</code></li>
<li>dequeue - 데이터 추출 <code>arr.shift( )</code><ul>
<li>배열이 비어있을 경우 <code>return undefined</code></li>
</ul></li>
<li>length - 데이터 길이 <code>arr.length</code></li>
<li>peek - 다음 데이터 확인 <code>arr[0]</code><ul>
<li>배열이 비어있을 경우 <code>return undefined</code></li>
</ul></li>
<li>isEmpty - 큐가 비어있는지 확인 <code>arr.length === 0</code></li>
<li>clear - 큐 초기화 <code>arr = [ ]</code></li>
</ul>
<pre><code>class Queue {
 constructor() {
 this.arr = [];
 }

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

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

 length() {
 return this.arr.length;
 }

 peek() {
 return this.arr[0];
 }

 isEmpty() {
 return this.arr.length === 0;
 }

 clear() {
 this.arr = [];
 }
}

const queue = new Queue();

// 데이터 삽입
queue.enqueue(1); // arr: [1]
queue.enqueue(20); // arr: [1, 20]
queue.enqueue(300); // arr: [1, 20, 300]

// 데이터 추출
queue.dequeue(); // 1

// 현재 큐 길이
queue.length(); // 2

// 다음에 추출될 데이터
queue.peek(); // 20

// 큐가 비어있는지 확인
queue.isEmpty(); // false

// 큐 초기화
queue.clear();</code></pre>
<h4 id="참고-자료-">참고 자료 📩</h4>
<a href="https://helloworldjavascript.net/pages/282-data-structures.html">큐, 스택, 트리 | JavaScript로 만나는 세상</a>
<a href="https://sub0709.tistory.com/147">[javascript] Queue 와 Stack 구현</a>
<a href="https://khwan.kr/blog/javascript/2020-03-14-queue-stack/">JavaScript로 구현해보는 큐(Queue), 스택(Stack)</a>
 
<hr>
 
<h3 id="3-심화">3. 심화</h3>
<ul>
<li><code>shift( )</code>를 사용할 경우 <code>array</code> 첫 번째 <code>index</code>가 빠져나가기 때문에 모든 원소들을 앞으로 한 칸씩 이동(나머지 배열 원소에 대한 재정렬)한다.</li>
</ul>
<blockquote>
<code>O(1)</code>이 걸려야 할 것이, <code>O(N)</code>이 걸리게 된다.
</blockquote>
<ul>
<li><code>shift( )</code> 메서드의 내부 로직<ol>
<li>배열의 첫 번째 원소&nbsp;<code>arr[0]</code>에 접근하여 해당 값을 반환하고 배열에서 제거한다.</li>
<li>기존 배열에서 첫 번째 원소&nbsp;<code>arr[0]</code>의 값은 사라졌지만 공간은 차지하고 있다.</li>
<li><code>shift()</code>&nbsp;메서드는 계속해서&nbsp;<code>arr[0]</code>에 접근한다.</li>
<li>따라서 나머지 배열의 원소들을 앞으로 한 칸씩 당겨주는 과정 필요하다.</li>
</ol></li>
</ul>
<pre><code>// 각각의 Node, Node의 data와 다음 Node 설정
class NodeQueue {
 constructor(data) {
 this.data = data;
 this.next = null;
 }
}

class Queue {
 constructor() {
 this.head = null; // 제일 앞 Node
 this.tail = null; // 제일 뒤 Node
 this.length = 0; // Node의 길이
 }

 enqueue(data) {
 // Node 추가
 let nodeQueue = new NodeQueue(data); // data를 가진 Node 생성

 if (!this.head) {
 // head가 없을 경우 해당 Node로 설정
 this.head = nodeQueue;
 } else {
 this.tail.next = nodeQueue; // 아닐 경우 마지막의 다음 Node로 설정
 }

 this.tail = nodeQueue; // 마지막을 해당 Node로 설정
 this.size++;
 }

 dequeue() {
 // Node 삭제
 if (this.size == 0) {
 // head가 없으면 한 개도 없는 것이므로 null 반환
 return null;
 }

 let data = this.head.data; // head를 head의 다음 것으로 바꾸고 제거한 value 반환
 this.head = this.head.next;
 this.size--;

 if (this.size == 0) {
 this.tail = null;
 }

 return data;
 }

 getQueue() {
 // queue 모든 원소 반환
 if (!this.head) return null;

 let node = this.head;
 const array = [];

 while (node) {
 // Node가 없을 때까지 array에 추가한 후 반환
 array.push(node.data);
 node = node.next;
 }

 return array;
 }

 isEmpty() {
 return this.size == 0;
 }
}</code></pre>
<pre><code>start = new Date();
let maxNum = 100000;

let q = new Queue();
for (let i = 0; i &lt; maxNum; i++) {
 q.enqueue(1);
}

end = new Date();
console.log(`enqueue ${maxNum} elements ${end - start}ms`);

start = new Date();
for (let i = 0; i &lt; maxNum; i++) {
 q.dequeue();
}

end = new Date();
console.log(`dequeue ${maxNum} elements ${end - start}ms`);</code></pre>
<h4 id="참고-자료--1">참고 자료 📩</h4>
<a href="https://medium.com/@songjaeyoung92/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-javascript-queue-%EB%9E%80-dbd8b2fffeac">[자료구조][Javascript] Queue 란?</a>
<a href="https://blue-jay.tistory.com/30">JavaScript Queue 구현</a>

<a href="https://velog.io/@longroadhome/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-JS%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-.%ED%81%90-Queue">[자료구조] JS로 구현하는 큐 (Queue)</a></div></div>

mnz.log

1. ADT(Abstract Data Type) or 추상 자료형
데이터의 구체적인 구현 방식은 생략하고 데이터의 추상적 형태와 다루는 방법만 정한 것이다.
큐(Queue), 스택(Stack), 트리(Tree)
2. 큐(Queue) :: BFS & 우선순위 큐
데이터를 넣을 수 있는 선형 자료형이다.
FIFO(First In First Out) 먼저 넣은 데이터가 먼저 나온다.
head - dequeue 했을 때 출력 (front, first)
tail - enqueue 했을 때 입력 (rear, back, last)
enqueue - 데이터 넣음 arr.push(item)
dequeue - 데이터 추출 arr.shift( )
배열이 비어있을 경우 return undefined
length - 데이터 길이 arr.length
peek - 다음 데이터 확인 arr[0]
배열이 비어있을 경우 return undefined
isEmpty - 큐가 비어있는지 확인 arr.length === 0
clear - 큐 초기화 arr = [ ]
class Queue {
 constructor() {
 this.arr = [];
 }
 enqueue(value) {
 this.arr.push(value);
 }
 dequeue() {
 return this.arr.shift();
 }
 length() {
 return this.arr.length;
 }
 peek() {
 return this.arr[0];
 }
 isEmpty() {
 return this.arr.length === 0;
 }
 clear() {
 this.arr = [];
 }
}
const queue = new Queue();
// 데이터 삽입
queue.enqueue(1); // arr: [1]
queue.enqueue(20); // arr: [1, 20]
queue.enqueue(300); // arr: [1, 20, 300]
// 데이터 추출
queue.dequeue(); // 1
// 현재 큐 길이
queue.length(); // 2
// 다음에 추출될 데이터
queue.peek(); // 20
// 큐가 비어있는지 확인
queue.isEmpty(); // false
// 큐 초기화
queue.clear();
참고 자료 📩
큐, 스택, 트리 | JavaScript로 만나는 세상
[javascript] Queue 와 Stack 구현
JavaScript로 구현해보는 큐(Queue), 스택(Stack)
3. 심화
shift( )를 사용할 경우 array 첫 번째 index가 빠져나가기 때문에 모든 원소들을 앞으로 한 칸씩 이동(나머지 배열 원소에 대한 재정렬)한다.
O(1)이 걸려야 할 것이, O(N)이 걸리게 된다.
shift( ) 메서드의 내부 로직
배열의 첫 번째 원소 arr[0]에 접근하여 해당 값을 반환하고 배열에서 제거한다.
기존 배열에서 첫 번째 원소 arr[0]의 값은 사라졌지만 공간은 차지하고 있다.
shift() 메서드는 계속해서 arr[0]에 접근한다.
따라서 나머지 배열의 원소들을 앞으로 한 칸씩 당겨주는 과정 필요하다.
// 각각의 Node, Node의 data와 다음 Node 설정
class NodeQueue {
 constructor(data) {
 this.data = data;
 this.next = null;
 }
}
class Queue {
 constructor() {
 this.head = null; // 제일 앞 Node
 this.tail = null; // 제일 뒤 Node
 this.length = 0; // Node의 길이
 }
 enqueue(data) {
 // Node 추가
 let nodeQueue = new NodeQueue(data); // data를 가진 Node 생성
 if (!this.head) {
 // head가 없을 경우 해당 Node로 설정
 this.head = nodeQueue;
 } else {
 this.tail.next = nodeQueue; // 아닐 경우 마지막의 다음 Node로 설정
 }
 this.tail = nodeQueue; // 마지막을 해당 Node로 설정
 this.size++;
 }
 dequeue() {
 // Node 삭제
 if (this.size == 0) {
 // head가 없으면 한 개도 없는 것이므로 null 반환
 return null;
 }
 let data = this.head.data; // head를 head의 다음 것으로 바꾸고 제거한 value 반환
 this.head = this.head.next;
 this.size--;
 if (this.size == 0) {
 this.tail = null;
 }
 return data;
 }
 getQueue() {
 // queue 모든 원소 반환
 if (!this.head) return null;
 let node = this.head;
 const array = [];
 while (node) {
 // Node가 없을 때까지 array에 추가한 후 반환
 array.push(node.data);
 node = node.next;
 }
 return array;
 }
 isEmpty() {
 return this.size == 0;
 }
}
start = new Date();
let maxNum = 100000;
let q = new Queue();
for (let i = 0; i < maxNum; i++) {
 q.enqueue(1);
}
end = new Date();
console.log(`enqueue ${maxNum} elements ${end - start}ms`);
start = new Date();
for (let i = 0; i < maxNum; i++) {
 q.dequeue();
}
end = new Date();
console.log(`dequeue ${maxNum} elements ${end - start}ms`);
참고 자료 📩
[자료구조][Javascript] Queue 란?
JavaScript Queue 구현
[자료구조] JS로 구현하는 큐 (Queue)

[Data Structure] 큐(Queue) - JS

댓글