stack, queue

1. stack

마지막에 삽입된 항목이 가장 먼저 제거되는 후입선출 (LIFO, Last In First Out) 방식으로, 마지막에 삽입된 항목만 접근 및 제거가 가능하다.

자바스크립트 배열에서는 push(), pop() 메소드를 이용하여 스택을 구현할 수 있다.

 

 

2. queue

먼저 삽입된 항목이 가장 먼저 제거되는 선입선출 (FIFO, First In First Out) 방식으로, 첫번째 삽입된 항목만 접근 및 제거할 수 있다 .

큐에 항목을 추가하는 것을 enqueue, 항목을 제거하는 것을 dequeue라고 하며, 자바스크립트 배열에서 push(), shift() 메소드를 이용하여 큐를 구현할 수 있다.

 

 

3.1 스택을 이용하여 큐 구현하기

큐의 dequeue() 메소드는 첫번째로 추가한 항목을, 스택의 pop() 메소드는 마지막으로 추가한 항목을 반환한다.

아래와 같이 두 개의 스택을 이용하여 큐의 dequeue() 메소드를 구현할 수 있다.

1) 스택A에 항목을 추가한다.

2) 스택A에 마지막으로 추가된 항목부터 스택B로 옮겨 항목의 순서를 뒤집는다.

3) 스택B의 마지막 항목부터 반환한다.   

 

class Queue {
  constructor (array) {
    this.stackA = array ? [...array] : [];
    this.stackB = [];
  }

  set enqueue (data) {
    this.stackA.push(data);
  }

  get dequeue (){
    if( this.stackB.length < 1 ) {
      while(this.stackA.length > 0) {
        this.stackB.push(this.stackA.pop());
      }
    }
    return this.stackB.pop();
  }
}

const queue = new Queue();
queue.enqueue = 'a';
queue.enqueue = 'b';
queue.enqueue = 'c';
console.log(queue.dequeue); // a
queue.enqueue = 'd';
console.log(queue.dequeue); // b
console.log(queue.dequeue); // c
console.log(queue.dequeue); // d

 

3.2 큐를 이용하여 스택 구현하기

스택의 push() 메소드는 마지막으로 추가한 항목을, 큐의 dequeue() 메소드는 첫번째로 추가한 항목을 반환한다.

아래와 같이 두 개의 큐를 이용하여 스택의 push() 메소드를 구현할 수 있다.

1) 큐A에 항목을 추가한다.

2) 큐A에 마지막 항목 외 나머지 항목을 큐B로 옮긴다 .

3) 큐A에 남은 마지막 항목을 반환한다.

 

class Stack {
  constructor (array) {
    this.queueA = array ? [...array] : [];
    this.queueB = [];
  }

  set push (data) {
    this.queueA.push(data);
  }

  get pop () {
    const length = this.queueA.length;
    while (this.queueB.length < length - 1) {
      this.queueB.push(this.queueA.shift());
    }
    const dequeue = this.queueA.shift();
    this.queueA = [...this.queueB];
    this.queueB = [];
    return dequeue;
  }
}

const stack = new Stack();
stack.push = 'a';
stack.push = 'b';
stack.push = 'c';
console.log(stack.pop);
stack.push = 'd';
console.log(stack.pop);
console.log(stack.pop);
console.log(stack.pop);

 

 

Reference 
배세민. 자바스크립트로하는 자료 구조와 알고리즘 .에이콘. 2019