LeetCode 데일리 챌린지 시리즈 #1

문제 설명

두 개의 대기열만 사용하여 후입선출(LIFO) 스택을 구현합니다. 구현된 스택은 일반 스택의 모든 기능(push, top, pop 및 empty)을 지원해야 합니다.

해결책

코드를 구현하기 전에 진행 방법에 대해 생각해 봅시다. 이 문제를 해결하는 방법에는 두 가지가 있습니다.

#### 2개의 대기열 사용: 2개의 대기열을 사용하여 스택을 구현할 수 있습니다. 두 가지 방법으로 처리할 수 있습니다.

푸시 방법을 비싸게 만들기

팝 방식을 비싸게 만드는

결정은 신청서를 기반으로 합니다. 우리의 경우에는 어느 쪽이든 괜찮습니다.


비싼 푸시 방법:

나머지 요소가 Queue1에 저장되는 동안 요소를 Queue2로 푸시합니다. 그런 다음 Queue1에서 요소를 팝하고 Queue2로 푸시합니다. Queue1과 Queue2의 이름을 바꿉니다.
새 요소가 추가될 때마다 이 프로세스를 반복하면 스택에서 튀어나올 것으로 예상되는 순서대로 요소를 갖게 됩니다. 따라서 우리는 스택을 달성했습니다.


비싼 팝 방법:

팝해야 할 때마다 - Queue1에서 마지막 요소를 제외한 모든 요소를 ​​대기열에서 빼고 Queue2에 넣습니다. Queue1에서 마지막 요소를 대기열에서 빼고 저장합니다(반환할 결과임). Queue1과 Queue2의 이름을 바꿉니다. 저장된 요소를 반환합니다. 따라서 우리는 터지는 동안 LIFO 주문을 갖게 될 것입니다.

#### 1개의 대기열 사용: 1개의 대기열만 사용하여 위의 동작을 수행할 수 있습니다.

대기열의 길이를 취하십시오. n이라고 말하십시오.

요소를 대기열에 넣습니다.

n까지 루프를 실행합니다. 큐에서 요소를 제거하고 큐에 넣습니다. 이렇게 하면 새 요소가 대기열의 첫 번째 요소가 됩니다.
대기열에서 새 요소를 푸시할 때마다 이 작업을 계속 수행하면 대기열에서 예상한 대로 요소가 올바른 순서로 배치됩니다.

대기열에서 요소의 순서를 수정했기 때문에 팝 작업은 대기열에서 빼서 요소를 반환하는 것처럼 간단해야 합니다.

암호

다음은 단일 대기열을 사용하여 스택을 처리하는 클래스의 Python 구현입니다.

from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()


    def push(self, x: int) -> None:
        size = len(self.q1)
        self.q1.append(x)
        for i in range(size):
            el = self.q1.popleft()
            self.q1.append(el)

    def pop(self) -> int:
        return self.q1.popleft()


    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0

참고: 여기에서는 Python의 deque 컬렉션을 사용하고 있지만 일반 대기열로만 사용하고 있습니다. 우리는 deque의 양방향 속성을 사용하지 않았습니다.