- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)
스택은 '후입선출'의 자료구조이다.
스택의 예시
콜스택(호출된 함수들의 자료 구조)
실행취소(ctrl + z)
브라우저의 history 객체
스택의 경우 굳이 자료구조를 따로 만들지 않아도 자바스크립트의 내장 배열로도 충분히 구현이 된다.
push, pop조합과 unshift, shift조합으로 구현할 수 있는데, shift와 unshift가 인덱스의 재정렬 때문에 n의 시간 복잡도를 갖는 것을 고려하면, 전자의 조합을 사용하는 게 타당하다
자바스크립트 내장 배열로 스택을 구현할 때는 push와 pop을 활용하는 게 더 타당하다고 했지만, 지난 포스팅에서 살펴 봤듯이 단일 연결 리스트에서 pop은 n의 시간 복잡도를 갖는다.
이중 연결 리스트를 활용하면 이 문제를 해결할 수 있지만, 알다시피 이중 연결 리스트는 메모리를 두 배로 사용한다는 단점이 있다.
그렇기에 단일 연결 리스트의 shift와 unshift의 조합으로 스택을 구현하는 게 최선이라고 판단된다.
const Node = {
init: function (val) {
this.val = val;
this.next = null;
},
};
const Stack = {
init: function () {
this.first = null;
this.last = null;
this.size = 0;
},
push: function (val) {
const newNode = Object.create(Node);
newNode.init(val);
if (!this.last) {
// last가 없다는 것은 push한 노드가 first이자 last이 되어야 한다는 것
this.first = newNode;
this.last = newNode;
} else {
newNode.next = this.last;
this.last = newNode;
}
this.size++;
return this;
},
pop: function () {
if (!this.last) {
// last가 없다는 것은 더 이상 pop할 노드가 없다는 것
return;
}
const oldLast = this.last;
if (this.size == 1) {
this.first = null;
this.last = null;
} else {
this.last = oldLast.next;
oldLast.next = null;
}
this.size--;
return oldLast;
},
};
const stack = Object.create(Stack);
stack.init();
다만, 주의할 것은 여기서 first와 last의 방향은 단일 연결 리스트의 head와 tail의 방향과는 반대라는 것이다.
last in first out(후입선출)의 개념에 혼동을 주지 않기 위해 이렇게 하는 게 맞다고 판단했다.
큐는 '선입선출'의 자료구조이다.
큐의 예시
백그라운드 작업
자료 업로딩
프린트
큐 역시 스택과 마찬가지로 자바스크립트 내장 배열로 구현할 수 있으며, shift와 push조합 또는 unshift와 pop조합을 사용하면 된다.
다만, stack과는 달리 어느 조합을 사용하더라도 인덱스의 재정렬을 피할 수 없기 때문에 자료 구조를 직접 구현하는 편이 바람직하다.
const Node = {
init: function (val) {
this.val = val;
this.next = null;
},
};
const Queue = {
init: function () {
this.first = null;
this.last = null;
this.size = 0;
},
enqueue: function (val) {
const newNode = Object.create(Node);
newNode.init(val);
if (!this.last) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
this.size++;
return this;
},
dequeue: function () {
if (!this.last) {
return;
}
const oldFirst = this.first;
if (this.size == 1) {
this.first = null;
this.last = null;
} else {
this.first = oldFirst.next;
oldFirst.next = null;
}
this.size--;
return oldFirst;
},
};
const queue = Object.create(Queue);
queue.init();