99클럽 코테 스터디 4일차 TIL + LeetCode 232 (Implement Queue using Stacks, java)

오늘의 학습 키워드

• 큐
• 스택

문제 탐색하기

문제

 

문제 풀이 설계하기

이 문제를 풀기 위해서는 큐와 스택의 개념을 이해하고 있어야합니다. 

 

Queue 란?

선입 선출을 기반으로 동작하는 자료 구조 이고 즉, 먼저 들어간 원소가 제일 먼저 나오는 구조입니다.

 

Stack 이란?

후입 선출을 기반으로 동작하는 자료 구조 이며 즉, 나중에 들어간 원소가 제일 먼저 나오는 구조입니다.

 

stack 구조체를 활용해서 선입선출을 하는 것 처럼 구현하여 문제를 풀어주면 됩니다. 

stack 구조체 2개를 통해서 입력을 받는 stack, 출력을 하는 stack의 역할로 나뉘어서 선언해줍니다.

push 메소드가 호출되면 입력을 받는 stack에 원소가 쌓이게 로직을 작성하면 되고

pop 메소드 또는 peek 메소드가 호출되면 입력을 받는 stack의 원소들을 출력을 하는 stack으로 후입선출의 동작을 살려서 원소를 옮겨주게 됩니다. 그 뒤에 출력 stack에서 후입선출 동작을 통해 제일 나중에 들어간 원소를 출력해주게 되면 이 일련의 과정이 큐의 선입선출과 동일하게 동작하게 됩니다.

 

코드

class MyQueue {

    Stack<Integer> inputStack = new Stack<>();
    Stack<Integer> outputStack = new Stack<>();

    public MyQueue() {}
    
    public void push(int x) {
        inputStack.push(x);
    }
    
    public int pop() {
        while(!inputStack.isEmpty()){
            outputStack.push(inputStack.pop());
        }

        int result = outputStack.pop();

        while(!outputStack.isEmpty()){
            inputStack.push(outputStack.pop());
        }

        return result;
    }
    
    public int peek() {
        while(!inputStack.isEmpty()){
            outputStack.push(inputStack.pop());
        }
    
        int result = outputStack.peek();

        while(!outputStack.isEmpty()){
            inputStack.push(outputStack.pop());
        }

        return result;
    }
    
    public boolean empty() {
        return inputStack.isEmpty();
    }
}

 

오늘의 회고

큐와 스택의 개념에 대해서 한번 더 짚어가는 기회가 되었고 스택을 통해서 큐를 구현할 수 있다는 것을 알 수 있어서 좋았습니다.