Javascript 스택 이해하기

스택(Stack)

스택stack 어원은 '쌓는다' 이다. 스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다.

티슈를 생각해보면 티슈를 만들 때는 먼저 넣은 티슈가 가장 아래에 위치한다. 그래서 티슈를 사용할 때는 가장 위에 있는 티슈부터 사용할 수 있다.

이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 후입선출 또는 LIFO(Last In First out)라고 한다.

이때 스택에 삽입하는 연산을 푸시(Push), 꺼내는 연산을 팝(Pop)이라고 한다.

스택의 ADT(Abstract Data Type)

ADT는 우리말로 추상 자료형이다

추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형인데 일종의 자료형의 설계도이다.

그렇다면 스택은 어떤 정의가 필요한 자료구조일까?

우선 스택에는 Push, Pop, isFull(가득 찼는지 확인), isEmpty(비었는지 확인)와 같은 연산을 정의해야 한다.

그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 top도 있어야 한다.

표와 그림으로 정리하면 다음과 같다

위는 스택의 ADT를 나타낸 그림이다

name	value
스택	data
최대 크기	maxsize
top(가장 최근에 추가한 데이터)	-1

스택의 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize - 1이다.

top은 가장 최근에 추가한 데이터의 위치를 참조한다.

지금 그림에서는 아무 데이터도 없으므로 top에 -1이 들어 있는데

만약 top이 0이면 데이터가 1개 있는 것이므로 초깃값을 0이 아니라 -1로 했음에 주목하면 된다

스택에 데이터 추가(push)

스택에 push(3)을 통해 데이터를 추가하는 경우를 생각해보면

1) 스택(data 배열)이 가득 찼는지 확인(boolean)

2) 꽉 차지 않았다면 top을 1 증가시킨 후

3) top이 가리키는 위치에 data[0]에 3을 추가

스택에서 데이터 삭제(pop)

반대로 pop()을 통해 데이터를 삭제하는 경우를 생각해보면

1) isEmpty()로 스택에 데이터가 없는지 확인(boolean)

2) top 1만큼 감소

3) 데이터 3을 반환

스택의 ADT 구현

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();
  }
}

위 코드는 스택의 ADT를 구현한 코드이다.

그러나 js의 배열은 크기를 동적으로 관리하므로 maxSize()나 isFull(), isEmpty() 함수는 실제 문제를 풀 때 구현할 필요가 없다.

const stack = []; // 스택 초기화

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

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

실제로 위 코드를 보면 maxSize, isFull() 함수는 사용하지 않고 isEmpty() 함수는 stack.length === 0으로 검사한다.

const stack = []; // 스택 초기화

// 스택에 데이터 추가
stack.push(1);
stack.push(2);
stack.push(3);

// 스택에서 데이터 꺼냄
const topElement = stack.pop();
const nextElement = stack.pop();

// 스택의 크기를 구함
const stackSize = stack.length;

// topElement : 3
// nextElement : 2

그런데 push() 함수, pop() 함수를 구현한 부분을 보면

실제 이 함수들이 하는 일은 배열의 push() 메서드, pop() 메서드를 호출하는 것이 전부이다.

그러므로 push() 함수와 pop() 함수는 위와 같이 굳이 구현하지 않아도 된다.

저작자표시 (새창열림)

커쟁이훈