Javascript 자료구조 1. 스택(stack)

대표적인 자료구조들인 스택, 큐, 연결리스트들과 정렬 알고리즘들을 직접 구현해보며 알아보면서 공부하고자 해요!

기본적인 동작 원리나 개념은 이미 알고있지만, 직접 구현해보며 동작원리를 살펴볼께요.

 

오늘은 먼저 스택!

 

스택(Stack)

1. 스택이란?

스택은 가장 많이 사용하는 자료구조로 말 그대로 "쌓여있는 데이터 더미"이고, 입구가 하나로 이루어진 자료구조라고 생각하면 돼요!

그렇기때문에 입구에 계속 넣는다면 처음에 넣은 것이 가장 마지막에 나오게 되는 후입선출[Last In First Out] 특성을 가지게 됩니다.

 

2. 스택의 연산?

스택의 연산에는 두가지 종류가 있어요.

첫번째는 push를 통한 입력, 두번째는 pop을 통한 제거 (플러스로 stack의 길이 ..?!)

스택의 입구는 뒤에 있기 때문에 push는 뒤로 입력, pop은 뒤에서 제거하는 구조가 됩니다.

 

3. 시간복잡도?

push : O(1)

pop : O(1)

search : O(n)

 

4. 구현 (Javascript)!

사실 stack은 Javascript에서 리스트로 쉽게 사용할 수 있어요. (기본적으로 push와 pop이 구현되어있어요!)

하지만 목표는 직접 구현이기때문에 클래스를 만들어서 구현해보도록 하지요.

class Stack {
  #list = [];
  #index = -1;

  push(val) {
    this.#list[++this.#index] = val;
  }
  pop() {
    if (this.#index === -1) throw new Error('Element does not exist.');
    return this.#list[this.#index--];
  }
  size() {
    return this.#index + 1;
  }
  getStack() {
    let stack = [];
    for (let i = 0; i <= this.#index; i++) {
      stack[i] = this.#list[i];
    }
    return stack;
  }
  getTail() {
    if (this.#index === -1) return null;
    return this.#list[this.#index];
  }
}

 

왜 이렇게 구현했는지 살펴볼까요?!

 

1번.

js의 Class 문법엔 es2021 부터 기존과 다르게 private 변수/함수를 만들수가 있어요!

(좀 더 Java 스러워졌다고 할 수 있죠 ㅎ)

기본적으로 외부에서 변수를 접근하지 못하게 만들기위해 #을 붙여 private 변수로 만든 후, 4가지 메소드 push, pop, size, getStack, getTail 정도만 제공했습니다.

 

2번.

getStack 구현 부분이 좀 의문이 들어요.. 사실 그냥 list를 주는 방법을 생각했지만 저는 index를 통해서 입출력을 조절하기 때문에 원치않는 부분까지 노출이 되더라구요... 그래서 list를 private으로 접근하지 못하게 하고, getStack으로 현재 index까지 출력해주는 형식으로 구현했어요. (어떻게하면 list를 쉽게 반환할 수 있을까요?)

 

 

결론!!

class Stack {
  #list = [];
  #index = -1;
  push(val) {
    this.#list[++this.#index] = val;
  }
  pop() {
    if (this.#index === -1) throw new Error('Element does not exist.');
    return this.#list[this.#index--];
  }
  size() {
    return this.#index + 1;
  }
  getStack() {
    let stack = [];
    for (let i = 0; i <= this.#index; i++) {
      stack[i] = this.#list[i];
    }
    return stack;
  }
  getTail() {
    if (this.#index === -1) return null;
    return this.#list[this.#index];
  }
}

const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
console.log(stack.getStack(), stack.size()); // [ 1, 2, 3, 4 ] 4
console.log(stack.pop()); // 4
console.log(stack.getStack()); // [ 1, 2, 3 ]
console.log(stack.pop()); // 3
console.log(stack.getStack()); // [ 1, 2 ]
console.log(stack.pop()); // 2
console.log(stack.getStack()); // [ 1 ]
console.log(stack.pop()); // 1

 

잘 출력되는걸 확인할 수 있어요!