[99클럽 코딩 스터디 5일차 TIL] LeetCode 225. Implement Stack using Queues 해설 및 풀이 (Java)

99클럽 코딩 스터디 5일차 TIL

LeetCode 225. Implement Stack using Queues

 

https://leetcode.com/problems/implement-stack-using-queues/description/

---

Implement a last-in-first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.
Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.
 

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False
 

Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.
 

Follow-up: Can you implement the stack using only one queue?

 

한글 번역

두 개의 큐만 사용하여 후입선출(LIFO) 스택을 구현합니다. 

구현된 스택은 일반 스택의 모든 기능(push, top, pop, empty)을 지원해야 합니다.

MyStack 클래스를 구현합니다.

void push(int x) 요소 x를 스택 맨 위로 푸시합니다.
int pop() 스택 맨 위의 요소를 제거하고 반환합니다.
int top() 스택 맨 위의 요소를 반환합니다.
boolean empty() 스택이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

참고:

큐의 표준 연산만 사용해야 합니다. 즉, 뒤로 푸시, 앞에서 peek/pop, 크기 및 비어 있음 연산만 유효합니다.
언어에 따라 큐가 기본적으로 지원되지 않을 수 있습니다. 큐의 표준 연산만 사용하는 한 목록이나 데크(양방향 큐)를 사용하여 큐를 시뮬레이션할 수 있습니다.

예제 1:

입력
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
출력
[null, null, null, 2, 2, false]

설명
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

제약 조건:

1 <= x <= 9
push, pop, top, empty에 대한 호출은 최대 100회가 이루어집니다.
pop과 top에 대한 모든 호출은 유효합니다.

후속 조치: 하나의 큐만 사용하여 스택을 구현할 수 있습니까?

---

 

문제 유형

스택
디자인
큐

 

풀이 방법 도출

 

큐(Queue)는 FIFO(First-In-First-Out) 구조입니다.
처음에 들어온 것이 처음에 나온다는 뜻입니다.

스택(Stack)은 LIFO(Last-In-First-Out) 구조입니다.
마지막에 들어온 것이 처음에 나온다는 뜻입니다.
큐의 메서드만 사용할 수 있으므로 직접 배열이나 인덱스 접근은 금지되어 있습니다. 

이 문제는 push, pop, top, empty의 대한 메서드를 구현해야 합니다.
각각의 메서드의 뜻을 알아보고자 합니다.

push()

- 큐나 스택에 추가하는 연산입니다.
- 따라서 q1에 그냥 요소를 넣습니다. (offer 사용)

pop()
- 큐나 스택에서 제거하는 연산입니다.
- q1에 있는 요소들 중 마지막 하나만 남겨두고 전부 q2로 이동합니다.

 

top()
- pop과 비슷하지만 마지막 요소를 다시 q2에 offer()해서 유지시킵니다.
- swap으로 큐 역할을 전환합니다.

 

empty()

- 뜻과 같이 q1이 비었는지 확인합니다. 

 

마지막으로 이 문제는 stack과 queue를 교환하는 함수가 필요하기 때문에

swapQueues() 메서드를 구현해야 합니다.

 

temp에 q1과 q2로 스왑하는 과정의 메서드를 작성합니다.

 

 

시간 복잡도

• push : O(1)
• pop : O(N)
• top : O(N)
• empty : O(1)

---

코드 작성

import java.util.*;

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    // push 연산: q1에 항상 넣기
    public void push(int x) {
        q1.offer(x);
    }

    // pop 연산: q1에서 마지막 요소를 제외한 나머지를 q2로 옮긴 뒤, 마지막 요소를 제거
    public int pop() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int top = q1.poll(); // 마지막 요소가 pop 대상
        swapQueues(); // q1과 q2를 교체
        return top;
    }

    // top 연산: pop과 비슷하지만, 마지막 요소를 제거하지 않고 반환
    public int top() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int top = q1.poll();
        q2.offer(top); // 다시 q2로 넣어서 유지
        swapQueues();
        return top;
    }

    // 비어있는지 확인
    public boolean empty() {
        return q1.isEmpty();
    }

    // 큐 교환 함수
    private void swapQueues() {
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
}