[코딩인터뷰 완전정복] 3.4 스택으로 큐

Q : 스택 두 개로 큐 하나를 구현한 MyQueue 클래스를 구현하라.

#include <iostream>

#include "Stack.h"

class MyQueue {

private:

    Stack<int> in;

    Stack<int> out;

    bool inputFlag;

public:

    MyQueue() {

        inputFlag = true;

    }

    void push(int n) {

        if (!inputFlag) {

            while (out.Size > 0) {

                in.push(out.pop);

            }

        }

        inputFlag = true;

        in.push(n);

    }

    int pop() {

        if (inputFlag) {

            while (in.Size > 0) {

                out.push(in.pop);

            }

        }

        inputFlag = false;

        return out.pop();

    }

};

push()는 in stack에서만, pop()은 out stack에서만 한다.

현재 상태가 push 상태인지 pop 상태인지를 확인해 상태가 바뀔 때 다른 스택으로 현재 값을 모두 옮겨준다.

---------------------------------------------

+ 수정

#include <iostream>

#include "Stack.h"

class MyQueue {

private:

    Stack<int> in;

    Stack<int> out;

public:

    MyQueue() {

    }

    void push(int n) {

        in.push(n);

    }

    int pop() {

        if (out.Size() == 0) {

            while (in.Size() > 0) {

                out.push(in.pop());

            }

        }

        if (out.Size() == 0) return NULL;

        return out.pop();

    }

};

 

push()는 in stack에서만, pop()은 out stack에서만 한다.

pop()시 out stack이 비었을 때만 in stack의 값을 모두 out stack으로 옮겨 준다.