이전에는 몰랐지만, 자료 구조를 공부하다보니 자바스크립트 배열의 push와 pop 메소드로 스택을, push, shift 메소드로 큐를 알게 모르게 사용하고 있었다는 것을 알게 되었다. 사실 이처럼 자바스크립트에서는 배열이 있기 때문에 스택과 큐를 따로 구현하지 않아도 되지만, shift로 경우 배열 맨 앞에 값을 추가하게 되면 배열의 길이 만큼 기존 요소들을 앞으로 당겨줘야 하므로 성능이 좋지 않다. 그래서 이번 기회에 스택과 큐의 구조를 이해하는 측면에서 배열을 사용하지 않고 구현해봤다.
해당 자료 구조가 가지는 속성과 메소드는 어떻게 구현하느냐에 따라 더 구체적일 수 있으므로, 나는 기본적으로 꼭 필요한 것들만 포함했다.
먼저, 스택과 큐에 대해 자세히 알아보자.
스택(Stack)
컨셉
스택은 Last in, First out 원칙으로 만들어진 자료 구조다. 즉, 가장 나중에 들어온 데이터가 먼저 나가야 그 전에 들어온 데이터들이 나갈 수 있는 구조로, 출입구가 동일한 것이 특징이다. 함수 실행 콘텍스트들이 쌓이는 Call stack과 브라우저의 방문 기록이 쌓이는 History stack이 대표적이다.
속성
top: 스택 맨 위의 아이템
메소드
push: 스택의 맨 위에 아이템을 삽입한다pop: 스택 맨 위의 아이템을 제거하고 및 그 아이템을 반환한다contains: 해당 아이템이 스택에 존재하는지 확인한다size: 현재 스택에 있는 아이템의 총 개수를 반환한다
큐(Queue)
컨셉
큐는 First in, First out 원칙으로 만들어진 자료구조이다. 즉 먼저 들어온 데이터가 먼저 나가게 된다. 스택과 달리 큐는 입구와 출구가 구분되어 있기 때문에, 입구로 들어온 데이터는 반드시 반대쪽 출구로 나가야만 한다. 자바스크립트 엔진에서 비동기 함수 실행시 콜백들이 대기열로 들어오는 Task queue가 대표적이다.
속성
first: 큐 맨 앞의 아이템
메소드
enqueue: 큐에 아이템을 추가한다dequeue: 큐 맨 앞의 아이템을 제거하고 및 그 아이템을 반환한다contains: 해당 아이템이 큐에 존재하는지 확인한다size: 현재 큐에 있는 아이템의 총 개수를 반환한다
스택 구현하기
배열을 이용하지 않고 구현하기 위해 연결 리스트 방식을 이용했다.
class Stack {
constructor() {
this.top = null;
}
makeNode(value) {
return {
value,
below: null,
};
}
push(...values) {
for (let value of values) {
const node = this.makeNode(value);
if (this.top === null) {
this.top = node;
} else {
node.below = this.top;
this.top = node;
}
}
}
pop() {
if (this.size() === 0) return;
let popped;
if (this.top && this.top.below) {
popped = this.top;
this.top = this.top.below;
} else {
popped = this.top;
this.top = null;
}
return popped.value;
}
contains(value) {
let clone = this.top;
while (clone !== null) {
if (clone.value === value) {
return true;
}
clone = clone.below;
}
return false;
}
size() {
let count = 0;
let clone = this.top;
while (clone !== null) {
count += 1;
clone = clone.below;
}
return count;
}
}스택으로 큐 구현하기
2개의 스택을 이용해 계량컵에 옮기듯 아이템들을 이동시켜 큐를 구현하는 방법이다. 이미 구현한 Stack을 통해 아이템을 추가(enqueue) 하기 위해 메인으로 사용할 스택(inbox)과 삭제(dequeue) 하기 위해 서브로 사용할 스택(outbox)을 만들어 사용한다.
class Queue {
constructor() {
this.inbox = new Stack();
this.outbox = new Stack();
}
enqueue(value) {
this.inbox.push(value);
}
dequeue() {
const size = this.inbox.size();
let temp_size = size;
while (temp_size > 0) {
this.outbox.push(this.inbox.pop());
temp_size -= 1;
}
const dequeued = this.outbox.pop();
temp_size = size - 1;
while (temp_size > 0) {
this.inbox.push(this.outbox.pop());
temp_size -= 1;
}
return dequeued;
}
contains(value) {
return this.inbox.contains(value);
}
size() {
return this.inbox.size();
}
}참고
