[DS] Stack, Queue

자료구조 체크포인트

• order 자료구조내 데이터가 순서가 보장되는가
• unique 중복된 데이터가 들어갈 수 있는가
• search 검색할 때 얼마나 효율적인지
• modification 수정할 때 얼마나 효율적인지

Stack

스택은 쌓여있는 접시더미와 같이 작동한다.
새로운 접시가 쌓일때도 맨 위에서 쌓이고, 가져갈 때도 맨위에서
가지고 가는것과 비슷하다.

사용할 수 있는 메소드

• push(element) : 요소를 스택의 최상단에 추가한다.
• pop() : 스택의 최상단에서 요소를 제거하고 반환한다.
• size() : 스택의 현재 요소 개수를 반환한다.

메소드 구현

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }

  size() {
    return this.top; 
  }

  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }

  pop() {
    if (this.size() <= 0) {
      return; // 오류처리
    }

    this.top -= 1;
    const result = this.storage[this.top];
    delete this.storage[this.top];

    return result; // 반환하기 위해 변수에 담아둔다.
  }
}

module.exports = Stack;

Queue

Queue는 놀이공원에서 서는 줄과 같이 작동합니다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같습니다. (FIFO: first in, first out).

메소드

• enqueue(element) - 요소를 큐의 뒤에 추가합니다.
• dequeue() - 요소를 큐의 앞에서 제거하고 반환합니다.
• size() - 큐의 현재 요소 개수를 반환합니다.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front;
  }

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }

  dequeue() {
    if (this.size() === 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

module.exports = Queue;