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());
}

// 출력:
// }
// )
// (
// {

결론

스택은 데이터를 일시적으로 저장하면서 가장 최근에 추가된 데이터에 빠르게 접근할 수 있는 자료구조입니다. 스택은 프로그래밍에서 함수 호출, 괄호 검사, 역순 문자열 생성 등 다양한 알고리즘과 문제 해결에서 유용하게 사용됩니다. 연결리스트를 활용하여 스택을 구현함으로써, 스택의 동작 원리를 더 깊이 이해하고, 다양한 상황에서 스택을 적절하게 활용할 수 있습니다.