[JS 자료구조] 스택(Stack)과 큐(Queue) 를 참조했다.
스택
가장 마지막에 요소를 추가할 수 있고,
가장 마지막 요소를 제거할 수 있는 자료구조를 의미한다.
자바스크립트에서의 스택
지난번 글 연결리스트에서 언급한 것 처럼, 스택은 직접 구현하는 것보다 Array를 이용하는 것이 빠르다. 메모리를 캐싱할 수 있기 때문이다.
'후입선출'이라는 특성을 가지느 본 자료형은 데이터를 관리하는데에 주로 쓰일 수 있다.
가령 '콜 스택'은 먼저 '콜 된 함수'가 아래에 쌓인다.
'콜 된 함수가 콜 한 함수'는 위에 쌓인다.
'콜 된 함수가 콜 한 함수'가 일반적으로 '콜 된 함수'보다 먼저 끝나며,
그 이유는 '콜 된 함수'가 '콜 된 함수가 콜 한 함수'가 참조하는 변수를 가지고 있는, 즉 '렉시컬 환경'이 되기 때문이다. 렉시컬 환경으로서 참조되고 있는 함수와 그 변수들이 사라지면 안되잖아??
(function 콜된함수() {
let 콜된함수의변수 = 0
(function 콜된함수가콜한함수(){
let 콜된함수가콜한함수의변수 = 콜된함수의변수 + 1
(function 콜된함수가콜한함수가콜하는함수(){
console.log(콜된함수가콜한함수의변수) // 2
})()
})()
})()
자바스크립트의 실행 콘텍스트에는 이러한 구조를 관리하는 '외부 렉시컬 환경에 의한 참조'이 있으며,
결과적으로 '외부 렉시컬 환경에 의한 참조'의 연결리스트가 콜 스택이라 할 수 있다.
('외부 렉시컬 환경에 의한 참조'는 ES5 이전 버전의 '스코프 체인'이라고도 알려져 있다.)
스택의 ADT
변수
-
value : 각 노드가 가지는 값이다
-
next : 각 노드의 다음 노드를 지시하는 값이다.
-
first : 가장 마지막에 추가된 노드를 의미하는 리스트의 변수이다. (top이라고도 한다.)
-
last : 리스트의 가장 마지막에 있는 노드를 의미하는 리스트의 변수이다.
-
size : 리스트에 있는 노드의 전체 갯수를 의미한다.
연산
- push : first에 새로운 노드를 추가한다.
- pop : first의 노드를 제거한다. 만일 first와 last가 같은 상태에서 pop을 시행하면 해당 리스트는 비게 된다.
- isEmpty(선택) : last가 비어있는지를 의미하며, empty 상태일 때에 pop을 하면 에러를 발생시킨다.
array
계속 언급하듯, 일반적으로 Array를 쓰면 된다.
next : Arr[Arr.indexOf(value)+1]
first : Arr[0]
last : Arr[Arr.length -1] 혹은 Array.prototype.at(-1)
size : Array.prototype.length
push : Array.prototype.push(element)
pop : Array.prototype.pop()
큐
가장 앞에 데이터를 넣고, 가장 뒤의 데이터를 뺄 수 있는 자료구조이다.
'선입선출', 즉 먼저 넣은 데이터를 먼저 빼는 것이다.
자바스크립트의 큐
배열에서 shift나 unshift를 하면 배열 내부의 자료들의 인덱스를 바꿔주어야 한다.
스택 오버플로에 따르면, 크롬 v8 엔진은 shift나 unshift를 할 때에 자동으로 위치를 바꿔주기 때문에 성능상 문제가 생기는 경우는 드물다.
다만, 이러한 자동 할당을 위해서 Array가 충분한 여유 메모리를 확보하게 되고, 데이터의 양이 많아지면 메모리를 관리하기 위해 시간비용이 증가할 수 있다.
이론적으로 Array의 shift, unshift를 하면 (Array는 일반적으로 선형적인 자료 구조를 의미하므로) O(n)의 시간 복잡도를 지닌다. 연결 리스트를 활용하면 O(1)의 시간복잡도를 지닌다.
그리고 자바스크립트에서는 연결리스트를 활용한 방식이 Array를 활용할 때보다 약 40%~100%까지 더 빠르다.
자바스크립트에서 가장 유명한 큐 자료구조는 '콜백 큐'이다. 기초지식: Non-blocking I/O, 싱글 스레드, 노드JS의 특징에서 언급했듯, 비동기 요청들을 순차적으로 실행하고, 순차적으로 처리한다. (순차적으로 끝날지는 알 수 없지만...) 콜백 큐 이외에도 Node.js는 다양한 이벤트 큐를 가지고 있다.
네트워크 환경에서는 '버퍼'가 대표적으로 큐에 해당한다. 일반적으로 가장 먼저 쓰일 청크를 가장 먼저 호출하여 큐에 가장 저장하고 가장 먼저 사용한다.
큐의 ADT
스택과 비슷하다.
변수
-
value : 각 노드가 가지는 값이다
-
next : 각 노드의 다음 노드를 지시하는 값이다.
-
first : 가장 마지막에 추가된 노드를 의미하는 리스트의 변수이다. (top이라고도 한다.)
-
last : 리스트의 가장 마지막에 있는 노드를 의미하는 리스트의 변수이다.
-
size : 리스트에 있는 노드의 전체 갯수를 의미한다.
연산
- enqueue : first에 새로운 노드를 추가한다.
- dequeue : last의 노드를 제거한다. 만일 first와 last가 같은 상태에서 dequeue를 시행하면 해당 리스트는 비게 된다.
- isEmpty(선택) : last가 비어있는지를 의미하며, empty 상태일 때에 pop을 하면 에러를 발생시킨다.
연결 리스트를 이용한 구현
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
enqueue(val) {
const newNode = new Node(val);
if (!this.first) {
this.first = newNode;
this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
return ++this.size;
}
dequeue() {
if (!this.first) return null;
const temp = this.first;
if (this.first === this.last) {
this.last = null;
}
this.first = this.first.next;
this.size--;
return temp.value;
}
}
알고리즘 문제
프로그래머스 고득점 킷 - 스택/큐
1.같은 숫자는 싫어
2.기능개발
3.올바른 괄호
4.프린터
5.다리를 지나는 트럭
6.주식가격