알고리즘 문제풀이 13_자료구조 stack&queue

자료구조 stack과 queue의 기본 성질을 구현하는 각 메소드를 알고리즘으로 풀어보는 문제였다.
이 문제는 알고리즘보다는 자료구조에 대한 이해를 위한 문제라고 이해하면 될 듯하다.

/**
 * Stack Class
 */
var Stack = function () {
  this.storage = {};
  this.top = 0;
  // top을 이해할때는 스택 저장소의 길이로 이해하면 좋을 듯 하다.
  this.push = function (value) {
    this.storage[this.top] = value;
    this.top++;
  };

  // remove an item from the top of the stack
  this.pop = function () {
    let topValue = this.storage[this.top - 1];
    //실제로 가장 위에 있는 값으 인덱스는 저장소의 길이보다 1개 작다.
    delete topValue;
    this.top--;
  };

  // return the number of items in the stack
  this.size = function () {
    return this.top;
  };
};

/**
 * Queue Class
 */
var Queue = function () {
  var queue = new Stack();
  //스택과 비슷한 성격을 지녔으므로 기본 스택의 형태를 가지고 와서 만들수 있다.
  this.front = queue.top;
  this.storage = queue.storage;
  this.rear = 0;
  //스택과는 다르게 큐에서는 앞과 뒤의 개념이 있으므로 새로 정의해준다.
  //큐에서는 rear이 현재 저장소 안에 있는 요소의 수로 이해하면 된다.
  // called to add an item to the `queue`
  this.enqueue = function (value) {
    if (this.rear === 0) {
      this.storage[this.front] = value;
      this.storage[this.rear] = value;
      this.rear++;
    } else {
      this.storage[this.rear] = value;
      this.rear++;
    }
  };

  // called to remove an item from the `queue`
  this.dequeue = function () {
    if (this.rear === 0) {
      return;
    } else {
      let frontValue = this.storage[this.front];
      delete frontValue;
      this.front++;
      return frontValue;
    }
  };

  // should return the number of items in the queue
  this.size = function () {
    if (this.rear < this.front) {
      return 0;
    } else {
      return this.rear - this.front;
    }
  };
};

큐를 스택을 두번사용해서 구현해보기

Stack을 이용한 Queue는 enqueue는 둘다 뒤에 넣어주는 것이므로 동일한 개념이다(단, 값을 '넣어'주는 거니까 inbox에 push해준다.)
그런데 dequeu가 서로 방법이 다르므로 조금 복잡하다. 
inbox   outbox
| c |   |   |
| b |   |   | 
|_a_|   |_ _|
일 때 dequeue시 a가 inbox에서 제거되어야 하므로
1. inbox.pop()을 a만 남아있을 때까지 반복해주고, (while (inbox.size() !== 1))
inbox   outbox
|   |   |   |
|   |   | b | 
|_a_|   |_c_|
2. a를 pop한 다음 (이 역시 값을 return해주어야지 테스트케이스 line 161, 162의 조건을 만족)(let item = inbox.pop())
inbox   outbox
|   |   |   |
|   |   | b | 
|_ _|   |_c_|
3. 다시 outbox에 있는 것들을 outbox에 아무것도 없을 때까지(while (outbox.size() !== 0)) outbox pop & inbox push
inbox   outbox
|   |   |   |
| c |   |   | 
|_b_|   |_ _|
4. 그리고 dequeue한 값인 a를 return 한다. (return item)
어짜피 이미 구현된 stack을 활용하는 것이므로 Queue 구현 과정에서 this.front나 this.end로 index를 고려해줄 필요는 없다. 
*/
var Queue = function () {
  // Use two `stack` instances to implement your `queue` Class
  var inbox = new Stack();
  var outbox = new Stack();

  // called to add an item to the `queue`
  this.enqueue = function (value) {
    // TODO: implement `enqueue`
    inbox.push(value);
  };

  // called to remove an item from the `queue`
  this.dequeue = function () {
    // TODO: implement `dequeue`
    //inbox안에 요소가 하나만 남을때까지
    while (inbox.size() !== 1) {
      let top = inbox.pop();
      outbox.push(top);
    }
    //그리고 맨 마지막 하나남은 요소를 꺼내주면 일종의 queue에서 pop을 구현한 것이다.
    let item = inbox.pop();
    //그리고 outbox에서 요소가 하나도 남지않을때까지 다시 inbox에서 넣어준다. 위의 그림 참고
    while (outbox.size() !== 0) {
      let value = outbox.pop();
      inbox.push(value);
    }
    return item;
  };

  // should return the number of items in the queue
  this.size = function () {
    // TODO: implement `size`
    return inbox.size();
  };
};