[JavaScript] JS로 Stack, Queue, Deque 구현하기

🟢 [1] Stack (LIFO)

'스택(Stack)'은 마지막에 들어간 데이터가 가장 먼저 나오는 후입선출(LIFO, Last-In First-Out) 방식입니다.

1️⃣ 삽입, 삭제

종류	문법	시간복잡도
삽입 (뒤)	stack.push(x)	O(1)
삭제 (뒤)	stack.pop()	O(1)

2️⃣ 예제

const stack = [1, 2, 3, 4];
stack.push(5);	// [1, 2, 3, 4, 5]
stack.pop();	// [1, 2, 3, 4]

🟢 [2] Queue (FIFO)

'큐(Queue)'는 들어온 순서대로 데이터가 처리되는 선입선출(FIFO, First-In, First-Out) 방식입니다.

1️⃣ 삽입, 삭제

종류	문법	시간복잡도
삽입 (뒤)	queue.push(x)	O(1)
삭제 (앞)	queue.shift()	O(n)

2️⃣ 예제

const queue = [1, 2, 3, 4];
queue.push(5);	// [1, 2, 3, 4, 5]
queue.shift();	// [2, 3, 4, 5]

🟢 [3] Deque

'덱(Deque)'은 'Double-ended queue'의 줄임말로, 양쪽 끝에서 데이터의 삽입과 삭제가 모두가능한 확장 형태의 자료 구조입니다.

1️⃣ 삽입, 삭제

종류	문법	시간복잡도
삽입 (뒤)	dq.push(x)	O(1)
삭제 (뒤)	dq.pop()	O(1)
삽입 (앞)	dq.unshift(x)	O(n)
삭제 (앞)	dq.shift(x)	O(n)

2️⃣ 예제

const dq = [2, 3, 4];
dq.push(5);		// [2, 3, 4, 5]
dq.pop();		// [2, 3, 4]
dq.unshift(1);	// [1, 2, 3, 4]
dq.shift();		// [2, 3, 4]