Implement Queue Using Stacks

+10

두 개의 스택만 저장 공간으로 사용하는 선입선출 큐를 구현하세요. 스택은 항목을 맨 위에 추가하고, 맨 위 항목을 제거하고 읽으며, 비어 있는지 확인하는 작업만 할 수 있습니다. 큐는 push x(x를 뒤에 추가), pop(맨 앞 항목을 제거하고 반환), peek(맨 앞 항목 반환), empty(큐가 비어 있는가?)를 지원합니다.

연산은 ops에 순서대로 주어지며, args[i]에는 push의 값이 들어 있고 다른 모든 연산에는 0이 들어 있습니다. 비어 있는 상태로 시작하는 하나의 큐에 연산을 실행하고, 각 연산에 대해 문자열 하나를 반환하세요. push에는 "null", pop 또는 peek에는 숫자를 텍스트로 표현한 값, empty에는 "true" 또는 "false"를 반환합니다.

함수

queueOps(ops: string-array, args: integer-array) → string-array

opsstring-array: 연산이 실행되는 순서
argsinteger-array: 각 푸시의 값, 다른 모든 연산의 경우 0
반환값string-array: 연산당 답변 하나를 텍스트로

제약 조건

1 ≤ ops.length ≤ 2000
args.length == ops.length
각 ops[i]는 push, pop, peek 또는 empty입니다.
-10⁹ ≤ args[i] ≤ 10⁹는 push 연산의 경우이고, args[i] == 0은 다른 모든 연산의 경우입니다.
pop과 peek은 큐에 항목이 하나 이상 있을 때만 호출됩니다.

예제

입력: ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
출력: ["null", "null", "1", "1", "false"]
설명: 1을 넣은 다음 2를 넣으면 맨 앞은 1이므로 peek와 pop은 모두 "1"을 반환합니다. 2는 여전히 안에 있으므로 empty는 "false"를 반환합니다.

입력: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
출력: ["null", "null", "4", "null", "7", "9", "true"]
설명: 첫 번째 pop은 가장 오래된 항목인 4를 반환합니다. 7이 아직 기다리는 동안 9가 들어오고, 7보다 나중에 들어왔기 때문에 7 다음에 나옵니다. 그러면 큐가 비어 있으므로 마지막 답은 "true"입니다.

입력: ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
출력: ["true", "null", "-3", "-3", "true"]
설명: 큐는 비어 있는 상태로 시작하므로 첫 번째 답은 "true"입니다. 음수도 다른 숫자와 마찬가지로 저장됩니다. peek와 pop 모두 "-3"을 반환하고, 그러면 큐는 다시 비어 있게 됩니다.

제출 시 숨은 테스트 +15개

후속 질문

다른 연산들의 분할 상환 경계를 깨뜨리지 않으면서 O(1)에 가장 최근 항목을 반환하는 back 연산을 어떻게 추가할 수 있을까요?

풀이

스택은 항목이 들어온 순서의 역순으로 항목을 반환하고, 큐는 같은 순서로 반환합니다. 스택의 항목을 두 번째 스택에 부으면 순서가 한 번 더 뒤집혀, 스택의 순서가 큐의 순서로 바뀝니다. 핵심은 언제 부을지입니다. 매 작업마다 부으면 매번 O(n)의 비용이 들지만, 두 번째 스택이 빌 때만 부으면 각 항목은 한 번만 이동합니다.

push할 때마다 전체 스택을 재정렬합니다

핵심 아이디어

모든 항목을 하나의 스택인 main에 보관하고, 가장 오래된 항목이 맨 위에 오도록 정렬합니다. 그러면 pop, peek, empty는 한 번의 스택 연산으로 처리됩니다.

