javascript의 Array를 사용하지 않고 Stack 자료구조를 구현해보자.
스택
참고 : 스택과 큐
스택은 나중에 들어간 것이 (Last-In) 먼저 나오는 (First-Out) LIFO 형태의 자료구조이다. 링크드 리스트를 이용해 구현해볼 것이다.
Interface
인터페이스는 일종의 규약으로 이를 사용해 특정 형식의 클래스를 만들 것이라고 규정할 수 있다.
1
2
3
4
5
interface Stack {
size: number;
push(value: string): void;
pop(): string;
}
스택의 사이즈와 push메서드 (스택에 데이터를 넣음), pop메서드 (스택에서 데이터를 꺼냄) 를 클래스 안에 작성할 것이라고 인터페이스를 이용해 규정했다.
1
2
3
4
5
6
7
8
class StackImple implements Stack {
private _size: number = 0;
get size() {
return this._size;
}
push(value: string): void {}
pop(): string {}
}
인터페이스에 맞는 형식의 클래스를 작성했다. size는 private 프로퍼티로 외부에서 읽을 수 없다. getter를 이용해 외부에서 size를 읽을 수 있게 한다. 클래스의 멤버 변수와 중복되는 값이 있을 땐 _를 이용해 구별한다.
Node
새로 들어온 데이터는 Node에 저장되고 head가 이 Node를 가리킨다. 새로운 Node가 들어오면 head는 이 Node를 가리키고 이 Node는 이전의 Node를 가리키면서 서로 연결된다.
type을 이용해 이 Node의 타입을 정의한다.
1
2
3
4
5
6
type StackNode = {
value: string;
next?: StackNode;
};
const node: StackNode = { value, next: StackNode };
제일 처음 생긴 Node는 이전의 Node가 없어 가리킬 Node가 없으므로 next값이 없다. optional로 지정해 next의 타입을 StackNode 혹은 undefined가 되도록 한다.
PUSH
1
2
3
4
5
6
7
8
9
10
11
12
13
class StackImple implements Stack {
private _size: number = 0;
private head: StackNode;
get size() {
return this._size;
}
push(value: string): void {
const node: StackNode = { value, next: this.head };
this.head = node;
this._size++;
}
pop(): string {}
}
클래스 멤버 변수인 head에 제일 최근의 Node를 저장하고 사이즈를 +1 해준다.
POP
push와 반대로 head가 이전 Node를 가리키게 변경하고 사이즈를 -1 해준다.
1
2
3
4
5
6
pop(): string {
const node = this.head;
this.head = node.next;
this._size --;
return node.value
}
이 때, this.head의 타입은 StackNode로 undefined일 수 있기 때문에 (스택이 비어있을 경우 head는 어떤 Node도 가리키지 않은 상태이기 때문에) if문을 이용해 예외처리를 해준다.
1
2
3
4
5
6
7
8
9
pop(): string {
if(this.head === null) {
throw new Error("Stack is empty")
}
const node = this.head;
this.head = node.next;
this._size --;
return node.value
}
정리
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
29
30
31
32
33
34
35
36
37
38
39
interface Stack {
readonly size: number;
push(value: string): void;
pop(): string;
}
type StackNode = {
readonly value: string;
readonly next?: StackNode;
};
class StackImple implements Stack {
private _size: number = 0;
private head?: StackNode;
get size() {
return this._size;
}
constructor(private capacity: number) {}
push(value: string): void {
if (this._size === this.capacity) {
throw new Error("Stack is full");
}
const node: StackNode = {
value,
next: this.head
};
this.head = node;
this._size++;
}
pop(): string {
if (this.head == null) {
throw new Error("Stack is empty");
}
const node = this.head;
this.head = node.next;
this._size--;
return node.value;
}
}
constructor에 capacity를 추가해 스택의 용량을 지정했고 push할 때 스택이 가득 차있을 경우 에러가 발생하도록 예외 처리를 해주었다.