[코딩연습] LeetCode Implement Queue using Stacks 스택으로 큐 구현하기

LeetCode 문제 중 난이도 Easy인 Implement Queue using Stacks이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

스택의 오퍼레이션을 이용하여 큐의 다음 오퍼레이션들을 구현하라.

push(x) -- 큐의 마지막에 x를 삽입

pop() -- 큐의 맨앞의 요소를 제거

peek() -- 맨앞의 요소를 가져옴

empty() -- 큐가 비었는지 여부를 리턴

스택(Stack)은 LIFO(Last-In, First-Out), 큐(Queue)는 FIFO(First-In, First-Out)의 구조를 가졌다. 스택과 큐를 잘 모른다면 아래 포스팅을 참고한다. 

스택&큐 Stack and Queue

스택으로 큐를 구현하려면, ① 넣을때부터 FIFO로 넣던지 ② 넣을때는 LIFO로 넣고 꺼낼때 FIFO로 꺼내면 된다.

① FIFO처럼 저장하는 방법은 마지막으로 넣는 요소를 스택의 가장 아래(bottom)에 저장하는 것이다. 그러면 스택에서 꺼낼때, 먼저 저장된 요소가 먼저 꺼내진다(FIFO). 코드로 나타내면 아래와 같다.

class MyQueue {
 
    Stack<Integer> myqueue = new Stack<Integer>();
 
    public MyQueue() {
        
    }
 
    public void push(int x) {
        Stack<Integer> temp = new Stack<Integer>();
 
        //myqueue에 있는 요소들을 temp으로 옮겨담는다
        while(!myqueue.isEmpty()){
            temp.push(myqueue.pop());
        }
        //temp의 맨 위에 x를 삽입한다
        temp.push(x);
        
        //myqueue에 다시 옮겨담는다(가장 마지막에 넣은 x가 temp의 가장 아래로 가게됨)
        while(!temp.isEmpty()){
            myqueue.push(temp.pop());
        }
    }
    
    public int pop() {
        return myqueue.pop();
    }
 
    public int peek() {
        return myqueue.peek();
    }
    
    public boolean empty() {
        return myqueue.isEmpty();
    }
}

② 넣을때는 LIFO로 넣고 꺼낼때 FIFO처럼 꺼내는 방법은 저장할때는 그냥 스택의 맨 위(top)에 저장한다. 꺼낼때에는 스택의 맨 마지막에 있는 요소를 불러온다. 코드로 나타내면 아래와 같다.

class MyQueue {
 
    Stack<Integer> myqueue = new Stack<Integer>();
    
    public MyQueue() {
        
    }
    
    public void push(int x) {
        myqueue.push(x);
        
    }
 
    public int pop() {
        Stack<Integer> temp = new Stack<Integer>();
        
        //myqueue의 요소들을 전부 temp에 옮겨담는다
        while(!myqueue.isEmpty()){
            temp.push(myqueue.pop());
        }
        
        //temp의 가장 위에있는 요소를 꺼낸다
        int top = temp.pop();
        
        //원래대로 myqueue에 옮겨담는다
        while(!temp.isEmpty()){
            myqueue.push(temp.pop());
        }
        return top;
    }
    
    public int peek() {
        Stack<Integer> temp = new Stack<Integer>();
        
        while(!myqueue.isEmpty()){
            temp.push(myqueue.pop());
        }
        
        int top = temp.peek();
        
        while(!temp.isEmpty()){
            myqueue.push(temp.pop());
        }
        return top;
    }
    
    public boolean empty() {
        return myqueue.isEmpty();
    }
}