[Hackerrank] Queue using Two Stacks

문제 설명

큐(Queue)는 데이터가 추가된 순서를 유지하며, 데이터의 가장 오래된 항목이 가장 먼저 제거되는 추상 데이터 타입입니다. 이는 선입선출(FIFO) 데이터 구조로 불리며, 먼저 큐에 추가된 데이터가 가장 먼저 제거됩니다.

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

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

이 문제에서는 두 개의 스택을 사용하여 큐를 구현해야 합니다. 이후 주어진 q개의 쿼리를 처리합니다. 각 쿼리는 다음 3가지 유형 중 하나입니다:

1. 1 x: 정수 x를 큐의 끝에 추가합니다.
2. 2: 큐의 앞쪽 요소를 제거합니다.
3. 3: 큐의 앞쪽 요소를 출력합니다.

---

입력 형식

• 첫 번째 줄에는 정수 q(쿼리의 개수)가 주어집니다.
• 다음 q개의 줄 각각에는 위에서 설명한 3가지 유형 중 하나의 쿼리가 주어집니다.
  • 1 x는 추가할 값 x가 주어지는 쿼리입니다.
  • 나머지 쿼리는 숫자만 포함됩니다(2, 3).

---

출력 형식

• 유형 3 쿼리마다 큐의 앞쪽 요소를 한 줄에 출력합니다.

일단 자료구조 문제다. 문제를 자세히 안 읽고, 어 그냥 스택 쓰면 해결되는 문제 아닌가? 하고 그냥 무지성으로 큐(deque)를 사용해서 문제를 풀었다.

from collections import deque
a = deque()
n = int(input())
for _ in range(n):
    text = input()
    if text == "2":
        a.popleft()
    elif text == "3":
        print(a[0])
    else:
        x, y = text.split()
        a.append(int(y))

정답처리 되었지만 문제를 다시 읽어보니 2개의 스택을 이용해서 큐를 구현하라고 했다. 그래서 문제를 다시 풀어보았다.

먼저 2개의 스택을 이용한 큐를 구현하였다. 큐를 선언하면 stack_in과 stack_out 2개의 스택을 리스트로 선언한다.

그 후에 enqueue라는 함수는 스택은 stack_in에 해당 데이터를 추가하고, dequeue라는 함수는 stack_out이 비어있다면 stack_in의 모든 요소를 stack_out으로 옮겨주고, stack_out에서 하나를 제거하고 돌려주는 방식이다.

마찬가지로 peek는 stack_out이 비어있다면 stack_in의 모든 요소를 stack_out으로 옮겨주고, stack_out의 마지막 원소를 돌려주는 방식을 이용한다. 코드는 다음과 같다.

class QueueUsingTwoStacks:
    def __init__(self):
        self.stack_in = []  
        self.stack_out = []  

    def enqueue(self, value):
        self.stack_in.append(value)  

    def dequeue(self):
        if not self.stack_out:  
            while self.stack_in: 
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop() if self.stack_out else None  
    def peek(self):
        if not self.stack_out:  
            while self.stack_in:  
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out[-1] if self.stack_out else None

그래서 이를 n번 동안 실행하고, text가 2면 dequeue를, text가 3이면 enqueue를 실행하도록 하고, text가 1과 Y라면 큐에 요소를 추가하도록 했다. 코드는 다음과 같다.

n = int(input())

queue = QueueUsingTwoStacks()
for _ in range(n):
    text = input()
    if text == "2":
        queue.dequeue()
    elif text == "3":
        print(queue.peek())
    else:
        x, y = text.split()
        queue.enqueue(int(y))

ㅁㄴㄹ