두 개의 스택으로 큐를 구현하는 방법은 무엇입니까?

이 칼럼에서는 두 개의 스택을 사용하여 대기열을 구현하는 방법을 소개합니다.

큐와 스택은 컴퓨터에서 매우 중요한 두 가지 데이터 구조입니다("큐", "스택"). 큐는 선입선출(FIFO)이며 각각의 특성을 알고 있습니다. 스택은 FILO(선입선출) 방식이므로 스택을 사용하여 대기열을 구현하는 방법은 무엇입니까? 이것은 전형적인 면접 질문이므로 이 글에서 이를 구현해 보겠습니다. 공식적으로 시작하기 전에 스택과 큐의 일반적인 방법을 검토해 보겠습니다. 일반적으로 사용되는 스택 메서드는 다음과 같습니다. push(): 푸시 메서드, 스택 상단에 요소 추가

pop(): 팝 메서드, 스택 상단에서 요소 제거 및 요소 반환 ;

peek(): 스택의 최상위 요소를 쿼리하고 요소를 제거하지 않습니다.

일반적으로 사용되는 Queue 메소드는 다음과 같습니다:

• offer(): 큐에 넣기 메소드, 큐 끝에 요소 추가
• poll(): 큐에서 빼기 메소드, 헤드에서 요소 제거 대기열의 요소를 반환합니다.
• peek(): 대기열의 헤드 요소를 쿼리하고 요소를 제거하지 않습니다.

이 전제 지식을 바탕으로 오늘의 주제를 살펴 보겠습니다.

문제 설명

• 두 개의 스택을 사용하여 대기열을 구현합니다. 대기열은 다음과 같이 선언됩니다. 대기열의 끝에 정수를 삽입하고 대기열에 요소가 없는 경우 대기열의 머리에서 정수를 삭제하는 기능을 각각 완료하려면 두 가지 함수(appendTail 및 deleteHead)를 구현하십시오. 대기열의 경우 deleteHead 작업은 -1을 반환합니다.
• 예 1:
• 입력:

["CQueue","appendTail","deleteHead","deleteHead"]

[[],[3],[],[]]

출력: [ null,null,3,-1]

예 2:

입력:

["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]

[[],[],[5],[2],[],[]]

출력: [null,-1,null,null,5,2]

팁:

1

appendTail 및 deleteHead에 대한 호출 최대 10000회

leetcode: leetcode-cn.com/problems/yo…

문제 해결 아이디어

이 질문의 의미는 실제로 이해하기 매우 쉽습니다. 사실, 이는 질문에도 나와 있습니다. "큐를 구현하려면 두 개의 스택을 사용하세요."라는 몇 가지 팁이 있습니다. 이 질문의 핵심 아이디어는 "음수가 양수를 만든다"입니다. 먼저 스택을 사용하여 요소를 저장한 다음(이때 가장 먼저 입력되는 요소는 스택의 맨 아래에 있습니다) 이동합니다. 첫 번째 스택의 요소를 새로운 스택에 넣으면 이때 처음으로 들어간 요소가 스택의 맨 위에 있게 되고, 이후 두 번째 스택을 사용하여 이를 pop out하게 되면 전체 실행 순서가 선착순이 됩니다. -밖으로.

다음으로 전체 프로세스를 그래픽으로 구현해 보겠습니다.

1단계

먼저 아래 그림과 같이 요소를 첫 번째 스택에 밀어 넣습니다.

2단계

아래 그림과 같이 첫 번째 스택의 모든 요소를 ​​두 번째 스택으로 이동합니다.

3단계

아래 그림과 같이 두 번째 스택에서 모든 요소가 팝됩니다.

요약

위 그림에서 볼 수 있듯이 요소 추가 순서는 1, 2, 3, 그리고 마지막으로 두 개의 스택 이후에 터지는 순서도 1, 2, 3이므로 두 개의 스택을 통해 큐(선입선출)를 구현합니다.

구현 코드

다음으로 위 아이디어를 구현하는 코드를 사용해 보겠습니다.

class CQueue {
    Stack<integer> inputStack; // 入栈的容器（添加时操作)
    Stack<integer> outputStack; // 出栈和查询的栈容器

    public CQueue() {
        inputStack = new Stack();
        outputStack = new Stack();
    }    // 添加操作
    public void appendTail(int value) {
        inputStack.push(value);
    }    // 删除操作
    public int deleteHead() {        if (!outputStack.isEmpty()) {            // 出栈容器不为空
            return outputStack.pop();
        } else if (!inputStack.isEmpty()) {            // 入栈 stack 全部转移到出栈 stack
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }        return outputStack.isEmpty() ? -1 : outputStack.pop();
    }
}复制代码</integer></integer>

위의 테스트 코드를 LeetCode에 제출했고, 실행 결과는 다음과 같습니다.

Notes

에 2개가 있습니다. 전체 구현 프로세스 작은 세부 사항에는 특별한 주의가 필요합니다.

1. 첫 번째 스택은 푸시(일시적으로 데이터 저장)만 담당하고 두 번째 스택은 팝(최종 대기열 실행 시퀀스)만 담당합니다.
2. 스택 2가 실행될 때마다 팝된 경우 모든 요소가 팝아웃된 후에만 스택 1에서 새 데이터를 추가(추가)할 수 있습니다. 스택 2의 모든 데이터가 팝아웃되지 않은 경우 스택 1의 요소는 스택 2로 푸시될 수 없습니다. 실행 순서가 혼란스럽습니다.

요약

이 기사에서는 두 개의 선입선출 스택을 사용하고 "음수가 양수를 만든다"는 아이디어를 통해 대기열의 선입선출 기능을 구현합니다. , 두 번째 스택이 팝될 때 특별한 주의가 필요합니다. 컨테이너가 비어 있지 않은 경우(스택), 프로그램 실행 순서를 혼동하지 않도록 첫 번째 스택의 요소를 두 번째 스택에 추가할 수 없습니다.

관련 무료 학습 권장사항: Java 기본 튜토리얼

위 내용은 두 개의 스택으로 큐를 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!