스택 (Stack)

접시를 쌓을 때를 생각해보자.

아래에서부터 차곡차곡 쌓아 올리고, 사용할 때는 가장 위에 있는 접시부터 꺼내게 된다.

이것이 바로 스택(Stack)의 핵심 개념이다.

 

스택

스택은 FILO(First-In-Last-Out) 또는 LIFO(Last-In-First-Out) 구조를 가지는 자료구조이다.

즉, 먼저 들어온 데이터가 나중에 나가고, 나중에 들어온 데이터가 먼저 나가는 구조이다.

스택의 핵심 연산

스택은 다음과 같은 기본 연산을 제공한다.

1. push(): 스택의 맨 위에 데이터를 추가
2. pop(): 스택의 맨 위에서 데이터를 제거하고 반환
3. peek(): 스태그이 맨 위 데이터를 제거하지 않고 확인
4. isEmpty(): 스택이 비어있는지 확인

 

연결 리스트로 스택 구현하기

스택은 배열로도 구현할 수 있지만, 이전 글에서 다룬 연결리스트를 활용하면 더 유연하게 구현할 수 있다.

연결리스트의 맨 앞에서 삽입과 삭제를 수행하면 O(1)의 시간복잡도로 효율적인 스택을 만들 수 있다.

Stack 클래스

import { LinkedList } from "../LinkedList.mjs";

class Stack {
  constructor() {
    this.list = nes LinkedList(); // 내부적으로 연결 리스트 사용
  }
}

스택은 내부적으로 연결 리스트를 사용한다.

이렇게 하면 스택의 기능에만 집중할 수 있고, 데이터 관리는 연결 리스트에게 위임할 수 있다.

 

주요 메서드

1. push() - 데이터 추가

push(data) {
  this.list.insertAt(0, data); // 항상 맨 앞(인덱스 0)에 삽입
}

새로운 데이터를 연결 리스트의 맨 앞(head)에 추가한다. 이렇게 하면 가장 최근에 추가된 데이터가 항상 맨 앞에 위치하게 된다.

 

2. pop() - 데이터 제거 및 반환

pop() {
  try {
    return this.list.deleteAt(0); // 맨 앞의 데이터 제거
  } catch (e) {
    return null; // 스택이 비어있으면 null 반환
  }
}

맨 앞의 데이터를 제거하고 반환한다. 스택이 비어있을 때는 에러 대신 null을 반환하여 안전하게 처리한다.

 

3. peek() - 맨 위 데이터 확인

peek() {
  return this.list.getNodeAt(0); // 맨 앞의 데이터만 확인
}

데이터를 제거하지 않고 맨 위의 데이터만 확인한다. 스택의 상태를 유지하면서 다음에 나올 데이터를 미리 볼 때 유용하다.

 

4. isEmpty() - 비어있는지 확인

isEmpty() {
  return this.list.count == 0;
}

스택에 데이터가 있는지 확인한다. pop()을 호출하기 전에 확인하면 안전하다.

 

스택 사용 예제

예제 1: 기본 push/pop 동작

let stack = new Stack();

stack.push(1);  // [1]
stack.push(2);  // [2, 1]
stack.push(3);  // [3, 2, 1]
stack.push(4);  // [4, 3, 2, 1]

console.log(stack.pop().data);  // 4 출력
console.log(stack.pop().data);  // 3 출력
console.log(stack.pop().data);  // 2 출력
console.log(stack.pop().data);  // 1 출력

가장 나중에 넣은 4부터 거꾸로 나오는 것을 확인할 수 있다.

 

예제 2: peek()와 isEmpty() 활용

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

console.log(stack.peek().data);  // 4 출력 (제거하지 않음)
stack.pop();
console.log(stack.peek().data);  // 3 출력

console.log(`stack.isEmpty: ${stack.isEmpty()}`);  // false

// 모든 데이터 제거
stack.pop();
stack.pop();
stack.pop();

console.log(`stack.isEmpty: ${stack.isEmpty()}`);  // true
console.log(stack.pop());  // null (빈 스택에서 pop)

 

스택의 시간복잡도

스택의 모든 기본 연산은 O(1)의 시간복잡도를 가진다.

• push(): O(1)
• pop(): O(1)
• peek(): O(1)
• isEmpty(): O(1)

연결 리스트의 맨 앞에서만 작업하기 때문에 매우 효율적이다.

 

스택의 실제 활용 사례

1. 함수 호출 스택 (Call Stack)

프로그래밍에서 함수가 호출될 때 사용된다.

함수 A가 함수 B를 호출하고, B가 C를 호출하면, 실행 순서는 C → B → A 순으로 종료된다.

function first() {
  second();
  console.log("첫 번째 함수");
}


function second() {
  third();
  console.log("두 번째 함수");
}

function third() {
  console.log("세 번째 함수");
}

first(); // 출력: 세 번째 함수 → 두 번째 함수 → 첫 번째 함수

 

2. 괄호 검사

코드 에디터나 컴파일러에서 프로그래밍 코드의 괄호가 올바른 쌍인지 확인할 때 사용한다.

여는 괄호를 push하고, 닫는 괄호를 만나면 pop하여 짝이 맞는지 확인한다.

function isValidParentheses(str) {
  const stack = new Stack();
  
  for (let char of str) {
    if (char === '(') {
      satck.push(char);
    } else if (char === ')') {
      if (stack.isEmpty()) return false; // 닫는 괄호가 더 많음
      stack.pop();
    }
  }
  return stack.isEmpty(); // 여는 괄호가 남아있으면 false
}

console.log(isValidParentheses("((()))")); // true
console.log(isValidParentheses("(()")); // false - 여는 괄호 1개 남음
console.log(isValidParentheses("())")); // false - 닫는 괄호가 더 많음

 

3. 브라우저 뒤로가기

웹 브라우저의 방문 기록을 관리할 때 스택을 사용한다.

새 페이지를 방문할 때마다 push하고, 뒤로 가기 버튼을 누르면 pop하여 이전 페이지로 돌아간다.

 

4. 실행 취소(Undo) 기능

텍스트 에디터나 그래픽 프로그램에서 작업 내역을 스택에 저장하여 Ctrl+Z 기능을 구현한다.

가장 최근 작업부터 순서대로 취소할 수 있다.

 

스택은 FILO 구조라는 간단한 규칙만으로도 다양한 문제를 해결할 수 있다.

특히 "가장 최근 것을 먼저 처리"해야 하는 상황에서는 스택이 적절한 선택이라고할 수 있다.