이제 push가 문제입니다. 새 항목은 대기 중인 모든 항목 아래, 맨 밑에 있어야 하지만 스택에는 맨 위에만 항목을 추가할 수 있습니다. 따라서 main의 모든 항목을 두 번째 스택인 helper로 옮기고, 비어 있는 main에 새 항목을 넣은 다음, 모든 항목을 다시 옮깁니다. 옮길 때마다 순서가 뒤집히고, 두 번 옮기면 원래 순서로 돌아오므로 새 항목은 맨 아래에 놓입니다.

이 방법은 올바르지만, 항목을 넣을 때마다 저장된 모든 항목을 두 번씩 건드립니다. 항목 1,000개를 연속으로 넣으면 대략 2 × (0 + 1 + ... + 999), 즉 거의 100만 번의 이동이 필요합니다. 실제 큐라면 1,000단계면 됩니다.

알고리즘

두 개의 스택을 유지합니다. 가장 오래된 항목이 맨 위에 있는 main과 비어 있는 helper입니다.
push x의 경우: main의 모든 항목을 helper로 꺼낸 다음, x를 main에 넣고, helper의 모든 항목을 다시 main으로 꺼내 넣습니다.
pop 및 peek의 경우: main의 맨 위 항목을 꺼내거나 읽습니다.
empty의 경우: main이 비어 있는지 여부를 반환합니다.
각 답을 텍스트로 기록하고 목록을 반환합니다.

class TwoStackQueue:
    def __init__(self):
        self.main = []    # the oldest item is on top
        self.helper = []

    def push(self, x):
        # Move everything aside, put x at the bottom, move everything back.
        while self.main:
            self.helper.append(self.main.pop())
        self.main.append(x)
        while self.helper:
            self.main.append(self.helper.pop())

    def pop(self):
        return self.main.pop()

    def peek(self):
        return self.main[-1]

    def empty(self):
        return not self.main


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

지연 전송을 사용하는 입력 및 출력 스택

핵심 아이디어

스택마다 별도의 역할을 맡기세요. 모든 삽입은 O(1)에 inbox에 합니다. 제거와 맨 앞 확인은 outbox에서 읽으며, 그 맨 위에는 항상 큐에서 가장 오래된 항목이 있습니다.

outbox가 비어 있는 상태에서 제거나 맨 앞 확인이 들어오면 inbox의 모든 항목을 outbox로 옮깁니다. 가장 최근 항목이 inbox에서 먼저 빠져나오므로 outbox의 맨 아래에 놓이고, 가장 오래된 항목은 맨 위에 놓입니다. outbox가 비어 있을 때만 옮기세요. 여기에 항목이 남아 있는 동안에는 그 항목이 inbox의 어떤 항목보다 오래된 것이므로 먼저 나가야 합니다. 두 번째 예시에서는 첫 번째 제거를 위해 4와 7을 옮기고, 9는 7이 나갈 때까지 inbox에서 기다립니다.

한 번의 제거로 여러 항목을 옮길 수 있지만, 항목별로 작업량을 계산하세요. 각 값은 inbox에 한 번 삽입되고, outbox로 한 번 옮겨지며, 한 번 제거됩니다. 따라서 n번의 연산에는 총 O(n)의 비용이 들고, 연산당 분할 상환 비용은 O(1)입니다. 두 스택이 모두 비어 있으면 큐도 비어 있습니다.

알고리즘

비어 있는 스택 inbox와 outbox를 유지합니다.
push x의 경우: x를 inbox에 푸시합니다.
pop 또는 peek의 경우: outbox가 비어 있으면 inbox의 모든 항목을 꺼내 outbox에 푸시합니다. 그런 다음 outbox의 맨 위 항목을 꺼내거나 읽습니다.
empty의 경우: 두 스택이 모두 비어 있는지 보고합니다.
각 답을 텍스트로 기록하고 목록을 반환합니다.

class TwoStackQueue:
    def __init__(self):
        self.inbox = []    # new items go on top
        self.outbox = []   # the oldest item is on top

    def push(self, x):
        self.inbox.append(x)

    def _refill(self):
        # Only when the outbox is empty: pouring the inbox over reverses it,
        # so the oldest item lands on top.
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

    def pop(self):
        self._refill()
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox


