[JS/Algorithm] 스택

1. 스택 개념

스택 : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조

LIFO (Last In First Out) : 먼저 들어간 것이 마지막에 나오는 규칙

push : 스택에 삽입하는 연산

pop : 스택에서 꺼내는 연산

최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋음

 

2. 스택의 정의

스택의 ADT

ADT란 ?
Abstract Data Type의 약자
추상 자료형 (인터페이스만 있고 실제로 구현은 되지 않는 자료형)
일종의 자료형의 설계도

정의해야 할 연산 : push , pop ,  isFull , isEmpty 

정의해야 할 상태 : top , data[maxsize]

  데이터가 없으면 top = -1

 

스택 세부 동작

1. push(3) 호출

2. isFull()을 수행하여 data 배열에 데이터가 가득 찾는지 확인

3. 가득 차지 않았으면 top을 1만큼 증가시킨 후 top이 가리키는 위치 data[0]에 3을 추가

4. pop() 호출

5. IsEmpty()를 수행하여 data 배열에 데이터가 있는지 확인

6. 데이터가 있다면 top을 1만큼 감소시킨 후 데이터 3을 반환

스택 구현

1. 스스로 구현해보기

class Stack {
  constructor(maxSize) {
    this.data = [];
    this.maxSize = maxSize;
    this.top = -1;
  }
  isFull() {
    return this.top === this.maxSize - 1;
  }

  isEmpty() {
    return this.top === -1
  }
  push(number) {
    if (!this.isFull()) {
      this.top += 1;
      this.data[this.top] = number;
    } 
  }

  pop() {
    if (!this.isEmpty()) {
      this.top -= 1;
      this.data.pop();
    }
  }

}

2. 교재

const stack = []; // 스택 초기화
const maxSize = 10; // 스택의 최대 크기

function isFull(stack) {
  // 스택이 가득 찾는지 확인하는 함수
  return stack.length === maxSize;
}

function isEmpty(stack) {
  // 스택이 비어있는지 확인하는 함수
  return stack.length === 0;
}

function push(stack, item) {
  // 스택에 데이터를 추가하는 함수
  if (isFull(stack)) {
    console.log("스택이 가득 찼습니다.");
  } else {
    stack.push(item);
    console.log("데이터가 추가되었습니다.");
  }
}

function pop(stack) {
  // 스택에서 데이터를 꺼내는 함수
  if (isEmpty(stack)) {
    console.log("스택이 비어있습니다.");
    return null;
  } else {
    return stack.pop();
  }
}