Binyard

Appearance

스택 (Stack) ​

스택은 데이터를 한쪽 끝에서만 넣고 꺼내는 자료구조이다.

Introduction to Stack Data Structure

스택의 가장 큰 특징은 나중에 들어온 데이터가 먼저 나간다는 점이다.
이러한 구조를 LIFO(Last In First Out)라고 한다.


스택의 기본 연산 ​

스택은 보통 다음과 같은 기능을 가진다.

  • push: 데이터 삽입
  • pop: 가장 위에 있는 데이터 제거하고 반환
  • peek: 가장 위에 있는 데이터를 제거하지 않고 확인
  • isEmpty: 스택이 비었는지 확인

스택은 다음과 같은 상황에서 자주 사용된다고 한다.

  • 뒤로 가기
  • 실행 취소
  • 함수 호출 관리
  • 괄호 검사
  • DFS 탐색

배열로 Stack 구현하기 ​

JavaScript 배열은 push()와 pop() 메서드를 기본으로 제공한다.
그래서 배열을 사용하면 스택을 가장 간단하게 구현할 수 있다.

배열의 마지막 요소를 스택의 가장 위, 즉 top으로 생각하면 된다.

txt
[1, 2, 3, 4]
          ↑
         top

class 문법으로 구현하기 ​

js
class Stack {
  constructor() {
    // 스택 데이터를 저장할 배열
    this.items = [];
  }

  push(data) {
    this.items.push(data);
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }

    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }

    // 배열의 마지막 요소가 스택의 top
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

export { Stack };

함수로 구현하기 ​

class 문법을 사용하지 않고 함수로도 스택을 만들 수 있다.

js
function createStack() {
  const items = [];

  return {
    push(data) {
      items.push(data);
    },

    pop() {
      if (items.length === 0) {
        return null;
      }

      return items.pop();
    },

    peek() {
      if (items.length === 0) {
        return null;
      }

      return items[items.length - 1];
    },

    isEmpty() {
      return items.length === 0;
    },
  };
}

export { createStack };
  • 이 방식은 createStack() 함수를 호출하면 스택처럼 사용할 수 있는 객체를 반환한다.
js
const stack = createStack();

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

console.log(stack.pop()); // 3
console.log(stack.peek()); // 2
console.log(stack.isEmpty()); // false
  • pop()과 peek()은 스택의 가장 위에 있는 데이터 값을 반환한다.

연결 리스트 방식으로 Stack 구현하기 ​

스택은 배열뿐만 아니라 연결 리스트 구조로도 구현할 수 있다.
연결 리스트 방식에서는 스택의 가장 위를 top이라고 두고, 새로운 데이터를 top 앞에 연결한다.

txt
top
 ↓
[4] → [3] → [2] → [1] → null

이 구조에서는 가장 마지막에 들어온 데이터가 항상 top에 위치한다.
따라서 pop()을 하면 top에 있는 데이터가 먼저 제거된다.


class 문법으로 구현하기 ​

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

class Stack {
  constructor() {
    this.top = null;
    this.count = 0;
  }

  push(data) {
    const newNode = new Node(data);

    // 새 노드를 현재 top 앞에 연결
    newNode.next = this.top;
    // 새 노드를 top으로 변경
    this.top = newNode;
    this.count++;
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }

    const removedData = this.top.data;

    // top을 다음 노드로 이동
    this.top = this.top.next;
    this.count--;

    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }

    return this.top.data;
  }

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

export { Stack };

연결 리스트 방식에서 가장 중요한 부분은 push()의 순서이다.

js
newNode.next = this.top;
this.top = newNode;
  • 먼저 새 노드가 기존 top을 가리키게 만든다.
  • 그 다음 top을 새 노드로 변경한다.
  • 만약 순서를 반대로 하면 기존 노드와의 연결이 끊길 수 있기 때문에,
    먼저 next를 연결하고 나서 top을 바꾸는 순서가 중요하다.

