자료구조 04 스택 | JS

스택 | Stack

이미지 출처

• 선형 자료구조의 일종
• Last In First Out (LIFO): 나중에 들어간 원소가 먼저 나옴
• 입력과 출력이 한 곳(방향)으로 제한
• 사용처: 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법

push : 데이터 삽입
pop : 데이터 추출 + 삭제
peek: head 데이터 확인(출력하면 가장 먼저 나올 데이터)
isEmpty: 비어있는지 확인

배열을 통한 구현

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
  isEmpty() {
    return this._arr.length === 0 ? true : false;
  }
}

연결 리스트를 통한 구현

• push/pop을 Head단 혹은 Tail단으로 구현할 수 있음
• Head단 => prepend / deleteHead (*peek have to return Head)
• Tail단 => append / deleteTail (*peek have to return Tail)
• 아래 코드에서는 Head단에서 구현

import LinkedList from '../linked-list/LinkedList';
// 기존에 제작한 LinkedList import

export default class Stack {
  constructor() {
    this.linkedList = new LinkedList();
  }
  
  push(value) {
    this.linkedList.prepend(value);
  }

  pop() {
    const removedHead = this.linkedList.deleteHead();
    return removedHead ? removedHead.value : null;
  }
  
  isEmpty() {
    return !this.linkedList.head;
  }

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

📚 참고

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
helloworldjavascript

Photo by Alain Pham on Unsplash