[자료구조] Stack, Queue

Stack

스택은 책을 쌓는 것처럼 데이터를 차곡차곡 쌓아 올리는 자료구조이다.

특징

• LIFO (Last In First Out)
  가장 마지막으로 들어온 데이터가 가장 먼저 나갈 수 있다.
• 데이터가 순서대로 저장되고, 가장 마지막으로 입력된 데이터가 유의미할 때 적합하다.
• 비어있는 스택에서 원소를 추출하려고 할 경우 stack underflow가 발생하고, 스택이 넘치는 경우를 stack overflow라고 한다.

활용

LIFO의 특징을 활용하면 다음과 같은 경우에 스택 자료구조를 사용할 수 있다.

• 웹브라우저 방문기록(뒤로가기)
  페이지를 이동할때마다 스택에 페이지가 푸시된다. 뒤로가기 버튼을 누르면 스택에 저장된 가장 마지막 데이터를 보여준다.
• 역순 문자열 만들기
  문자열 순서대로 스택에 푸시되고, 모든 문자열이 스택에 저장되었다면, 차례로 pop한다.
• 실행취소 (Ctrl+Z)
  뒤로가기와 마찬가지로 실행기록을 스택에 차례로 푸시한다. 실행 취소 시 마지막 기록을 pop한 후 이전 기록으로 돌아간다.
• 재귀적 알고리즘 구현

구현

배열을 사용하지 않은 경우 다음과 같이 구현할 수 있다.

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()<1) {
      return;
    }
    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    return result;
  }
}

Queue

데이터가 줄을 서서 기다리는 것처럼 FIFO 특징을 갖는 자료구조이다.

특징

• FIFO (First In First Out)
  먼저 들어온 데이터가 먼저 나간다. 스택이 하나의 문을 통해 push, pop 되었다면 큐는 입구와 출구가 따로 나누어져있다.
• 데이터가 입력된 순서대로 실행되어야 하는 경우 적합하다.

활용

• 프린터 인쇄 대기열
• 콜센터 고객 대기
• BFS 알고리즘 구현

구현

자바스크립트의 배열의 shift, push 사용해 큐를 흉내내서 구현할 수 있다. 하지만, shift로 첫번째 요소를 제거할 경우, 배열 내부에서는 재정렬이 일어나므로 시간 복잡도가 실제 큐에 비해 커진다. 실제로 큐에서는 첫번째 요소를 제거하는데 O(1)이 걸리지만, 배열을 이용한 경우, 첫번째 요소를 제거하고 배열 전체를 순회하면서 남은 배열들의 요소를 앞으로 한칸씩 당겨주는 데에 추가적인 시간이 소요된다. 따라서 다음과 같이 구현할 수 있다.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    return this.rear - this.front;
  }
  
  enqueue(element) {
    this.storate[this.rear] = element;
    this.rear += 1;
  }
  
  dequeue() {
    if(this.size() === 0) {
      return;
    }
    const result = this.storate[this.front];
    delete this.storate[this.front];
    this.front += 1;
    return result;
  }
}