공부/그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)
스택 - 개념
KDONG
2024. 1. 28. 23:08
스택(Stack) 이해와 구현
스택은 데이터를 제한된 방식으로 접근할 수 있는 선형 자료구조입니다. 스택은 특히 "First In Last Out(FILO)" 또는 "Last In First Out(LIFO)"의 특성을 가지며, 이는 가장 마지막에 쌓은 데이터를 가장 먼저 꺼낼 수 있다는 의미입니다. 일상생활에서 접시를 쌓는 것과 같이, 스택은 데이터의 추가와 삭제가 한 방향에서만 이루어지는 구조를 가지고 있습니다.
1. 스택의 기본 동작
스택의 기본적인 동작은 다음과 같습니다:
- push: 스택의 맨 끝에 데이터를 추가합니다.
- pop: 스택의 맨 끝에서 데이터를 꺼냅니다.
- peek: 스택의 맨 끝 데이터를 확인합니다.
- isEmpty: 스택이 비어 있는지 확인합니다.
2. 스택의 구현
연결리스트를 사용하여 스택을 구현할 수 있습니다. 이전 강의에서 구현한 연결리스트를 기반으로 스택을 구현해 보겠습니다. 스택은 연결리스트의 **head**를 사용하여, 데이터의 삽입과 삭제를 **head**에서만 수행하게 됩니다. 데이터의 삽입은 연결리스트의 insertAt 함수를 이용하여 **index 0**에 데이터를 삽입하고, 데이터의 삭제는 deleteAt 함수를 이용하여 **index 0**의 데이터를 삭제합니다.
// Stack.js
import LinkedList from './LinkedList.js';
class Stack {
constructor() {
this.linkedList = new LinkedList();
}
push(data) {
this.linkedList.insertAt(0, data);
}
pop() {
if (this.isEmpty()) {
throw new Error("스택이 비어있습니다.");
}
return this.linkedList.deleteAt(0).data;
}
peek() {
if (this.isEmpty()) {
throw new Error("스택이 비어있습니다.");
}
return this.linkedList.head.data;
}
isEmpty() {
return this.linkedList.count === 0;
}
print() {
this.linkedList.printAll();
}
}
3. 스택의 사용 예시
스택을 사용하여 코드에서 여는 괄호와 닫는 괄호의 쌍을 확인하는 간단한 예시를 만들어보겠습니다.
// test.js
import Stack from './Stack.js';
const stack = new Stack();
stack.push('{');
stack.push('(');
stack.push(')');
stack.push('}');
while (!stack.isEmpty()) {
console.log(stack.pop());
}
// 출력:
// }
// )
// (
// {
결론
스택은 데이터를 일시적으로 저장하면서 가장 최근에 추가된 데이터에 빠르게 접근할 수 있는 자료구조입니다. 스택은 프로그래밍에서 함수 호출, 괄호 검사, 역순 문자열 생성 등 다양한 알고리즘과 문제 해결에서 유용하게 사용됩니다. 연결리스트를 활용하여 스택을 구현함으로써, 스택의 동작 원리를 더 깊이 이해하고, 다양한 상황에서 스택을 적절하게 활용할 수 있습니다.