[LeetCode] - 232. Implement Queue Using Stacks

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Implement Queue Using Stacks" 문제입니다.

--> https://leetcode.com/problems/implement-queue-using-stacks/description/

 

문제 : 

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.

 

Notes :

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

---

Example 1 :

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

 

Constraints :

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

 

Follow-up :

Can you implement the queue such that each operation is amortized O(1) time complexity?

In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

---

주어진 문제는 두 개의 스택을 사용하여 FIFO(First-In-First-Out) 큐를 구현하는 것입니다. 큐의 기본 연산은 다음과 같습니다 :

1. push(int x) : 큐의 뒤에 요소 x를 추가합니다.
2. pop() : 큐의 앞에 있는 요소를 제거하고 반환합니다.
3. peek() : 큐의 앞에 있는 요소를 반환합니다. (제거하지 않음)
4. empty() : 큐가 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

큐의 구현은 두 개의 스택을 사용하여 이루어지며, 스택의 표준 연산(상단으로의 푸시, 상단에서의 팝, 상단 조회, 비어 있는지 확인)만을 사용할 수 있습니다.

 

class MyQueue {
    private Stack<Integer> q;
    private Stack<Integer> q2;

    public MyQueue() {
        q = new Stack<>();
        q2 = new Stack<>();
    }
    
    public void push(int x) {
        q.push(x);
    }
    
    public int pop() {
        if (q2.isEmpty()) {
            while (!q.isEmpty()) {
                q2.push(q.pop());
            }
        }
        return q2.pop();
    }
    
    public int peek() {
        if (q2.isEmpty()) {
            while (!q.isEmpty()) {
                q2.push(q.pop());
            }
        }
        return q2.peek();
    }
    
    public boolean empty() {
        return q.isEmpty() && q2.isEmpty();
    }
}

 

이번 문제도 제가 알고리즘 수업 때 본 거라 금방 풀 수 있었습니다. 제 블로그 게시물 중에도 비슷한 류의 문제 풀이가 있습니다 혹시 모르니 링크를 달아드리겠습니다 : https://jayj-blog.tistory.com/56

[LeetCode] - 225. Implementing Stack Using Queues

 

이 코드는 두 개의 스택을 사용하여 큐(FIFO)를 구현하는 예시입니다. 각각의 스택을 이용하여 큐의 기본 연산인 push, pop, peek, empty를 구현합니다.

스택은 LIFO(Last-In-First-Out) 구조를 가지며, 두 스택을 활용하여 큐의 동작을 모방합니다.

코드 설명

1. 스택 초기화 :
   • q와 q2는 Stack<Integer>의 인스턴스로, 각각 스택으로 초기화됩니다.
   • q는 새 요소를 저장하는 데 사용되고, q2는 요소를 제거할 때 사용됩니다.
2. push(int x) 메소드 :
   • q.push(x);를 사용하여 q 스택에 새로운 요소를 추가합니다.
   • 이 연산은 O(1) 시간 복잡도를 가집니다.
3. pop() 메소드 :
   • if (q2.isEmpty()) 조건문을 통해 q2가 비어 있는지 확인합니다.
   • q2가 비어 있다면, q의 모든 요소를 q2로 이동합니다. 이 과정에서 순서가 반전되어, q2의 상단에 가장 오래된 요소가 위치하게 됩니다.
   • return q2.pop();를 통해 q2의 상단 요소를 제거하고 반환합니다.
   • 요소 이동은 최악의 경우 O(n) 시간이 소요되지만, 전체적으로 Amortized O(1)입니다.
4. peek() 메소드 :
   • if (q2.isEmpty()) 조건문을 통해 q2가 비어 있는지 확인합니다.
   • q2가 비어 있다면, q의 모든 요소를 q2로 이동하여 요소의 순서를 맞춥니다.
   • return q2.peek();를 통해 q2의 상단 요소를 반환합니다. 이 요소는 큐의 맨 앞 요소와 같습니다.
   • 요소 이동은 최악의 경우 O(n) 시간이 소요되지만, 전체적으로 Amortized O(1)입니다.
5. empty() 메소드 :
   • return q.isEmpty() && q2.isEmpty();를 사용하여 두 스택이 모두 비어 있는지 확인합니다.
   • 이 메서드는 O(1) 시간 복잡도를 가집니다.

• 시간 복잡도 :
  • push : O(1) - 요소를 q에 추가하는 연산은 상수 시간에 수행됩니다.
  • pop : Amortized O(1) - q2가 비어 있는 경우에만 요소를 이동하며, 전체적으로 요소 하나당 한 번씩만 이동합니다.
  • peek : Amortized O(1) - pop과 동일한 이유로 O(1)의 평균 시간 복잡도를 가집니다.
  • empty : O(1) - 두 스택이 비어 있는지 확인하는 연산은 상수 시간에 수행됩니다.
• 공간 복잡도 :
  • O(n) - 두 스택 q와 q2는 최대 n개의 요소를 저장할 수 있으므로 공간 복잡도는 O(n)입니다.

---

Runtime 결과