[Stack] Implement Stack using Queues

원리

문제의 핵심 : queue 2개로 stack을 구현하라

첫 시도 (틀림)

처음엔 pop 메소드로 풀었는데 너무 간단해서 이게 아니다 싶었다.
역시 문제의 요구사항이 까다로웠다!
요구사항은 바로 queue로 stack을 구현할 것

var MyStack = function () {
    this.array = []
};


MyStack.prototype.push = function (x) {
    // 맨뒤에 추가
    this.array.push(x)
};


MyStack.prototype.pop = function () {
    // 맨뒤 값만 뽑아서 리턴
    return this.array.pop()
};

MyStack.prototype.top = function () {
    // 맨뒤 값 리턴
    return this.array[this.array.length - 1]
};

MyStack.prototype.empty = function () {
    // 비어있는지 확인
    return this.array.length < 1
};

queue와 stack

📌 자료구조에서의 Stack과 Queue
queue는 선입선출(FIFO), stack은 후입선출(LIFO)
자세한 내용은 위의 글에서 확인

최종 제출

queue와 stack을 이론적으로만 알고 있었지 직접 구현해본 것은 처음이다.

왜 pop을 못쓰는지 이해를 못했는데 (요구사항 이해 못한 사람)
"array로 queue처럼 사용하고, array를 stack처럼 사용하는 경우"에 대한 개념이 없었던 것 같다.
이 기회에 개념을 확실하게 잡아서 다행이다!

var MyStack = function () {
    this.queue1 = []
    this.queue2 = []
    // 이 배열은 queue로만 사용 가능하다고 제한되어있는 상태.
    // 따라서 push, shift만 사용이 가능함. pop 사용 불가
  // queue1, queue2를 가지고 stack처럼 작동해야한다

};
MyStack.prototype.push = function (x) {
    this.queue1.push(x)
    // push 동작은 queue와 stack 동일하다. 여기서 종료
};

MyStack.prototype.pop = function () {
    // queue1, queue2를 가지고 stack처럼 작동해야한다
    // 맨뒤 값만 뽑아서 리턴
    // 하지만 queue의 출구는 맨 앞에만 있는데 어떻게 맨뒤값을 뽑을 수 있을까?
    // 반복문을 돌며 임시보관용 queue에 넣는다? 여기서는 어떤 생각을 해야하지?

    while (this.queue1.length > 1) {
        // length가 2일때까지는 빼서 queue2에 넣어야함. 그래서 마지막 한개만 남긴다
        this.queue2.push(this.queue1.shift())
        // 반복문을 돌면서 임시 queue에 차례대로 넣으면 아래처럼 된다
        // queue1 = [1,2,3]
        // queue2 = [3,2,1]
    }

    // 현재 
    const popped = this.queue1.shift()
    // queue1에 남은 한개가 제일 마지막에 추가되었던 요소니까 이걸 리턴

    // 큐들의 값을 원복한다.
    [this.queue1, this.queue2] = [this.queue2, this.queue1]
    // 이때 queue1과 queue2의 교체가 왜 필요한가?
    // queue1에 데이터를 추가하고, 맨뒤 값을 꺼내기 위해 queue2로 하나씩 추가해뒀다.
    // 그래서 지금 queue1은 빈 배열, queue2에는 데이터가 남아 있음
    // 하지만 다음 push, pop 동작도 똑같은 방식으로 이어가야한다.
    // 기존처럼 메인 큐인 queue1에 데이터가 남아있고, queue2는 비어있는 임시 큐로 되돌아가야하는 것.
    return popped
};

MyStack.prototype.top = function () {
    // queue1, queue2를 가지고 stack처럼 작동해야한다
    // 맨뒤 값 리턴
    while (this.queue1.length > 1) {
        // length가 2일때까지는 빼서 queue2에 넣어야함. 그래서 마지막 한개만 남긴다
        this.queue2.push(this.queue1.shift())
    }
    const top_value = this.queue1.shift()
    this.queue1.push(top_value)
    // 근데 이건 제거가 아니라 유지해야하니까 다시 넣는다
    // 4. 큐들의 값을 원복한다.
    [this.queue1, this.queue2] = [this.queue2, this.queue1]
    return top_value
};

MyStack.prototype.empty = function () {
    // 비어있는지 확인
    return this.queue1.length === 0
};