[HackerRank] Queue using Two Stacks

Problem

---

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed.

A basic queue has the following operations:

• Enqueue: add a new element to the end of the queue.
• Dequeue: remove the element from the front of the queue and return it.

In this challenge, you must first implement a queue using two stacks. Then process q queries, where each query is one of the following 3 types:

1. 1 x: Enqueue element  into the end of the queue.
2. 2: Dequeue the element at the front of the queue.
3. 3: Print the element at the front of the queue.

Input Format

The first line contains a single integer, q, denoting the number of queries.
Each line i of the q subsequent lines contains a single query in the form described in the problem statement above. All three queries start with an integer denoting the query type, but only query 1 is followed by an additional space-separated value, x, denoting the value to be enqueued.

Constraints

• 1 ≤ q ≤ 10^5
• 1 ≤ type ≤ 3
• 1 ≤ |x| ≤ 10^9
• It is guaranteed that a valid answer always exists for each query of type 3.

Output Format

For each query of type 3, print the value of the element at the front of the queue on a new line.

Sample Input

STDIN   Function
-----   --------
10      q = 10 (number of queries)
1 42    1st query, enqueue 42
2       dequeue front element
1 14    enqueue 42
3       print the front element
1 28    enqueue 28
3       print the front element
1 60    enqueue 60
1 78    enqueue 78
2       dequeue front element
2       dequeue front element

Sample Output

14
14

Explanation

Perform the following sequence of actions:

1. Enqueue 42; queue = {42}.
2. Dequeue the value at the head of the queue, 42; queue = {}.
3. Enqueue 14; queue = {14}.
4. Print the value at the head of the queue, 14; queue = {14}.
5. Enqueue 28; queue = {14, 28}.
6. Print the value at the head of the queue, 14; queue = {14, 28}.
7. Enqueue 60; queue = {14, 28, 60}.
8. Enqueue 78; queue = {14, 28, 60, 78}.
9. Dequeue the value at the head of the queue, 14; queue = {28, 60, 78}.
10. Dequeue the value at the head of the queue, 28; queue = {60, 78}.

---

큐(Queue)는 요소가 추가된 순서를 유지하는 추상 자료형으로, 가장 오래된 요소가 가장 먼저 제거되는 특징이 있습니다. 이를 FIFO(First-In-First-Out, 선입선출) 자료 구조라고 하며, 첫 번째로 큐에 추가된 요소가 가장 먼저 제거됩니다.

큐의 기본 연산은 다음과 같습니다:

• Enqueue: 새로운 요소를 큐의 끝에 추가합니다.
• Dequeue: 큐의 앞에서 요소를 제거하고 반환합니다.

이 문제에서는 두 개의 스택을 사용하여 큐를 구현해야 합니다. 그리고 다음과 같은 세 가지 유형의 쿼리를 처리해야 합니다:

1. 1 x: 요소 x를 큐의 끝에 추가합니다.
2. 2: 큐의 앞에서 요소를 제거합니다.
3. 3: 큐의 앞에 있는 요소를 출력합니다.

입력 형식

• 첫 번째 줄에 쿼리의 수 q가 주어집니다.
• 그 다음 q개의 줄에 각 쿼리가 주어집니다. 모든 쿼리는 정수로 시작하며, 쿼리 1의 경우 추가로 삽입할 요소 x가 주어집니다.

제약 조건

• 1 ≤ q ≤ 10^5
• 1 ≤ type ≤ 3
• 1 ≤ |x| ≤ 10^9
• 쿼리 유형 3은 항상 유효한 답이 존재하는 상태에서 호출됩니다.

출력 형식

• 각 3 유형의 쿼리에 대해, 큐의 앞에 있는 요소 값을 새로운 줄에 출력합니다.

 

 

728x90

 

Solution

