스택

진호우 2025. 1. 21. 20:17

스택의 개념

스택(Stack)은 자료를 순서대로 저장하고, 나중에 저장된 데이터부터 꺼내는 방식을 따르는 자료구조이다.
이는 후입선출(LIFO: Last In, First Out) 원칙을 기반으로 동작한다.
스택은 데이터 삽입(Push)과 삭제(Pop)이 항상 같은 한쪽 끝에서만 이루어진다.

스택의 주요 연산

push:
스택에 데이터를 삽입하는 연산이다. 새 데이터는 스택의 맨 위에 추가된다.
pop:
스택에서 데이터를 삭제하는 연산이다. 삭제 대상은 스택의 맨 위에 있는 데이터이다.
스택이 비어 있는 상태에서 Pop 연산을 수행하려고 하면 오류 또는 예외가 발생할 수 있다.
peek(Top):
스택의 맨 위에 있는 데이터를 확인하는 연산이다.
데이터를 꺼내지 않고 단순히 값을 반환한다.
isEmpty:
스택이 비어 있는지 확인하는 연산이다.
비어 있다면 true, 비어 있지 않다면 false를 반환한다.
size:
스택에 저장된 데이터의 개수를 반환하는 연산이다.

스택의 특징

LIFO 구조:
스택은 나중에 삽입된 데이터가 먼저 삭제되는 구조를 가진다.
접근 제한:
데이터의 삽입과 삭제는 스택의 맨 위에서만 이루어지며, 중간에 있는 데이터에는 접근할 수 없다.
시간 복잡도:
삽입(Push)과 삭제(Pop) 연산은 O(1)의 시간 복잡도를 가진다.
주요 구현 방식:
스택은 배열(Array) 또는 연결 리스트(Linked List)를 이용해 구현할 수 있다.

스택의 활용 사례

함수 호출 관리:
프로그램의 함수 호출이 스택 메모리 구조를 이용해 관리된다.
호출된 함수는 스택에 쌓이고, 함수의 실행이 끝나면 스택에서 제거된다.
문자열 뒤집기:
문자열을 스택에 한 문자씩 삽입한 후, Pop 연산을 통해 꺼내면 문자열을 역순으로 만들 수 있다.
괄호 짝 검사:
프로그램의 괄호 짝이 올바르게 구성되었는지 확인하는 데 사용된다.
여는 괄호는 Push로 삽입하고, 닫는 괄호를 만날 때 Pop으로 짝을 맞춘다.
탐색 알고리즘(DFS):
깊이 우선 탐색은 재귀적으로 호출되며 스택을 이용해 탐색 경로를 관리한다.
Undo/Redo:
텍스트 에디터에서 작업 취소(Undo)와 복구(Redo) 기능은 스택을 이용해 구현된다.
- Undo 스택: 이전 작업을 저장.
- Redo 스택: 취소된 작업을 저장.

자바스크립트를 이용한 스택 구현 예제

배열(Array)을 이용해 스택을 구현한 코드이다.

const createStack = () => {
  let items = []; // 데이터를 저장할 배열 (캡슐화된 상태)

  return {
    // 데이터 삽입
    push(element) {
      items.push(element); // 배열의 끝에 데이터 추가
    },

    // 데이터 삭제
    pop() {
      if (this.isEmpty()) {
        return "스택이 비어 있습니다."; // 비어 있으면 에러 메시지 반환
      }
      return items.pop(); // 배열의 마지막 데이터 제거 및 반환
    },

    // 맨 위 데이터 확인
    peek() {
      if (this.isEmpty()) {
        return "스택이 비어 있습니다.";
      }
      return items[items.length - 1]; // 마지막 데이터 반환
    },

    // 스택이 비어 있는지 확인
    isEmpty() {
      return items.length === 0; // 배열 길이가 0인지 확인
    },

    // 스택 크기 확인
    size() {
      return items.length; // 배열의 길이 반환
    },
  };
};

// 스택 사용 예제
const stack = createStack();

// 데이터 삽입
stack.push(10);
stack.push(20);
stack.push(30);

// 스택 상태 확인
console.log(stack.peek()); // 30
console.log(stack.size()); // 3

// 데이터 삭제
console.log(stack.pop()); // 30
console.log(stack.pop()); // 20
console.log(stack.isEmpty()); // false
console.log(stack.pop()); // 10
console.log(stack.isEmpty()); // true

스택 구현 시 고려할 점

오버플로우(Overflow):
스택에 데이터가 가득 찬 상태에서 Push 연산을 시도하면 발생한다.
배열을 이용할 경우, 최대 크기를 지정해 오버플로우를 방지할 수 있다.
언더플로우(Underflow):
스택이 비어 있는 상태에서 Pop 연산을 시도하면 발생한다.
이 경우 예외 처리를 통해 오류를 방지할 수 있다.