[자료구조] 자바스크립트로 스택(Stack) 구현하기

스택(Stack)

블록을 아래에서 부터 위로 쌓아 올리는 구조를 가지고 있습니다. 가장 마지막에 삽입한 데이터를 가장 먼저 사용하게 됩니다.

이러한 자료구조의 특성을 LIFO(Last-in, First-out)라고 합니다.

 

출처: https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90

 

시간 복잡도
삽입 O(1)
삭제 O(1)
검색 O(n)

삽입과 삭제는 맨 위에서 모두 진행이 되기 때문에 O(1)의 시간복잡도를 가집니다.

검색은 스택안의 데이터를 찾을 때 까지 진행되기 때문에 O(n)의 시간복잡도를 가지게 됩니다.

자바스크립트 코드

스택은 자바스크립트에서 쉽게 구현할 수 있습니다.

자바스크립트 내장 메소드인 pop()과 push()를 이용하면 됩니다.

 

자바스크립트에서 배열을 하나 생성하고,

아이템을 넣고 싶다면 push(아이템)

아이템을 빼고 싶다면 pop()

을 해주면 됩니다.

 

배열로 구현

간단히 10만개의 아이템을 넣고 빼는 시간을 측정해봤습니다.

배열로 구현했을 때입니다.

const iter = 100000;
let start = new Date();
let end = new Date();

const arr = [];

start = new Date();
for (let i = 0; i < iter; i += 1) arr.push(i);
end = new Date();

console.log(`push ${iter}: ${end - start}ms`);

start = new Date();
for (let i = 0; i < iter; i += 1) arr.pop();
end = new Date();

console.log(`pop ${iter}: ${end - start}ms`);

push()는 7ms, pop()은 2ms로 조금 차이가 납니다.

 

노드로 구현

const iter = 100000;
let start = new Date();
let end = new Date();

class Node {
	constructor(item) {
		this.item = item;
		this.prev = null;
	}
}

class Stack {
	constructor() {
		this.top = null;
		this.size = 0;
	}

	push(item) {
		const node = new Node(item);
		if (!this.size) this.top = node;
		else {
			node.prev = this.top;
			this.top = node;
		}
		this.size += 1;
	}

	pop() {
		if (!this.size) return null;
		
		const pop = this.top;
		this.top = this.top.prev;
		this.size -= 1;
		return pop.item;
	}
}

const stack = new Stack();

start = new Date();
for (let i = 0; i < iter; i += 1) stack.push(i);
end = new Date();

console.log(`stack push ${iter}: ${end - start}ms`);

start = new Date();
for (let i = 0; i < iter; i += 1) stack.pop();
end = new Date();

console.log(`stack pop ${iter}: ${end - start}ms`);

혹시나 차이가 있을까해서 노드로 직접 넣고 빼는 스택 클래스를 만들어보았습니다.

결과는 아래와 같습니다!

 

무슨이유에서인지 제가 구현한 스택보다 배열을 이용한 스택이 조금 더 빠른 것을 볼 수 있습니다.

 

자바스크립트에서 스택을 구현할 때에는 배열로 하는 것이 좋아보입니다.

 

추천 문제

https://www.acmicpc.net/problem/10828

10828번: 스택