[Data Structure] Stack & Queue

자료구조(Data Structure)란 여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한 것으로 배열(Array), 스택(Stack), 큐(Queue), 트리(Tree) 등의 종류가 있으며, 대부분은 특정한 상황의 문제를 해결하는 데 특화되어 있다. 즉 어떠한 상황에 닥쳤을 때, 그에 적합한 자료구조를 사용하여 문제를 해결할 수 있다.

1. Stack

Stack은 쌓여있는 접시 더미와 같이 작동한다. 새로운 접시가 쌓일 때도 맨 위에서 쌓이고, 접시를 가져갈 때도 맨 위에서 가지고 가는 것과 같다. 즉 마지막에 들어온 데이터가 먼저 삭제되는 구조를 가지고 있다(LIFO, Last In First Out). 이를 자바스크립트 코드로 구현해 보면 아래와 같다.

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }
//스택의 현재 요소 개수를 반환
  size() {
    return this.top;
  }
//요소를 스택의 최상단에 추가
  push(element) {
    this.storage[this.top] = element;
    this.top++;
    return element;
  }
//스택의 최상단에서 요소를 제거하고 반환
  pop() {
    if(this.top < 1) {
      return; 
    } //새로 쌓인 요소가 없을 경우, 기존 자료 그대로 리턴

    let removed = this.storage[this.top - 1]; // 인덱스 값을 삭제해야하므로 데이터길이에서 -1
    delete this.storage[this.top - 1];
    this.top--;
    return removed; //새로 쌓인 요소 삭제
  }
}

2. Queue

Queue는 놀이공원에서 서는 줄과 같이 작동한다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같다. 즉 먼저 들어온 데이터가 먼저 삭제된다(FIFO, First In First Out). 이를 자바스크립트 코드로 구현해보면 아래와 같다.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
// 큐의 현재 요소 개수를 반환
  size() {
    return Object.keys(this.storage).length;
  }
//요소를 큐의 뒤에 추가
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++;
  }
//요소를 큐의 앞에서 제거하고 반환
  dequeue() {
   let removed = this.storage[this.front];
   delete this.storage[this.front];
   this.front++;
   return removed;
  }
}