스택 (Stack)

스택은 데이터를 차곡차곡 쌓아 올리는 형태의 선형 자료구조이다.
가장 마지막에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO, Last-In First-Out) 원칙을 따른다.

스택의 정의와 특징

스택은 한쪽 끝에서만 삽입과 삭제가 일어나는 제한적인 자료구조이다.
이 때문에 데이터의 순서와 접근 방식이 중요한 알고리즘에 널리 활용된다.
대표적인 예시로 Undo/Redo, Call Stack, DFS (깊이 우선 탐색) 등이 있다.

주요 특징

후입선출(LIFO): 가장 나중에 추가된 요소가 가장 먼저 제거된다. 단방향 입출력: 데이터는 항상 스택의 Top에서만 추가되고 제거된다.

연산	설명	시간 복잡도
push(element)	스택의 가장 위(top)에 요소를 추가합니다.	O(1)
pop()	스택의 가장 위(top) 요소를 제거하고 반환합니다.	O(1)
peek()	스택의 가장 위(top) 요소를 제거하지 않고 확인만 합니다.	O(1)
isEmpty()	스택이 비어있는지 확인합니다. (true/false)	O(1)
size()	스택에 포함된 요소의 개수를 반환합니다.	O(1)

Javascript로 Stack 구현하기

class Stack {
  constructor() {
    this.items = []; // 배열을 사용하여 데이터를 저장
  }
  // 스택에 요소 추가
  push(data) {
    this.items.push(data);
  }
  // 스택에서 요소 제거 및 반환
  pop() {
    return this.items.pop();
  }
  // 스택의 최상단 요소 확인
  peek() {
    return this.items[this.size() - 1];
    // ES2022 -> return this.items.at(-1);
  }
  // 스택이 비어있는지 확인
  isEmpty() {
    return this.size() === 0;
  }
  // 스택의 크기 반환
  size() {
    return this.items.length;
  }
  // 스택 초기화
  clear() {
    this.items = [];
  }
}
const stack = new Stack();
stack.push(1); // [1]
stack.push(2); // [1, 2]
stack.push(3); // [1, 2, 3]
stack.pop(); // [1, 2]
stack.peek(); // 2

console.log(stack.isEmpty()); // false
stack.clear();
console.log(stack.isEmpty()); // true