[Data Structure] 스택(Stack)

스택(Stack)이란?

스택(Stack) 은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조다.

Stack은 쌓다, 쌓이다, 포개지다와 같은 뜻을 가지고 있다. 마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 직역 그대로, 데이터(data)를 순서대로 쌓는다.

Stack의 구조

스택(Stack) 은 다음과 같은 구조로 나누어서 진행된다.

스택(Stack) 은 top이 있는 위치에서만 데이터에 접근할 수 있다.

• top() — 스택의 맨 위에 있는 데이터 값 (현재 가리키고 있는 데이터)
• pop() — 데이터를 스택에서 빼내는 것
• push() — 데이터를 스택에 쌓는 것

Stack의 특징

1. 후입선출(LIFO: Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조로 되어 있다. 이러한 특성으로 인해 구조 내에서 특정 데이터를 조회할 수 없으며, 스택의 최상단에서만 데이터를 저장하고 꺼낼 수 있는 특징이 있다.

그렇기 때문에 데이터를 저장할 때나 검색할 때 항상 스택의 최상단에서만 행위가 이루어지며, 이에 따라 데이터를 저장하고 검색하는 프로세스가 매우 빠르다.

2. 하나의 입출력 방향을 가지고 있다.

Stack은 데이터가 들어가고 나가는 곳이 스택의 가장 최상단, 한 군데다. 즉 데이터를 넣을 때도 스택의 가장 최상단으로 넣고(입력) 뺄 때 또한 스택의 가장 최상단으로 뺄 수(출력) 있다.

3. 데이터는 하나씩 넣고 뺄 수 있다.

Stack은 데이터를 넣고 뺄 수 있는 경로가 스택의 최상단, 한 군데이기 때문에 스택 내부에 데이터를 넣을 때도 하나씩 최상단을 통해 넣고 데이터를 뺄 때 또한 항상 스택 최상단에서 하나씩 데이터를 뺄 수 있다.

즉, 스택에 한개 씩 여러 번 데이터를 넣어 스택 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 스택의 가장 최상단에서 한 번에 한 개의 데이터만을 뺄 수 있다.

Stack의 활용 예시

• 괄호 검사, 후위 연산법, 문자열 역순 출력 등
• 작업 실행 취소와 같은 역추적 작업이 필요할 때

e.g. 브라우저의 뒤로 가기와 앞으로 가기 기능에 사용된 Stack

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는, Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.

이렇게 자료구조 Stack을 이용하면, 뒤로 가기와 앞으로 가기 버튼을 구현할 수 있다.

Stack 구현

JavaScript에서는 Stack 라이브러리를 지원해주지 않는다.

보통의 스택은 배열로 선언하고 push, pop 메서드를 사용하여 대체할 수 있다. 스택에서는 끝 부분의 인덱스만 사용하여 연산을 하기 때문에 Stack의 삽입과 삭제는 문제가 되지 않는다.

하지만, 배열로 구현하기 한계가 있다보니 간단한 예제가 아닌 이상 연결리스트로 구현하는 것이 좋다.

연결리스트를 활용한 Stack Code

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

class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }

  // 데이터 삽입
  push(value) {
    let newNode = new Node(value);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      let tmp = this.first;
      this.first = newNode;
      this.first.next = tmp;
    }
    return ++this.size;
  }

  // 데이터 삭제
  pop() {
    if (!this.first) return null;
    let tmp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return tmp.value;
  }

  // 데이터 출력
  print() {
    let current = this.first;

    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }
}

const stack = new Stack();
stack.push(0);
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();
stack.print();

/**
2
1
0
*/

정리

Stack 은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 널리 사용된다.

• Stack은 데이터 구조의 이전 구현을 기반으로 한다.
• Stack은 LIFO 이다.
• 컴퓨터 과학 전반에 걸쳐 널리 사용된다.

Reference

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!
[Javascript] Stack, Queue / Javascript Queue 구현해야 하는 이유
CODESTATES (SEB_FE_43)