[자료구조] 스택 Stack 개념 | js 구현

Stack의 특징

1. LIFO(Last In First Out) 

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조를 가지고 있습니다.

 

2. 데이터는 하나씩 넣고 뺄 수 있습니다.

Stack 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺍니다. 한꺼번에 여러 개를 넣거나 뺄 수 없습니다.

 

3. 하나의 입출력 방향을 가지고 있습니다.

Stack 자료구조는 데이터의 입출력 방향이 같습니다. 만약, 입출력 방향이 여러 개라면 Stack 자료구조라고 볼 수 없습니다.

 

js 코드 구현

class Stack {
  // stack constructor를 생성합니다.
  constructor() {
    this.storage = {};
    this.top = -1;
  }
  // stack의 사이즈를 구합니다.
  // this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로부터 size를 구할 수 있습니다.
  // this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타냅니다. 빈 스택을 표현하는 -1부터 1씩 증감하며 표현하며 전체 요소의 개수를 추정할 수 있습니다
  size() {
    return this.top + 1;
  }
  // stack에 element를 추가합니다.
  // 현재 추가하는 element의 인덱스인 this.top을 키로, 요소를 값으로 하여 storage에 할당합니다.
  push(element) {
    this.top += 1;
    this.storage[this.top] = element;
  }
  // 만약 size가 0보다 작거나 같다면 이는 비어있는 스택을 의미하므로 아무 일도 일어나지 않습니다.
  // stack에서 현재 stack의 최상단에 있는 element를 변수에 저장합니다.
  // storage에서 해당 element를 제거합니다.
  // 하나를 제거했으니 방금 제거한 element의 인덱스를 나타내는 top 또한 감소시켜 업데이트 해줍니다.
  // 최상단에 있던 element가 저장된 변수 result를 반환합니다.
  pop() {
    if (this.size() <= 0) {
      return;
    }
    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    return result;
  }
}

 

Stack의 실사용 예제

컴퓨터에서 자료구조 Stack은 어떤 곳에 사용되고 있을까요? 대표적으로 우리가 자주 사용하는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용됩니다.

 

브라우저에서 자료구조 Stack이 사용될 때는 다음과 같은 순서를 거칩니다.

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관합니다.

2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옵니다.

3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는, Next Stack의 가장 마지막으로 보관된 페이지를 가져옵니다.

4. 마지막으로 현재 페이지를 Prev Stack에 보관합니다.

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