---

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine().trim());
        
        Stack<Integer> stackEnqueue = new Stack<>();
        Stack<Integer> stackDequeue = new Stack<>();
        
        StringBuilder output = new StringBuilder();
        
        for (int i = 0; i < q; i++) {
            String[] query = br.readLine().split(" ");
            int type = Integer.parseInt(query[0]);
            
            if (type == 1) {
                // Enqueue: 스택에 요소 추가
                int x = Integer.parseInt(query[1]);
                stackEnqueue.push(x);
            } else if (type == 2) {
                // Dequeue: 스택에서 요소 제거
                if (stackDequeue.isEmpty()) {
                    while (!stackEnqueue.isEmpty()) {
                        stackDequeue.push(stackEnqueue.pop());
                    }
                }
                stackDequeue.pop();
            } else if (type == 3) {
                // Print front element
                if (stackDequeue.isEmpty()) {
                    while (!stackEnqueue.isEmpty()) {
                        stackDequeue.push(stackEnqueue.pop());
                    }
                }
                output.append(stackDequeue.peek()).append("\n");
            }
        }
        
        System.out.print(output);
    }
}

 

두 개의 스택을 사용하여 큐를 구현할 때의 핵심은 다음과 같습니다:

1. enqueue: 첫 번째 스택(stackEnqueue)에 요소를 삽입합니다.
2. dequeue 및 peek 연산이 필요할 때:
   • stackDequeue가 비어있으면 stackEnqueue에 있는 모든 요소를 stackDequeue로 옮겨 순서를 반전시킵니다.
   • 그런 다음 stackDequeue의 맨 위 요소를 이용해 dequeue나 peek 연산을 수행합니다.

이 방법은 enqueue 연산이 스택 하나에 추가하는 작업만 포함하므로 O(1)이며, dequeue 및 peek 연산은 최악의 경우에도 모든 요소를 한 번만 이동하므로 시간 효율성을 유지할 수 있습니다.

---

 

1. 입력 처리:
   • BufferedReader를 사용하여 빠르게 입력을 처리하고, 입력된 쿼리를 저장합니다.
2. 두 개의 스택 사용:
   • stackEnqueue는 요소를 추가하는 데 사용하고, stackDequeue는 큐의 앞에서 요소를 제거하거나 출력하는 데 사용합니다.
3. enqueue 연산 (1 x 쿼리):
   • stackEnqueue에 새로운 요소 x를 추가합니다.
4. dequeue 연산 (2 쿼리):
   • stackDequeue가 비어있으면 stackEnqueue에 있는 요소들을 stackDequeue로 모두 옮겨 큐의 앞에서 요소를 제거할 수 있도록 합니다.
   • 그런 후, stackDequeue에서 맨 위 요소를 제거합니다.
5. peek 연산 (3 쿼리):
   • stackDequeue가 비어있으면 stackEnqueue의 모든 요소를 stackDequeue로 옮겨 순서를 맞추고, 맨 위의 요소를 출력합니다.
6. 출력:
   • StringBuilder를 사용해 각 출력 값을 저장한 뒤 한 번에 출력하여 성능을 최적화합니다.

---

이 코드는 두 개의 스택(stackEnqueue와 stackDequeue)을 이용하여 큐(Queue) 기능을 구현한 프로그램입니다. 큐는 선입선출(FIFO) 구조를 가진 자료구조로, 먼저 들어온 데이터가 먼저 나갑니다. 이 프로그램에서는 주어진 입력을 기반으로 요소를 추가, 제거하거나 출력합니다.

코드 구조 및 기능 설명

throws IOException

throws IOException은 IOException이라는 예외를 처리하겠다는 선언입니다. BufferedReader와 같은 입출력 작업에서 발생할 수 있는 예외를 명시하여, IOException이 발생할 경우 이를 호출한 쪽에서 예외를 처리하도록 합니다.

 

BufferedReader

BufferedReader는 입력을 효율적으로 읽기 위해 사용하는 Java 클래스입니다. 일반적으로 콘솔이나 파일에서 데이터를 읽을 때 사용됩니다. 이 클래스는 한 번에 한 줄씩 데이터를 읽어와서 효율적인 입력 처리를 가능하게 합니다.

 

