[알고리즘] 스택과 큐 (자바스크립트)

1. 스택

스택이란 후입선출 원칙을 따르는 데이터 집합을 말한다. 재귀 파트에서의 호출 스택으로 사례를 접해본 적이 있다. 외에도 Undo / Redo Funtion 혹은 방문기록 라우팅 등에 스택 알고리즘이 사용된다.

 

배열에서는 Push / Pop 혹은 Shift / Unshift 메서드를 통해 스택을 구현할 수 있다. 맨 앞의 요소를 제어할지, 맨 마지막 요소를 제어할지의 차이이다. 연산도 측면에서는 맨 앞 요소를 변경할 경우 뒤따르는 모든 요소를 새로 배정해주어야 하기 때문에 Shift / Unshft가 열세하다. 그렇기 때문에 배열로 스택을 구현하는 것은 가능은 하지만, 효율 측면에 있어 선호하는 방법은 아니다.

 

연결 리스트를 통한 구현

단일 연결 리스트와 유사하다. 단, 스택에서의 메서드는 상수 시간의 복잡도를 갖는다.

 

클래스 정의

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

 

Push 메서드

  push(val) {
    var newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      var temp = this.first;
      this.first = newNode;
      this.first.next = temp;
    }
    return ++this.size;
  }

 

Pop 메서드

  pop() {
    if (!this.first) return null;
    var temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }

    this.first = this.first.next;
    this.size--;
    return temp.value;
  }

 

2. 큐

선입선출 구조를 갖는 자료구조 집합. 운영체제에서의 Running queue, Block queue에서 만나보았다. 이 외에도 파일 입출력, 업로드 등 많은 컴퓨터의 처리 방식은 큐 알고리즘을 이용한다.

 

배열을 통한 큐 구현

 Push / Shift 혹은 Unshift / Pop 메서드 짝을 통해 큐를 구현할 수 있다.

 

연결 리스트를 통한 구현

  enqueue(val) {
    var newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }

  dequeue() {
    if (!this.first) return null;

    var temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }

 

스택과 마찬가지로, 큐 알고리즘 또한 상수 시간의 삽입 / 제거 복잡도를 갖는다.