[LeetCode] - 225. Implementing Stack Using Queues

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Implementing 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, Last In First Out) 스택을 구현하는 것입니다. 구현된 스택은 일반적인 스택의 기능인 push, pop, top, empty를 지원해야 합니다.

import java.util.LinkedList;
import java.util.Queue;

public class MyStack {
    private Queue<Integer> stackQueue;

    public MyStack() {
        // Initialize the queue in the constructor
        this.stackQueue = new LinkedList<>();
    }
    
    public void push(int x) {
        stackQueue.add(x);
        for (int i = 1; i < stackQueue.size(); i++) {
            stackQueue.add(stackQueue.remove()); // 1,2,3 되던게 3,2,1 가 되게끔 만들어서
        }
    }
    
    public int pop() {
        return stackQueue.remove(); //queue 의 특성상, remove를 하면 앞에 꺼를 삭제하는데, 아까 push를 거꾸로, 마치 queue.reverse() 한거 마냥 했으니 사실상 가장 뒤를 remove 한 거임
        
    }
    
    public int top() {
        return stackQueue.peek();

    }
    
    public boolean empty() {
        return stackQueue.isEmpty();
    }
}

 

이 문제는 제가 알고리즘에서 자료구조 파트를 배울 때 해본 문제라서 쉽게 풀었습니다. 

위 코드는 하나의 큐를 사용하여 스택을 구현하는 방법입니다. 이를 통해 후입선출(LIFO) 구조를 달성합니다. 핵심 아이디어는 새로운 요소를 큐에 추가한 후, 큐의 나머지 요소를 모두 뒤로 이동시키는 것입니다. 이렇게 하면 새로운 요소가 큐의 앞에 위치하게 되어 마치 스택의 맨 위에 있는 것처럼 동작합니다.

---

내 코그 Runtime 결과