자료구조 - 스택(Stack)

Stack 이란?

스택이란 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조를 말한다.

 

 

Stack의 연산

스택은 LIFO 형식을 따른다. 따라서 가장 최근에 스택에 추가한 항목이 가장 먼저 제거된다.

• push(item): item 하나를 스택의 가장 윗부분에 추가한다.
• pop(): 스택에서 가장 위에 있는 항목을 제거한다.
• peek() : 스택의 가장 위에 있는 항목을 반환한다.
• isEmpty() : 스택이 비어 있을 때에 true를 반환한다.
• length() : 스택의 길이를 반환한다.
• getBuffer(): 스택 전체를 반환한다.

Stack을 사용하는 경우

• 재귀 알고리즘
• 재귀적으로 함수를 호출해야하는 경우에 임시 데이터를 스택에 넣어준다.
• 웹 브라우저 방문기록(뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사
• 후위 표기법 계산

Stack 구현 방법

1. 배열을 사용하는 방법

• 배열 사용시 구현이 쉽다.
• 원하는 데이터의 접근 속도가 빠르다.
• 데이터의 최대 개수가 미리 정해져야 한다.
• 데이터의 삽입 및 삭제에 있어 매우 비효율적이다. 두번째 위치에 데이터를 삽입 하려면 그 보다 먼저 들어간 데이터들을 한칸씩 전부 옮겨줘야한다.

1. 연결 리스트를 사용하는 방법

• 데이터의 최대 개수가 한정적이지 않다.
• 데이터의 삽입 및 삭제에 용이하다.

배열의 경우 데이터의 양이 많지만 삽입/삭제가 거의 없고 데이터의 접근이 자주 일어날때 사용하면 좋고 반대로 연결 리스트의 경우 삽입/삭제가 빈번히 이뤄지고, 데이터의 접근이 거의 없을때 사용하는것이 좋다.

 

 

배열을 이용한 Stack 구현코드

<script>
class Stack {
  constructor() {
    this.count = 0;
    this.storage = [];
  }

  push(item) {
    this.storage[this.count] = item;
    this.count++;
  }

  pop() {
    if (this.count === 0) {
      return undefined;
    }

    this.count--;
    var result = this.storage[this.count];
    delete this.storage[this.count];
    return result;
  }

  peek() {
    if (this.count === 0) {
      return "stack is empty";
    }
    return this.storage[this.count - 1];
  }

  isEmpty(){
    return this.count==0?true:false;
  }

  length() {
    return this.count;
  }

  getBuffer() {
    return this.storage;
  }
}

</script>