[LeetCode] 232. Implement Queue using Stacks

232. Implement Queue using Stacks

LeetCode

Implement a first in first out (FIFO) queue using only two stacks.
The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty)

Implement the MyQueue class:
- void push(int x) Pushes element x to the back of the queue.
- int pop() Removes the element from the front of the queue and returns it.
- int peek() Returns the element at the front of the queue.
- boolean empty() Returns true if the queue is empty, false otherwise.

두 개의 스택(Stack)만을 사용하여 선입선출(FIFO) 큐를 구현하세요.
구현된 큐는 일반적인 큐의 모든 기능(push, peek, pop, empty)을 지원해야 합니다.

MyQueue 클래스를 구현하세요:
- void push(int x): 요소 x를 큐의 맨 뒤(back)에 추가합니다.
- int pop(): 큐의 맨 앞(front)에 있는 요소를 제거하고 그 값을 반환합니다.
- int peek(): 큐의 맨 앞에 있는 요소를 반환합니다.
- boolean empty(): 큐가 비어있으면 true, 그렇지 않으면 false를 반환합니다.

 

Example

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

---

1. 문제 요구사항 분석

Stack을 이용하여 Queue 구현하기

 

2. 접근 전략

😄 Stack 사용 : Java에서는 Stack 클래스보다 ArrayDeque가 더 성능 좋음

표준 스택 작업	Deque의 스택 전용 메서드	Deque의 양방향 메서드 (동일 동작)
Push	push(e)	addFirst(e)
Pop	pop()	removeFirst()
Peek	peek()	peekFirst()

 

import java.util.*;

class MyQueue {

    private Deque<Integer> stack1;
    private Deque<Integer> stack2;

    public MyQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }
    
    // 넣는 건 무조건 stack1에만
    public void push(int x) {
        stack1.addFirst(x);
    }
    
    // 빼는 건 stack2에서
    // stack2에 없으면 1에서 가져오기
    public int pop() {
        if (stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.addFirst(stack1.removeFirst());
            }
        } 

        return stack2.removeFirst();
    }
    
    // stack2에서 peek
    public int peek() {
        if (stack2.isEmpty()) {
            while(!stack1.isEmpty()) {
                stack2.addFirst(stack1.removeFirst());
            }
        } 

        return stack2.peekFirst();
    }
    
    public boolean empty() {
        if (stack1.isEmpty() && stack2.isEmpty()) return true;
        return false;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */