[Javascript] 스택과 큐 직접 구현하기 (feat. 자료구조, ES6 Class, Node.js)

척척 프로그래밍, 인프준

 

 

 

 

 

 

 

 

 

 

들어가며

자료구조란 데이터를 구성하고 저장하는 방식을 의미합니다. 이를 이용하면 프로그램이 데이터를 빠르게 검색하거나, 정렬하거나, 수정하거나, 추가하는 등의 작업을 수행할 수 있습니다. 예를 들어, 리스트는 데이터를 순서대로 저장하고 검색하는 데 유용하며, 트리는 계층적인 데이터를 저장하고 탐색하는 데 효과적입니다.

 

자료구조를 알고 있으면 데이터를 더 빠르고 효율적으로 처리할 수 있으며, 더 나은 알고리즘을 개발할 수 있습니다. 이는 메모리 사용을 최적화하며, 더 좋은 성능을 제공하는 프로그램을 만들 수 있도록 도와줍니다. 오늘은 가장 기본적인 자료구조인 스택과 큐에 대해 Javascript로 구현해 보며 자세히 알아보려 합니다.

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

스택, Stack

스택은 한 방향으로 데이터를 넣고 뺄 수 있는 자료구조이며 나중에 들어온 데이터가 먼저 나가는 LIFO( Last In First Out )라 불립니다. 일상생활의 예시로 프링글스와 웹 브라우저의 방문기록을 쌓아 뒤로 가기가 같은 개념이며 재귀 알고리즘과 DFS 알고리즘 등이 큐를 활용한 방법입니다.

 

 

 

 

Stack

 

 

스택은 top에 바로 접근 가능하기 때문에 삽입, 삭제의 시간 복잡도는 O(1)입니다. top은 가장 끝쪽에 위치한 데이터를 가리키며 push는 top에 새로운 데이터를 추가하고, pop은 top을 추출합니다.

 

 

class Stack {
  constructor() {
    this.storage = new Object();
    this.size = 0;
  }

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

  pop() {
    let removed = this.storage[this.size];
    delete this.storage[this.size];
    this.size--;
    return removed;
  }

  top() {
    return this.storage[this.size];
  }
}

const stack = new Stack();

stack.push("Apple");
stack.push("Banana");
stack.push("Carrot");

console.log(stack.pop()); // Carrot
console.log(stack.top()); // Banana

 

 

자바스크립트에서 스택은 사실 위처럼 별도의 알고리즘 구현 필요 없이 Array의 push()와 pop() 메서드를 사용하여 활용이 가능합니다. 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

큐, Queue

큐는 한쪽 방향으로 데이터를 넣고 다른 한쪽 방향으로 데이터를 뺄 수 있는 자료구조이며 먼저 들어온 데이터가 먼저 나가는 FIFO( First In First Out )라 불립니다. 프린터의 인쇄 대기열, 음식집에서 줄을 서서 기다려 먼저 온 사람이 먼저 들어가는 것과 같은 개념이며 BFS 알고리즘, 프로세스 관리 등이 큐를 활용한 방법입니다.

 

 

Queue

 

 

큐는 front와 rear의 위치로 데이터의 삽입과 삭제를 처리하므로 시간 복잡도는 O(1)입니다. enqueue로 가장 끝쪽에 데이터를 삽입하며 dequeue로 가장 먼저 들어온 데이터를 추출합니다.

 

 

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

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

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

  dequeue() {
    let removed = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;

    if (this.front === this.rear) {
      this.front = 0;
      this.rear = 0;
    }

    return removed;
  }
}

let queue = new Queue();

queue.enqueue("Dog");
queue.enqueue("Cat");
queue.enqueue("Pig");
queue.enqueue("Cow");

queue.dequeue(); // Dog
queue.dequeue(); // Cat

console.log(queue); // { storage: { '2': 'Pig', '3': 'Cow' }, front: 2, rear: 4 }
console.log(queue.size()); // 2

 

 

자바스크립트 Array에서 push()와 shift() 메서드를 사용하면 큐와 같은 동작 구현이 가능합니다. 하지만 push()와 다르게 shift()의 경우 맨 앞 데이터를 추출하고 정렬되면서 O(N)의 시간 복잡도를 가집니다. 데이터의 양이 적을 때는 문제없지만, 많아질수록 처리 시간에 큰 영향을 줄 수 있습니다. 따라서 다양한 문제를 해결하기 위해 위 코드와 같이 구현하여 사용하는 것이 좋습니다.

 

 

 

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

 

 

 

Reference

beiatrix님의 영상, nnnyeong님의 글, longroadhome님의 글