스택에 대해 알아보자.
스택 Stack
스택은 마지막에 삽입된 항목만을 제거하고 접근할 수 있는 LIFO(Last In First Out) 원리를 따르는 자료구조입니다.
스택의 추상 자료형 ADT
- push : 맨 마지막에 새로운 요소 삽입
- pop : 맨 마지막 요소 추출하고 반환
- peek : 맨 마지막 요소 확인
- isEmpty : 비어있는지 확인
- size : 요소 갯수 반환
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Stack {
#arr = [];
push(item) {
this.#arr.push(item);
}
pop() {
if (this.isEmpty()) {
throw new Error("Stack is empty");
}
return this.#arr.pop();
}
peek() {
if (this.isEmpty()) return null;
return this.#arr[this.size() - 1];
}
isEmpty() {
return this.#arr.length === 0;
}
size() {
return this.#arr.length;
}
}
push
새로운 요소를 삽입하는 것으로 Javascript의 배열이 기본 지원하는 push 메서드를 사용합니다.
1
2
3
4
5
6
7
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [1, 2, 3]
- 시간복잡도 : O(1)
pop
요소를 추출하는 것으로 Javascript의 배열이 기본 지원하는 pop 메서드를 사용합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [1, 2, 3]
stack.pop(); // 3
stack.pop(); // 2
stack.pop(); // 1
console.log(stack); // []
- 시간복잡도 : O(1)
peek
마지막 요소를 확인합니다.
1
2
3
4
5
const stack = new Stack();
stack.push(1);
console.log(stack.peek()); // 1
isEmpty
스택 안에 요소가 있는 지 확인합니다.
1
2
3
4
5
stack.isEmpty(); // true
stack.push(1);
stack.isEmpty(); // false
size
스택 안에 있는 요소들의 갯수를 반환합니다.
1
2
3
4
5
stack.push(1);
stack.push(2);
stack.push(3);
stack.size(); // 3