Javascript 자료구조 시리즈(2) Stack 스택

Stack
스택은 LIFO(Last In First Out) 또는 FILO(First In Last Out) 원칙을 따르는 데이터 구조입니다.

👉🏻 스택에 요소를 추가할 때마다 스택 맨 위에 추가됩니다.
👉🏻 스택에 마지막으로 삽입된 항목이 가장 먼저 삭제됩니다.
👉🏻 스택은 ToS(Top of Stack)라고 하는 목록의 한쪽 끝에서만 액세스할 수 있는 요소 목록입니다.

쉽게 말해 멘토스 구조라고 생각하시면 됩니다. 멘토스를 깠을때 가장 처음 먹는부분이 마지막으로 쌓인 멘토스라고
생각하시면 됩니다.

 

 

기존에 9~11번 멘토스를 먹었고 11번 pop(), 10번 pop(), 9번 pop()

짝지랑 멘토스 맛을 교환하기로 하였습니다. 그리하여 8번 pop(), 7번 pop(), 6번 pop()

 

다른 멘토스맛 6번 push(), 7번 push(), 8번 push()

Stack구조는 이처럼 쉽습니다.

 

이제 코드로 표현해보겠습니다.👨🏻‍💻

 

우리가 구현할 작업:
Push → 스택에 요소를 추가합니다.
Pop → 스택에서 요소를 삭제합니다.
Peek → 스택의 최상위 요소를 가져옵니다.
Length → 스택의 길이를 반환합니다.
IsEmpty → 스택이 비어 있는지 확인합니다.
Print → 스택의 요소를 인쇄합니다.

 

아래처럼 Stack 클래스를 구현해줍니다.

class Stack {
  /*
  Stack 클래스에는 두 가지 속성이 있습니다.
  data → 값을 저장하는 배열입니다.
  top → 최상위 요소 인덱스를 가리킵니다.
  */
  constructor() {
    this.data = [];
    this.top = 0;
  }

  /*
  push: 스택의 맨 위에 요소 삽입
  요소를 스택에 push할 때 데이터의 맨 위 위치에 저장해야 하고 맨 위가 다음 빈 위치를 가리키도록 top 변수를 증가시켜야 합니다.
  */
  push(element) {
    this.data[this.top] = element;
    this.top = this.top + 1;
  }

  /*
  pop: 스택의 맨 위에 있는 요소를 삭제합니다.
  스택에서 요소를 pop할 때 데이터의 맨 위 위치에 있는 요소를 제거해야 하고 맨 위가 이전 요소의 위치를
  가리키도록 top 변수를 감소시켜야 합니다.
  */
  pop() {
    if (this.isEmpty() === false) {
      this.top = this.top - 1;
      return this.data.pop(); // 마지막 요소를 삭제합니다.
    }
  }

  /*
  peek: 스택의 최상위 요소 가져오기
  스택의 peek 요소를 얻으려면 다음의 top-1 속성을 사용할 수 있습니다.
  */
  peek() {
    return this.data[this.top - 1];
  }

  /*
  length: 스택의 길이를 반환합니다.
  스택의 길이를 얻으려면 top 값을 반환할 수 있습니다.
  */
  length() {
    return this.top;
  }

  /*
  isEmpty: 스택이 비어 있는지 확인
  top의 값이 0이면 스택에 요소가 없습니다.
  */
  isEmpty() {
    return this.top === 0;
  }

  /*
  print: 스택의 요소 인쇄
  */
  print() {
    var top = this.top - 1; // 상단이 새 요소를 삽입할 인덱스를 가리키기 때문입니다.
    while (top >= 0) { // 0번째 인덱스까지 출력
      console.log(this.data[top]);
      top--;
    }
  }
}

Stack 사용 예시

const stack = new Stack()

stack.push('chocolate')
stack.push('ice cream')
stack.push('cookie')
stack.print()
/*
Print Result

  cookie
  ice cream
  chocolate
*/


stack.pop()
stack.print()
/*
Print Result

  ice cream
  chocolate
*/


stack.push('cake')
stack.print()
/*
Print Result

  cake
  ice cream
  chocolate
*/


console.log('stack.peek : ', stack.peek());
console.log('stack.length : ', stack.length());
/*
Log Result

  stack.peek :  cake
  stack.length :  3
*/