InputStreamReader

InputStreamReader는 InputStream을 문자 스트림으로 변환하는 클래스입니다. System.in은 바이트 입력 스트림이기 때문에, 이를 BufferedReader가 읽을 수 있도록 문자 스트림으로 변환하는 데 사용됩니다.

 

System.in

System.in은 자바에서 표준 입력 스트림을 나타내며, 일반적으로 콘솔 입력을 처리하는 데 사용됩니다. 키보드 입력을 받을 때 주로 사용됩니다.

 

readLine

readLine 메서드는 한 줄을 읽고 문자열로 반환합니다. 사용자가 입력한 한 줄을 읽어들이는 데 적합하며, 개행 문자를 기준으로 데이터를 가져옵니다.

 

trim

trim 메서드는 문자열의 양 끝에 있는 공백 문자를 제거합니다. readLine()으로 입력받은 값에 공백이 있을 경우, 이를 제거해주기 위해 사용합니다.

 

Stack<Integer>

Stack<Integer>는 Java의 Stack 클래스에서 정수형 요소를 저장하는 스택을 선언한 것입니다. 스택은 후입선출(LIFO) 구조를 가진 자료구조입니다. 여기서는 두 개의 스택을 사용해 큐를 구현하고 있으며, 하나는 stackEnqueue로 큐의 끝부분 역할을 하고, stackDequeue는 큐의 앞부분 역할을 합니다.

 

int type = Integer.parseInt(query[0]);와 if 조건

이 줄에서 query[0]을 정수로 변환하여 type에 저장합니다. 이 type은 수행할 작업의 종류를 결정합니다.

• type == 1 : Enqueue 작업으로, 큐에 새로운 요소를 추가합니다.
• type == 2 : Dequeue 작업으로, 큐의 맨 앞 요소를 제거합니다.
• type == 3 : 큐의 맨 앞 요소를 출력합니다.

 

stackDequeue.isEmpty()

stackDequeue.isEmpty()는 stackDequeue가 비어있는지 확인합니다. 비어 있다면 true, 요소가 하나라도 있으면 false를 반환합니다. stackDequeue가 비어있을 경우 stackEnqueue의 요소를 모두 이동시켜 큐의 순서를 유지하는 데 사용됩니다.

 

!stackEnqueue.isEmpty()

!stackEnqueue.isEmpty()는 stackEnqueue가 비어있지 않은지 확인하는 조건문입니다. 요소가 있을 경우, stackEnqueue에서 요소를 꺼내 stackDequeue에 넣어줍니다.

 

stackDequeue.push(stackEnqueue.pop())

이 부분은 stackEnqueue에서 가장 위의 요소를 꺼내(pop), 그 요소를 stackDequeue에 추가(push)하는 코드입니다. stackEnqueue의 요소가 역순으로 stackDequeue에 쌓이게 되어 큐의 순서를 유지할 수 있게 됩니다.

 

stackDequeue.pop()

stackDequeue.pop()은 stackDequeue에서 가장 위의 요소를 제거하고 반환합니다. type == 2 (즉, Dequeue 명령어)일 때 사용되며, 큐의 맨 앞 요소를 제거하는 작업을 수행합니다.

 

output.append(stackDequeue.peek()).append("\n");

output.append(stackDequeue.peek()).append("\n");은 stackDequeue의 가장 위에 있는 요소(즉, 큐의 맨 앞 요소)를 가져와(peek) output에 추가합니다. output은 최종 출력 결과를 저장하는 StringBuilder 객체이며, 모든 type == 3의 결과를 모아서 한 번에 출력하도록 사용됩니다.

 

 

전체적인 동작 요약

1. type == 1일 경우, stackEnqueue에 새로운 요소를 추가합니다.
2. type == 2일 경우, stackDequeue에서 요소를 제거합니다. 만약 stackDequeue가 비어있으면 stackEnqueue의 모든 요소를 stackDequeue로 옮깁니다.
3. type == 3일 경우, stackDequeue의 맨 위 요소를 출력합니다.