Implement Stack using Queues

+10

저장소로 큐만 사용하는 후입선출 스택을 구현하세요. 큐는 뒤에 항목을 추가하고, 맨 앞 항목을 제거하거나 읽고, 크기를 반환할 수 있습니다. 스택은 push x(x를 맨 위에 놓기), pop(맨 위 항목을 제거하고 반환하기), top(맨 위 항목을 반환하고 그대로 두기), empty(스택이 비어 있는지 확인하기)를 지원합니다.

연산은 ops에 순서대로 주어지며, args[i]에는 push에 사용할 값이, 그 외의 경우에는 0이 들어 있습니다. 비어 있는 스택 하나에 연산을 실행하고, 각 연산마다 문자열 하나씩 반환하세요. push에는 "null", pop 또는 top에는 숫자를 문자열로, empty에는 "true" 또는 "false"를 반환합니다.

함수

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

opsstring-array: 연산이 실행되는 순서
argsinteger-array: 각 push의 값, 그 외 모든 연산에는 0
반환값string-array: 연산당 하나의 답변을 텍스트로

제약 조건

1 ≤ ops.length ≤ 1000
args.length == ops.length
모든 ops[i]는 push, pop, top 또는 empty입니다.
-10⁹ ≤ args[i] ≤ 10⁹는 푸시 연산의 경우이고, 그 외의 연산에서는 args[i] == 0입니다.
pop과 top은 스택에 항목이 하나 이상 있을 때만 호출됩니다.

예제

입력: ops = ["push", "push", "top", "pop", "empty"]args = [1, 2, 0, 0, 0]
출력: ["null", "null", "2", "2", "false"]
설명: 2가 마지막에 들어갔으므로 맨 위에 있습니다. top과 pop은 모두 "2"를 반환합니다. 1은 아직 안에 있으므로 empty는 "false"를 반환합니다.

입력: ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
출력: ["null", "null", "7", "null", "9", "4", "true"]
설명: 첫 번째 pop은 가장 최근 항목인 7을 반환합니다. 그런 다음 9가 4 위에 올라가고 4보다 먼저 나가므로, 다음 pop은 "9"와 "4"를 반환하고 스택은 비게 됩니다.

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

후속 질문

큐 하나만 유지하면서 작업을 push에서 pop으로 옮겨 push를 O(1)로 만들 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

큐는 항목을 가장 오래된 것부터 내보내고, 스택은 가장 최근 항목부터 내보내며, 큐는 맨 뒤 항목을 절대 보여 주지 않습니다. 사용할 수 있는 도구는 맨 앞에서 디큐하고 맨 뒤에 인큐하는 것뿐이며, 이렇게 하면 큐가 회전합니다. 가장 최근 항목을 읽어야 할 때나 그 항목이 도착한 직후에 큐를 회전시켜 맨 앞으로 가져오세요.

두 개의 큐를 사용해 pop할 때 가장 최신 항목 꺼내기

핵심 아이디어

큐 main의 항목을 도착 순서대로 유지하여, 가장 최근 항목이 뒤쪽에 오도록 합니다. 따라서 push는 한 번의 enqueue입니다. pop은 항목 하나만 남을 때까지, 즉 가장 최근 항목만 남을 때까지 나머지 모든 항목을 두 번째 큐 spare로 옮깁니다. 그 항목을 dequeue하고 큐를 맞바꿉니다. 이제 spare에 나머지 항목이 원래 순서대로 들어 있기 때문입니다. top도 같은 방식으로 순회하지만, 가장 최근 항목을 spare에 enqueue하기도 합니다.

pop 또는 top을 수행할 때마다 저장된 모든 항목을 한 번씩 옮깁니다. 500번 push하고 매번 top을 수행하면 비용은 1 + 2 + ... + 500, 즉 약 125,000번의 이동입니다.

알고리즘

두 개의 큐를 유지합니다. 도착 순서대로 항목이 들어 있는 main과 비어 있는 spare입니다.
push x의 경우: x를 main에 추가합니다.
pop과 top의 경우: 하나만 남을 때까지 항목을 main에서 spare로 옮긴 다음, 남은 항목을 꺼내 답으로 반환합니다. top의 경우에는 그 항목도 spare에 추가합니다. 두 큐를 서로 바꿉니다.
empty의 경우: main이 비어 있는지 보고합니다.

from collections import deque

