자료구조와 알고리즘, Stack

 

스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙에 따라 데이터를 관리하는 자료 구조입니다. 이는 마지막에 삽입된 데이터가 가장 먼저 제거되는 구조를 의미합니다. 스택은 주로 재귀 알고리즘, 언어의 함수 호출, 실행 취소 기능 등에서 많이 사용됩니다.

주요 연산

1. push: 스택의 맨 위에 데이터를 추가합니다.
2. pop: 스택의 맨 위에 있는 데이터를 제거하고 반환합니다.
3. peek (또는 top): 스택의 맨 위에 있는 데이터를 반환하지만 제거하지는 않습니다.
4. isEmpty: 스택이 비어 있는지 확인합니다.
5. size: 스택에 있는 데이터의 개수를 반환합니다.

스택의 특징

• LIFO: 마지막에 삽입된 데이터가 가장 먼저 제거됩니다.
• 제한된 접근: 스택은 오직 한쪽 끝에서만 데이터의 삽입과 제거가 가능합니다.

스택의 활용 예시

• 재귀 알고리즘: 함수 호출 시 호출된 함수가 완료될 때까지의 상태를 저장하는 데 사용됩니다.
• 웹 브라우저의 뒤로 가기 기능: 사용자가 방문한 페이지를 스택에 저장하고, 뒤로 가기 버튼을 누르면 스택의 맨 위 페이지를 제거하고 이전 페이지로 이동합니다.
• 텍스트 편집기의 실행 취소 기능: 사용자가 수행한 작업을 스택에 저장하고, 실행 취소 버튼을 누르면 마지막 작업을 제거하여 이전 상태로 되돌립니다.

JavaScript로 구현하기

다음은 JavaScript로 스택을 배열을 사용하여 구현한 예제입니다.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null; // 스택의 맨 위 요소
    this.size = 0;   // 스택의 크기
  }

  // 스택에 요소 추가
  push(value) {
    const newNode = new Node(value);
    if (!this.top) {
      this.top = newNode;
    } else {
      newNode.next = this.top;
      this.top = newNode;
    }
    this.size++;
    return this;
  }

  // 스택에서 요소 제거 및 반환
  pop() {
    if (!this.top) return null;
    const removedNode = this.top;
    this.top = this.top.next;
    this.size--;
    return removedNode.value;
  }

  // 스택의 맨 위 요소 반환 (제거하지 않음)
  peek() {
    if (!this.top) return null;
    return this.top.value;
  }

  // 스택이 비어 있는지 확인
  isEmpty() {
    return this.size === 0;
  }

  // 스택의 크기 반환
  getSize() {
    return this.size;
  }
}

// 사용 예시
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);

console.log(stack.peek());    // 30
console.log(stack.pop());     // 30
console.log(stack.getSize()); // 2
console.log(stack.isEmpty()); // false
console.log(stack.pop());     // 20
console.log(stack.pop());     // 10
console.log(stack.isEmpty()); // true

배열과의 차이점

1. 접근 방식: 스택은 LIFO 구조로 데이터에 접근하는 반면, 배열은 인덱스를 통해 임의 접근이 가능합니다.
2. 연산 시간 복잡도: 스택의 push와 pop 연산은 O(1) 시간 복잡도를 가집니다. 배열에서도 끝에 요소를 추가하거나 제거하는 것은 O(1)이지만, 배열의 중간에 요소를 삽입하거나 제거하는 것은 O(n)입니다.

스택은 단순한 구조임에도 불구하고 다양한 알고리즘과 프로그램에서 유용하게 사용됩니다. 특히 재귀적 문제 해결, 실행 취소 기능, 함수 호출 관리 등에서 중요한 역할을 합니다.