스택을 사용하여 큐 구현

큐와 스택은 우리가 일상적인 코딩에 사용하는 상당히 간단한 데이터 구조입니다. 사실 데이터를 유지하는 가장 쉬운 구조라고 생각할 수 있습니다.

기사 전체에서 데이터 구조를 언급하기 위해 DS를 사용하겠습니다.

큐는 FIFO 원칙에 따라 작동하는 DS입니다. 먼저 들어오는 데이터가 먼저 나가는 것이 허용됩니다. 대기열을 구현하는 방법에는 여러 가지가 있습니다. 배열, 연결 목록 및 기타 여러 가지를 자유롭게 사용할 수 있습니다. 하지만 여기서는 Stack이라는 또 다른 DS를 사용하여 Queue를 구현하는 방법에 대해 설명하겠습니다.

이제 우리 모두는 Stack이 LIFO 원리로 작동하는 DS라는 것을 알고 있습니다. 저는 항상 책을 쌓아두는 것에 대해 생각하므로 시각화하는 데 도움이 된다면 자유롭게 그 비유를 사용해 보세요.

저는 hackerrank에서 2개의 스택을 사용하여 대기열을 구현하도록 요구하는 질문을 발견했습니다. 간단하게 들리죠? 잠시 시간을 내어 이를 어떻게 달성할 수 있을지 생각해 보세요.

이를 수행할 수 있는 방법이 많기 때문에 몇 가지 해결책을 생각해 냈을 수도 있습니다. 그렇다면 직접 시도해 보는 것은 어떨까요?

질문

이제 시도했지만 "시간 초과 오류"가 발생한 사람들과 노력하지 않은 사람들을 위해 이 문제에 대한 가장 간단하고 쉬운 해결책을 설명하겠습니다.

먼저 스택이 어떻게 구현될 수 있는지 살펴보세요.

보시다시피 저는 리스트를 이용하여 스택을 구현해봤습니다. 처음에 생성자는 빈 목록을 초기화합니다. 데이터를 목록 끝에 추가하여 푸시합니다. 팝되는 동안 인덱스를 제공하지 않으면 목록 끝에서 팝됩니다. 따라서 마지막에 삽입된 요소가 가장 먼저 튀어나옵니다.

이제 대기열과 비슷한 방식으로 두 개의 서로 다른 스택을 초기화했습니다. 하나는 enqueue용이고 다른 하나는 dequeue용입니다.

우리는 목록 끝에 데이터를 푸시하기 위해 스택과 유사한 enqueueStack을 사용합니다. 그러나 dequeueStack의 경우 스택의 pop 함수가 마지막 요소를 제거한다는 것을 알고 있으므로 우리가 하는 일은 다음과 같습니다. enqueueStack을 뒤집어 dequeueStack에 넣습니다. 따라서 enqueueStack의 첫 번째 요소는 dequeueStack의 마지막 요소가 되고, enqueueStack의 두 번째 요소는 dequeueStack의 두 번째 마지막 요소가 되는 식입니다. 따라서 이제 dequeueStack에 pop 함수를 사용하면 푸시한 첫 번째 요소가 제거되어 대기열을 모방하게 됩니다.

지금 당장 혼란스럽게 들리더라도 걱정하지 마세요! 코드를 보시면 제가 무슨 말을 하는지 아실 겁니다. 실제로 지금 바로 살펴보세요!

추가 확인 사항이 무엇인지 궁금하실 것입니다. dequeueStack이 비어 있는지 확인하는 것과 같습니다. 처음에 확인하지 않으면. 반전을 통해 enqueueStack의 요소는 dequeueStack에 배치되고 첫 번째에 있어야 했던 dequeue Stacks 요소가 이제 마지막이 됩니다. 따라서 먼저 코드에 표시된 것처럼 dequeueStack을 비워야 합니다.

이와 유사하게 printFront는 대기열의 맨 앞에 있어야 하는 항목을 인쇄합니다.

이 구현 후에는 STDIN에서 입력을 읽고 STDOUT으로 출력을 인쇄합니다.

우리의 입력은 다음과 같습니다.

전체 주요 기능은 다음과 같습니다.

최대한 쉽게 구현해보았습니다. 이를 구현하는 다른 더 나은 방법이 여러 개 있을 수 있습니다. 그 중 하나를 소개합니다!

위 내용은 스택을 사용하여 큐 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!