자바스크립트로 스택 구현하기
백준 10828번 스택 문제와도 같다.
본문은 서적
Data Structures and Algorithms with JavaScript(Michael McMillan)의Chapter 4. Stack을 정리한 내용이다.
1. 스택(Stack)이란?
스택은 요소들의 배열로, 스택의 'top'이라고 부르는 배열의 한쪽 끝에 있는 요소만 접근할 수 있다는 특징이 있다.
즉 가장 끝(top 쪽)에 있는 요소만 빼낼 수 있으며, 새로운 요소는 가장 끝(top 쪽)에 들어간다.
이를 두고 last-in, first-out(LIFO) 자료 구조라고 부른다.
이 특징으로 인해 스택은 실행하기 쉽고 속도가 매우 빠르다는 장점을 갖는다.
2. 스택 연산(Stack operations)
스택의 주요 연산은 다음과 같다.
| - push: 요소를 스택에 넣는다 - pop: 스택의 가장 위에 있는 요소를 뺀다 - size: 스택에 들어있는 요소의 개수를 반환한다 - peek(백준 문제의 top): 스택의 가장 위에 있는 요소를 반환하되, 조회만 하고 스택에서 빼지는 않는다 |
3. 구현하기
다음과 같이 구현하면 된다.
| - dataStore(=스택): Array - push: Array의 push method - pop: Array의 pop method - size: Array의 length property - peek(백준 문제의 top): Array의 가장 마지막 요소(위치는 length - 1) 반환 |
구현은 백준 문제를 따랐다.
내가 참고한 서적은 function으로만 구현했는데... (출간한 지 좀 돼서인 것 같다)
class를 사용해서 구현해봤다.
|
class Stack {
constructor() {
this.dataStore = [];
}
get size() {
return this.dataStore.length;
}
get empty() {
if (this.size == 0){
return 1;
}
else {
return 0;
}
}
get top() {
if (this.size != 0) {
return this.dataStore[this.size - 1];
}
else {
return -1;
}
}
push(element) {
this.dataStore.push(element);
}
pop() {
if (this.size != 0){
this.dataStore.pop();
return this.dataStore[this.size - 1];
}
else {
return -1;
}
}
}
|
출력할 때 하나씩 console.log 하면 시간초과가 날 수 있으니 주의!
변수 하나에 계속 이어붙인 다음 한꺼번에 출력했더니 통과했다.
'front-end > Javascript' 카테고리의 다른 글
| 집합(Set)과 맵(Map) (0) | 2022.05.23 |
|---|---|
| 자바스크립트 자료 구조 - Lists (0) | 2022.04.20 |
| 웹페이지 로딩 화면 만들기 (0) | 2022.01.24 |