스택으로 큐를 구현해보고, 큐로 스택을 구현해보면서 분석해보자.

Implement Queue using Stack, Implement Stack using Queue

역사

스택은 누가 만든걸까?
기록으로만 보면 아이디어는 1946년 우리 튜링 아저씨가 냈고 특허를 낸건 독일사람임.
튜링은 아시다시피 2차 세계대전, 전쟁때 컴퓨터의 발전속도를 굉장히 끌어올린 사람이다.
이 사람이 전쟁중에 암호해독기 만들었거든 튜링기계인가 먼가
폰 노이만(주기억장치, 보조기억장치 etc… 이 컴퓨터 구조 만든사람) 제자임
결론적으로 이 글은 영국에서 시작되었으며… 하아… 심지어 스택이란게 만들어진지 50년도 안되었음.
그럼 큐는? 그 이전 1900년대 초반부터 있었던 큐잉이론이란게 있다고 한다.
뭐 암튼 막상 컴퓨터에서 활발하게 쓰여진 것은 전쟁과 함께 컴퓨터가 발전된 시기.
알고리즘이 컴퓨터과학에서 유용하게 작용하기 시작하고, 많은사람들이 컴퓨터를 알게 된 시기가 아닐까 싶다.
2차세계대전부터 그냥 다같이 썼다고 생각하자. 전쟁은 이겨야지.

왜 구현함?

기본적인 스택과 큐는 일단 굉장히 유사하다.

1. 둘다 1차원적으로 입력과 출력이 나열된다.
2. 입/출력 1번 -> 1개 값이 입/출력 된다.
3. 복잡도가 똑같다 (추가, 삭제에 효율적인 모습을 보인다 근데 중간에 넣는 기능이 없다… ㅋㅋㅋㅋㅋ)
4. 다른점은 스택은 LIFO , 큐는 FIFO

Last In First Out / First In First Out 이다.
스택은 벽돌쌓으면 허(리)아(포) , 큐는 줄서세요 폴리스라인 (삐)(뽀)(삐)(뽀)… ㅈㅅ

스택을 이용해서 큐를 구현해보자

사실 자바스크립트에는 Array객체가 있어서 내장메소드로 엄청쉽게 구현이 된다. 하지만 이건 공부용.

이거는 pop이 중요하다.
스택 두개를 쓴다. 스택과 유사하게 push와 pop 만 사용
1번 스택이 비어버릴 때까지 2번 스택에 붓는다고 생각하면 메인1,2,3,4,5 >> 서브5,4,3,2,1 이런식으로 뒤집혀지게 된다.
여기서 뒤집힌 스택을 pop 하나만 해주면 큐처럼 선입 선출 First In First Out 의 효과가 된다.
다시 원래대로 돌려놔주면 pop기능 완성
나머지 메소드는 간단하게 내장기능을 사용하겠다. (추후에 구현해봐야지)

var MyQueue = function() {
  this.inStack = [];
  this.outStack = [];
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
  return this.inStack.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
  let res; 
  while (this.inStack.length !== 0) {
    this.outStack.push(this.inStack.pop());
  }
  res = this.outStack.pop();
  while (this.outStack.length > 0) {
    this.inStack.push(this.outStack.pop());
  }
  this.outStack = [];
  return res;
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
  return this.inStack[0];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
  return this.inStack.length === 0;
};

큐를 이용해서 스택을 구현해보자

큐 두개를 쓴다. (unshift 와 pop만 사용 해서 큐와 유사하게 사용)
이거는 푸시가 중요하다.
큐에 넣긴 넣을건데 한번 다른 큐에 다 넣고! 메인큐에 먼저 넣고 서브큐를 넣어준다.
이것도 큐가 뒤집힌 형태가 되는것이다. 1,2,3,4,5메인큐 >> 5,4,3,2,1서브큐 >> 1,2,3,4,5,6 하고 나갈땐 6 부터
여기서 메인큐를 pop 하나만 해주면 스택처럼 후입선출 Last In First Out 의 효과가 된다.
나머지 메소드는 간단하게 내장기능을 사용하겠다. (추후에 구현해봐야지)

/**
 * Initialize your data structure here.
 */
var MyStack = function() {
  this.inQ = [];
  this.subQ = [];
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}
 */
MyStack.prototype.push = function(x) {
  let res;
  while (this.inQ.length !== 0) {
    this.subQ.unshift(this.inQ.pop());
  }
  res = this.inQ.unshift(x);
  while (this.subQ.length > 0) {
    this.inQ.unshift(this.subQ.pop());
  }
  return res;
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
  return this.inQ.pop();
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
  return this.inQ[this.inQ.length - 1];
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
  return this.inQ.length === 0;
};