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

개념

LIFO

Last In First Out

먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 또는 LIFO Last In First Out라고 합니다. 이때 스택에 삽입하는 연산을 푸시 push, 꺼내는 연산을 팝POP이라고 합니다.

동작과정을 살펴보면 다음과 같습니다.

처음에 빈 스택이 존재합니다.

이후 1을 push하게 되면 다음과 같이 존재합니다.

여기서 2를 push하면 다음과 같이 그 위로 쌓이게 됩니다.

여기서 pop을 하면 LIFO 방식에 따라서 가장 위에 있는 2가 빠져나오게 됩니다.

이후 3을 push하면 다시 1위로 3이 쌓이게 됩니다.

마지막으로 pop을 2번 연속으로 하게 되면 위에서부터 빠져나오다가 다시 처음으로 돌아갑니다.

ADT

ADT

Abstract Data Type ( 추상 자료형 ) 인터페이스만 있고 실제로 구현은 되지 않은 자료형입니다. 일종의 자료형의 설계도라고 보시면 됩니다.

스택은 push, pop, isFull, isEmpty 같은 연산이 있어야 합니다. 또한 변수로 top도 있어야 스택 동작을 구현할 수 있어요.

이를 표로 정리하면 다음과 같습니다.

표를 기반으로 ADT를 나타내면 다음과 같습니다.

NOTE

주목할 점은 top에 -1이 들어간 것입니다. top은 data의 인덱스로써 사용됩니다. 데이터가 하나 있을 때 인덱스는 0이므로 아무것도 없을 때를 표현하기 위해 -1을 넣은 것입니다.

스택에 데이터를 추가하는 경우 다음과 같이 표현할 수 있습니다.

1. isFull을 수행하여 data 배열에 더 넣을 수 있는지 확인
   1. 넣을 수 있다면 top을 1 증가시키고 data[top]에 데이터 추가
   2. 넣을 수 없다면 종료

스택에 데이터를 꺼낸다면 다음과 같이 표현할 수 있습니다.

1. isEmpty를 수행하여 data 배열에 데이터가 있는지 확인
   1. 있다면 top을 1 감소시키고 data[top+1]을 반환
   2. 없다면 종료

이제 이러한 ADT를 기반으로 스택을 구현해봅시다.

구현

ADT 대로라면 다음과 같이 구현할 수 있어요.

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

  isEmpty() {
    return this.top === -1;
  }

  push(element) {
    if (this.isFull()) {
      console.log("스택이 가득찼어요");
    } else {
      this.data[this.top++] = element;
    }
  }

  pop() {
    if (this.isEmpty()) {
      console.log("스택이 비어있어요");
    } else {
      return this.data[--this.top];
    }
  }
}

JS는 동적으로 배열을 관리하기 때문에 isFull, isEmpty 없이도 배열 메소드를 이용해 스택처럼 사용할 수 있어요.

const stack = new Array(maxsize);

// push : stack.push(1)
// pop : stack.pop()
// top : stack.length-1

참고 문헌

https://product.kyobobook.co.kr/detail/S000213641007

SUMMARY

알고리즘은 꾸준히 공부해주지 않으면 개념들이 유독 빠르게 사라지는 것 같아요. 사라지면 다시 채워넣을 수 있도록 꾸준히 공부해보겠습니다. 잘못된 지식이 있다면 댓글 부탁드려요!

읽어주셔서 감사해요.