스택 (Stack)

스택 (Stack) 설명:

스택은 Last In First Out (LIFO) 원칙에 따라 항목들을 저장하는 자료구조입니다. 즉, 가장 최근에 스택에 추가된 항목이 가장 먼저 제거됩니다. 이러한 특성 때문에 다양한 애플리케이션에서 유용하게 사용됩니다. 스택은 배열이나 연결 리스트와 같은 기본 데이터 구조를 사용하여 구현될 수 있습니다.

기본 연산:
1. Push: 항목을 스택의 꼭대기에 추가한다.
2. Pop: 스택의 꼭대기에서 항목을 제거하고 반환한다.
3. Top/Peek: 스택의 꼭대기 항목을 조회한다. (제거하지 않음)
4. isEmpty: 스택이 비어있는지 확인한다.

JavaScript에서의 스택 구현 예제:

배열을 사용한 간단한 스택 구현:

class Stack {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element);
    }

    pop() {
        return this.items.pop();
    }

    peek() {
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }

    clear() {
        this.items = [];
    }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.peek());  // 2
stack.pop();
console.log(stack.peek());  // 1

스택의 사용 사례:

1. 함수 호출: 함수 호출 시 생성되는 실행 컨텍스트는 스택에 push되고, 함수 종료 시 pop된다.
2. 표현식 계산: 후위 표기법(Postfix notation) 계산 시 사용된다.
3. 문자열 역순 출력: 문자열의 문자를 스택에 push하고 pop하여 역순으로 출력할 수 있다.
4. 괄호 짝 검사: 괄호의 시작을 스택에 push하고, 종료 괄호가 나타날 때 pop하여 짝이 맞는지 확인한다.
5. 문제 풀이: 많은 알고리즘 문제에서 스택이 유용하게 사용된다. 예를 들어, 미로 탐색이나 깊이 우선 탐색(DFS)에서 스택을 사용한다.

장점:
1. 구조가 단순하고 구현이 쉽다.
2. 데이터 추가 및 삭제의 시간 복잡도가 O(1)이다.

단점:
1. 스택의 크기가 고정된 경우, 스택 오버플로우(overflow)가 발생할 수 있다.
2. 배열을 사용하여 구현하는 경우, 스택의 크기를 동적으로 변경하기 어렵다. (하지만 연결 리스트를 사용하면 해결 가능하다.)

스택은 컴퓨터 과학에서 핵심적인 자료구조 중 하나로, 알고리즘 문제 해결부터 실제 소프트웨어 개발까지 다양한 곳에서 활용됩니다.