DS_1. Stack과 Queue

자료구조 중 선형구조에서 가장 대표적인 방식이 바로 Stack과 Queue이다. 이러한 구조는 순서가 있으므로 주로 배열을 이용해서 표현한다.

Stack

스택(stack)은 데이터를 한 방향으로 쌓아올리는 방식이다. 이러한 방법은 후입선출(LIFO: Last In First Out)로, 가장 나중에 들어온 자료가 가장 먼저 나간다.

스택의 예는 웹 페이지의 이동 버튼을 들 수 있다. 웹 페이지에서 뒤로 가기(undo)를 누르면 바로 전 페이지로 돌아갈 수 있다. 다시 앞으로 가기(redo)를 누르면 다음 페이지 스택에 있던 페이지를 보여주며 현재 페이지는 이전 페이지 스택에 저장된다.

이러한 스택 구조를 자바스크립트 내에서 구현해 보면 다음과 같다.

class Stack {
  constructor() {
    this.stack = [];
  }
  push(item) {
    this.stack.push(item);
  }
  pop() {
    this.stack.pop();
  }
}

기존 메소드인 push()와 pull()을 이용하면 위와 같이 Stack이라는 클래스를 간단히 구현할 수 있다.

만약 스택의 크기를 알려주는 메소드와 함께 push, pull 메소드까지 직접 구현한다면 어떻게 할까?

class Stack {
  constructor() {
    this.stack = {}; // 객체 형태로 표현하기 위해 초기화
    this.top = 0; // 스택의 최상단을 가리키는 포인터
  }

  size() {
    return this.top; // 스택의 크기 리턴
  }

  push(item) {
    this.stack[this.top] = item;
    this.top += 1;
  }

  pop() {
    if (this.top === 0) {
   	  return; // 만약 빈 스택이라면 아무 행동도 하지 않음(에러 방지)
  	}
    const result = this.stack[this.top-1]; // 마지막 인덱스
    delete this.stack[this.top-1]; // 마지막 인덱스 삭제
    this.top -= 1; // 포인터 -1
    return result; // 제거된 내용 반환
  }
}

위와 같이 구현할 수 있다. 여기서 주의할 점은 초기화 시 배열([])로 구성하게 되면 pop() 메소드를 통해 삭제한 stack의 자리가 다음과 같이 null로 남게 된다.

class Stack {
  constructor() {
    this.storage = []; // 배열 초기화
    this.top = 0;
  }

...
}

const stack = new Stack();
stack.push(`a`); // { "storage": ["a"], "top": 1 }
stack.push(`b`); // { "storage": ["a", "b"], "top": 2 }
stack.push(`c`); // { "storage": ["a", "b", "c"], "top": 3 }
stack.pop(); // { "storage": ["a", "b", null], "top": 2 }

객체({}) 리터럴로 구성하면 다음과 같이 pop()을 이용해 삭제된 후에도 기록이 남지 않는다.

class Stack {
  constructor() {
    this.storage = {}; // 객체 초기화
    this.top = 0;
  }

...
}

const stack = new Stack();
stack.push(`a`); // { "storage": { "0": "a" }, "top": 1 }
stack.push(`b`); // { "storage": { "0": "a", "1": "b" }, "top": 2 }
stack.push(`c`); // { "storage": { "0": "a", "1": "b", "2": "c" }, "top": 3 }
stack.pop(); // { "storage": { "0": "a", "1": "b" }, "top": 2 }

Queue

큐(queue)는 스택과 반대로 데이터를 옆으로 줄짓는 방식이다. 또한 선입선출(FIFO: First In First Out)로, 처음 들어온 자료가 먼저 나간다.

이러한 큐는 주로 소프트웨어와 하드웨어 간의 속도 차이를 보정하기 위한 버퍼(buffer)에서 사용되는 방식이다.

큐를 자바스크립트 내에서 구현해 보면 다음과 같다. 스택과 같이 이미 존재하는 shift와 unshift 메소드를 enqueue와 dequeue로 직접 구현해 보았다.

class Queue {
  constructor() {
    this.queue = {}; // 객체 형태로 초기화
    this.tail = 0; // 큐의 처음을 가리키는 포인터
    this.head = 0; // 큐의 마지막을 가리키는 포인터
  }

  size() {
   	return this.tail - this.head; // 큐의 사이즈 리턴
  }

  enqueue(item) {
    this.queue[this.tail] = item;
    this.tail += 1;
  }

  dequeue() {
    if (this.tail === this.head) {
      return; // 만약 빈 큐라면 아무 행동도 하지 않음(에러 방지)
    }
    const result = this.queue[this.head];
    delete this.queue[this.head]; // 마지막 삭제
    this.head += 1; // head 포인터 -1
    return result; // 제거된 내용 반환
  }
}

const queue = new Queue();
queue.enqueue(`a`); // { "queue": { "0": "a" }, "tail": 1, "head": 0 }
queue.enqueue(`b`); // { "queue": { "0": "a", "1": "b" }, "tail": 2, "head": 0 }
queue.dequeue(); // { "queue": { "1": "b" }, "tail": 2, "head": 1 }

코드를 보면 큐의 맨 처음과 마지막을 가리키는 head와 tail 두 포인터를 사용한다는 점이 스택과는 다른 점이다. 이러한 포인터의 차이가 바로 큐의 사이즈가 되며, enqueue와 dequeue를 반복하면 head 포인터의 위치는 스택과 달리 계속해서 변한다는 특징이 있다.

참고
stackoverflow - How do you implement a Stack and a Queue in JavaScript?
Leonardo Maldonado - Stack and Queue in JavaScript