js
const removedData = this.top.data;
this.top = this.top.next;
  • pop()에서는 현재 top에 있는 데이터를 저장한다.
  • 그 다음 top을 다음 노드로 이동시킨다.
  • 마지막으로 제거된 데이터 값을 반환한다.

함수로 구현하기 ​

class를 사용하지 않고 함수로도 연결 리스트 기반 스택을 만들 수 있다.

js
function createNode(data) {
  return { data, next: null };
}

function createStack() {
  let top = null;
  let count = 0;

  return {
    push(data) {
      const newNode = createNode(data);

      // 새 노드를 현재 top 앞에 연결
      newNode.next = top;
      // top 변경
      top = newNode;
      count++;
    },

    pop() {
      if (this.isEmpty()) {
        return null;
      }

      const removedData = top.data;

      // top을 다음 노드로 이동
      top = top.next;
      count--;

      return removedData;
    },

    peek() {
      if (this.isEmpty()) {
        return null;
      }

      return top.data;
    },

    isEmpty() {
      return count === 0;
    },
  };
}

export { createStack };

사용 예시는 다음과 같다.

js
const stack = createStack();

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

console.log(stack.pop()); // 4
console.log(stack.pop()); // 3
console.log(stack.peek()); // 2
console.log(stack.isEmpty()); // false

배열 방식과 연결 리스트 방식의 공통점 ​

배열 방식과 연결 리스트 방식은 내부 구현 방법은 다르지만, 스택을 사용하는 방법은 같다.

js
console.log(stack.pop()); // 4
console.log(stack.peek()); // 3
  • pop()은 가장 위에 있는 데이터를 제거하고 반환한다.
  • peek()은 가장 위에 있는 데이터를 제거하지 않고 확인한다.
  • 배열 방식이든 연결 리스트 방식이든 사용자는 데이터 값을 바로 받을 수 있다.

즉, 배열 방식은 배열의 마지막 요소를 top처럼 사용하고,
연결 리스트 방식은 top이라는 노드를 직접 관리한다는 차이가 있다.

하지만 스택을 사용하는 입장에서는 둘 다 다음과 같이 동일하게 사용할 수 있다.

js
stack.push(1);
stack.push(2);

console.log(stack.pop()); // 2
console.log(stack.peek()); // 1

배열 방식과 연결 리스트 방식 비교 ​

스택은 배열과 연결 리스트 두 방식 모두로 구현할 수 있다.

구현 방식pushpop특징
배열 방식O(1)O(1)구현이 간단하고 JavaScript에서 가장 쉽게 사용할 수 있다
연결 리스트 방식O(1)O(1)노드와 top의 연결 관계를 직접 이해하기 좋다

스택 사용 예시: 괄호 검사 ​

HTML/XML 태그 검사, 코드 컴파일러, 계산기 등에서 괄호 쌍이 맞는지 검증할 때 사용된다.

아래 예시는 앞에서 만든 createStack()을 사용한다고 가정한다.
배열 방식이든 연결 리스트 방식이든 pop()이 데이터 값을 반환하면 같은 방식으로 사용할 수 있다.

js
function isValidParentheses(str) {
  const stack = createStack();
  const pairs = { ")": "(", "}": "{", "]": "[" };

  for (const char of str) {
    if ("({[".includes(char)) {
      stack.push(char);
    } else if (")]}".includes(char)) {
      if (stack.isEmpty() || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  return stack.isEmpty();
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({[}])")); // false
  • 괄호가 올바르게 닫혔다면 마지막에 스택이 비어 있어야 한다.

정리 ​

스택은 나중에 들어온 데이터가 먼저 나가는 LIFO 구조의 자료구조이다.

배열로 구현할 때는 배열의 마지막 요소를 top처럼 사용하고,
연결 리스트로 구현할 때는 top 노드를 직접 관리한다.

구현 방식은 다르지만 push, pop, peek, isEmpty 같은 기본 연산은 동일하게 사용할 수 있다.

스택은 뒤로 가기, 실행 취소, 함수 호출 관리, 괄호 검사처럼
가장 최근에 들어온 데이터를 먼저 처리해야 하는 상황에서 자주 사용된다.