HackerRank : A Tale of Two Stacks

Queues: A Tale of Two Stacks | HackerRank

 

문제 요약

• 2개의 Stack을 이용해서 Queue와 동일한 로직을 만들어 보세요.
• input 값으로 다음과 같이 입력이 가능합니다
  • q : 쿼리의 갯수 (최초에 1회 입력)
  • 1 x : x를 큐에 저장
  • 2 : 큐의 맨 앞 (가장 오래된 값)을 제거
  • 3 : 큐의 맨 앞 (가장 오래된 값)을 출력

 

핵심 요약

 

해당 LeetCode의 문제와 흡사한 문제 유형입니다.

필요한 기능은 크게 다음 3가지로, 각각을 2개의 Stack을 이용해 구현합니다.

 

• enqueue : 큐에 값을 저장 
• dequeue : 큐의 첫 번째 값을 제거
• peek : 큐의 첫 번째 값을 출력

 

문제 풀이

 

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        MQ q = new MQ();
        int cnt = 0;
        
        Scanner sc = new Scanner(System.in);
        cnt = sc.nextInt();
        
        while(cnt>0){
            int cmd = sc.nextInt();
            if(cmd == 1) {
                q.enqueue(sc.nextInt());
            } else if(cmd == 2){
                q.dequeue();
            } else if (cmd == 3){
                System.out.println(q.peek());
            }
            cnt--;
        }
    }
    
    public static class MQ {
        private Stack<Integer> s1 = new Stack<>();
        private Stack<Integer> s2 = new Stack<>();
        
        public void enqueue(int num){
            s1.push(num);
        }
        
        public void dequeue() {
            // push all elements into s2 and then pop
            if(!s2.empty()) {
                s2.pop();
            } else {
                while(!s1.empty()){
                    s2.push(s1.pop());
                } s2.pop();
            }
        }
        
        public int peek() {
            // push all elements into s2 and then return the peek
            if(!s2.empty()) {
                return s2.peek();
            } else {
                while(!s1.empty()){
                    s2.push(s1.pop());
                } return s2.peek();
            }
        }
    }
}

s1에는 stack과 동일한 로직을 기반으로 값을 저장해주기만 합니다.

반면 s2에서는 dequeue, peek가 이루어지며, 값을 제거하거나 첫 번째 값을 출력해줍니다.

이때 s2에서는 이루어지는 dequeue와 peek는 queue의 remove, peek와 동일한 기능을 갖게 됩니다.

이해가 안될 경우, 위의 코드를 따라 그림을 그려가며 예시를 생각하면 쉽게 이해할 수 있습니다.