class QueueStack:
    def __init__(self):
        self.main = deque()    # the oldest item at the front, the newest at the back
        self.spare = deque()   # empty between operations

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

    def _move_all_but_newest(self):
        # Pass every item except the newest to the spare queue, in order.
        while len(self.main) > 1:
            self.spare.append(self.main.popleft())

    def pop(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.main, self.spare = self.spare, self.main
        return newest

    def top(self):
        self._move_all_but_newest()
        newest = self.main.popleft()
        self.spare.append(newest)   # top keeps the item
        self.main, self.spare = self.spare, self.main
        return newest

    def empty(self):
        return not self.main

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

하나의 큐, 푸시할 때마다 회전

핵심 아이디어

항상 큐를 스택 순서로 유지합니다. 가장 최근 항목이 맨 앞에 옵니다. 그러면 pop은 dequeue가 되고, top은 맨 앞을 읽으며, 두 번째 큐는 필요하지 않습니다. 새 항목 x는 뒤쪽에 들어가 오래된 항목들 뒤에 놓입니다. 이 항목들은 이미 가장 최근 항목이 앞에 오도록 정렬되어 있습니다. 맨 앞 항목을 dequeue한 다음 size-1번 뒤에 enqueue합니다. 각 단계에서 오래된 항목 하나가 x 뒤로 이동하면서 순서가 유지되므로, 마지막에는 x가 맨 앞에 옵니다.

첫 번째 예시에서 [1]에 2를 push하면 [1, 2]가 되고, 한 번 회전하면 [2, 1]이 됩니다. k개 항목에 push를 수행하려면 k번 회전해야 하므로 push는 O(n)이고, 나머지 연산은 O(1)입니다.

알고리즘

큐 하나를 유지하며, 그 맨 앞은 항상 스택의 맨 위에 해당합니다.
push x의 경우: x를 enqueue한 다음, size-1번 반복하여 맨 앞 항목을 dequeue하고 다시 enqueue합니다.
pop의 경우: 맨 앞 항목을 dequeue하여 반환합니다.
top의 경우: 맨 앞 항목을 제거하지 않고 반환합니다.
empty의 경우: 큐가 비어 있는지 여부를 알립니다.

from collections import deque

class QueueStack:
    def __init__(self):
        self.queue = deque()   # the newest item is always at the front

    def push(self, x):
        self.queue.append(x)
        # Rotate the older items behind x, so x comes out first.
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        return self.queue.popleft()

    def top(self):
        return self.queue[0]

    def empty(self):
        return not self.queue

def stackOps(ops, args):
    stack = QueueStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            result.append(str(stack.pop()))
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append("true" if stack.empty() else "false")
    return result

함정과 경계 사례

size번 회전하는 대신 size-1번 회전하는 경우. 한 바퀴를 모두 돌면 x가 맨 뒤에 남으므로, 다음 pop에서 가장 오래된 항목이 반환됩니다.
x를 enqueue하기 전에 회전하는 경우. 더 오래된 항목들이 원을 따라 이동하고 x는 여전히 맨 뒤에 놓입니다.
큐를 두 개 사용하는 경우, 항목을 top에 다시 넣지 않는 경우. 그러면 다음 pop에서 그 아래에 있는 항목이 반환됩니다.
큐를 두 개 사용하는 경우, 큐를 서로 바꾸지 않는 경우. 항목들이 spare에 남고, empty가 너무 일찍 "true"를 반환합니다.
숫자나 불리언을 반환하는 경우. 푸시의 경우 "null"을 포함해 모든 답은 문자열입니다.

자주 묻는 질문3

큐로 구현한 스택의 시간 복잡도는 얼마인가요?

push할 때마다 회전하는 큐 하나를 사용하면 push는 O(n)이고 pop, top, empty는 O(1)입니다. pop할 때마다 항목을 이동하는 큐 두 개를 사용하면 push는 O(1)이고 pop과 top은 O(n)입니다. 어느 쪽이든 각 항목은 한 번씩 저장되므로 공간 복잡도는 O(n)입니다.

큐로 만든 스택이 스택으로 만든 큐보다 느린 이유는 무엇인가요?

한 스택의 내용을 다른 스택에 부으면 순서가 뒤집히므로, 한 번의 붓기로 스택의 순서가 큐의 순서가 되고 각 항목은 전체 과정에서 한 번 이동합니다. 큐 사이에서 항목을 옮기면 순서가 유지되므로 어떤 이동도 순서를 뒤집지 않습니다. 그래서 여기서 연산 하나의 비용은 항상 O(n)입니다.

push와 pop 중 어느 연산의 비용이 더 커야 할까요?

더 드문 작업에 비용을 부담시키세요. 스택이 커지는 횟수보다 top과 pop으로 읽는 횟수가 훨씬 많다면, push할 때 회전시켜 모든 읽기를 O(1)로 만드세요. 몇 번의 pop 전에 push가 많이 발생한다면, push는 O(1)로 유지하고 pop할 때 이동 작업을 하세요.

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

테스트 #1

테스트 #2

테스트 #3

인자들

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

예상 출력

["null", "null", "2", "2", "false"]