def queueOps(ops, args):
    queue = TwoStackQueue()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            queue.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(queue.pop()))
        elif op == "peek":
            result.append(str(queue.peek()))
        else:
            result.append("true" if queue.empty() else "false")
    return result

함정과 경계 사례

대부분의 버그는 잘못된 순간에 옮겨 붓거나 스택 하나만 확인해서 발생합니다.

outbox에 항목이 남아 있는데 inbox를 outbox에 붓는 경우입니다. 새 항목이 오래된 항목 위에 놓여 먼저 나가므로 큐의 순서가 깨집니다. 두 번째 예에서는 7보다 9가 먼저 나옵니다.
outbox만 보고 empty라고 판단하는 경우입니다. 푸시 직후 새 항목은 inbox에 있으므로, outbox가 비어 있어도 큐는 비어 있지 않습니다.
peek에도 pop과 동일한 보충이 필요하다는 점을 잊는 경우입니다. 첫 번째 푸시 직후 peek을 하면 outbox가 비어 있습니다.
라이브러리 큐를 사용하거나 인덱스로 스택의 맨 아래를 읽는 경우입니다. 핵심은 스택 연산만으로 큐의 순서를 구현하는 것입니다.
문자열 대신 숫자나 불리언을 반환하는 경우입니다. 푸시의 경우 "null"을 포함해 모든 답은 문자열입니다.

자주 묻는 질문4

두 개의 스택으로 만든 큐의 시간 복잡도는 무엇인가요?

push는 O(1)입니다. pop과 peek은 분할 상환 O(1)입니다. 한 번의 호출로 한 스택의 모든 항목을 다른 스택으로 옮길 수 있지만, 각 항목은 수명 동안 최대 한 번만 이동하므로 n번의 연산은 총 O(n)의 비용이 듭니다. 두 스택을 합치면 각 항목을 한 번씩 보관하므로 공간 복잡도는 O(n)입니다.

여기서 분할 상환 O(1)은 무슨 뜻인가요?

이는 단일 작업이 느릴 수 있더라도 전체 시퀀스에서 작업당 평균 비용은 일정하다는 뜻입니다. 항목 1,000개를 쏟아내는 pop의 비용은 그 전에 수행된 저렴한 push 1,000개가 부담합니다. 해당 항목들은 다시 쏟아내지 않기 때문입니다. n개 작업으로 이루어진 어떤 시퀀스도 스택 단계 수가 약 4n을 초과하지 않습니다.

왜 스택이 하나가 아니라 두 개 필요한가요?

스택 하나는 가장 최근 항목만 꺼낼 수 있지만, 큐에는 가장 오래된 항목이 필요합니다. 스택의 맨 아래에 있는 항목에 도달하려면 그 위에 있는 항목을 모두 제거해야 하고, 그 항목들은 대기할 곳이 필요한데, 그곳이 두 번째 스택입니다. 항목을 옮기면 순서가 뒤집히며, 이 역순이 가장 최근 항목부터 가장 오래된 항목 순서로 바꿔 줍니다.

대신 큐를 사용해 스택을 구현할 수 있나요?

네, 하지만 일반적인 방법은 상각 비용을 절감하지 못합니다. 흔히 큐 하나를 사용하는 방법이 있습니다. 새 항목을 추가한 뒤, 기존 항목을 앞에서 하나씩 꺼내 뒤에 추가하면 새 항목이 맨 앞에 오게 됩니다. 이 방법에서는 push가 O(n)이고 pop이 O(1)입니다.

Python

def queueOps(ops, args):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

ops = ["push", "push", "peek", "pop", "empty"]
args = [1, 2, 0, 0, 0]

기대값

["null", "null", "1", "1", "false"]