C++의 스택과 큐

C++의 스택 및 큐 소개

스택과 큐는 C++에서 일반적으로 사용되는 데이터 구조이며 프로그램에서도 널리 사용됩니다. 이 문서에서는 스택과 큐의 개념, 사용 및 애플리케이션 시나리오를 자세히 소개합니다.

1. 스택의 개념

스택은 "선입, 최후"의 특성을 갖는 선형 데이터 구조입니다. 스택에서는 스택에 푸시된 데이터가 스택의 맨 아래에 더 가깝습니다. 나중에 스택에 푸시된 데이터는 스택의 맨 위에 더 가깝습니다.

스택의 주요 작업은 푸시와 팝입니다. 푸시는 스택에 데이터를 추가하는 것이고, 팝핑은 스택에서 데이터를 삭제하는 것입니다. 스택에는 또한 두 가지 중요한 특수 작업이 있습니다. 즉, 스택의 최상위 요소 보기(top)와 스택이 비어 있는지 확인하는 것(empty)입니다.

스택의 적용 시나리오는 매우 광범위합니다. 예를 들어 스택 사용은 함수 호출과 관련됩니다. 함수가 호출되면 해당 매개변수, 지역 변수 및 기타 정보가 스택에 푸시됩니다. 함수 실행이 끝나면 이 정보는 스택에서 팝되고 함수 호출 전 상태로 복원됩니다.

2. 큐의 개념

큐(Queue) 역시 "선입 선출"의 특성을 지닌 선형 데이터 구조입니다. 대기열에서 더 일찍 대기열에 추가된 데이터는 대기열의 헤드에 더 가깝고 나중에 대기열에 추가된 데이터는 대기열의 끝에 더 가깝습니다.

큐의 주요 작업은 대기열에 넣기와 대기열에서 빼기입니다. 대기열에 들어간다는 것은 대기열 끝에 데이터를 추가하는 것을 의미하고, 대기열에서 빼낸다는 것은 대기열의 선두에서 데이터를 삭제하는 것을 의미합니다. 대기열에는 또한 두 가지 중요한 특수 작업이 있습니다. 즉, 헤드 요소 보기(앞)와 대기열이 비어 있는지 확인하는 것(비어 있음)입니다.

대기열은 또한 널리 사용됩니다. 예를 들어 운영 체제의 프로세스 예약에서 대기열은 실행 대기 중인 프로세스를 저장하는 데 사용될 수 있습니다. 시스템 리소스가 여유로워지면 대기열의 헤드에서 프로세스가 꺼내져 모든 작업이 완료될 때까지 실행됩니다.

3. 스택 및 큐의 적용 예

1. 대괄호 일치

프로그래밍에서는 문자열의 대괄호가 일치하는지 확인해야 하는 경우가 많습니다. 예를 들어, Python 프로그램을 작성할 때 코드 블록이 올바르게 들여쓰기되었는지 확인해야 하는 경우 스택을 사용하여 이를 달성할 수 있습니다.

구체적인 구현 방법은 문자열의 각 문자를 순회하여 왼쪽 대괄호를 만나면 스택에 푸시하는 것입니다. 오른쪽 괄호가 나타나면 일치를 위해 스택의 최상위 요소가 팝됩니다. 일치하면 계속해서 탐색하고, 그렇지 않으면 오류 메시지가 반환됩니다.

2. 프로세스 스케줄링

운영 체제에서는 프로세스의 통일된 스케줄링과 조정이 필요합니다. 이때, 실행을 기다리는 프로세스를 큐(Queue)에 저장하면 운영체제가 우선순위와 실행 순서를 결정한다.

구체적인 구현 방법은 프로세스 번호, 우선순위 및 기타 정보를 포함하여 각 프로세스를 데이터 구조로 추상화하는 것입니다. 이러한 프로세스를 대기열에 넣은 다음 대기열에 있는 프로세스를 순서대로 실행합니다. 프로세스가 작업을 완료하면 대기열이 빌 때까지 대기열에서 제거됩니다.

4. C++에서 스택 및 큐 구현

C++에서는 표준 라이브러리에서 제공하는 컨테이너 클래스를 사용하여 스택 및 큐를 구현할 수 있습니다.

1. 스택 구현

스택은 컨테이너 클래스 std::stack을 사용하여 구현할 수 있습니다.

std::stack은 요소 유형과 기본 컨테이너 유형을 지정해야 하는 템플릿 클래스입니다. 기본 컨테이너 유형이 지정되지 않은 경우 기본적으로 std::deque가 기본 컨테이너로 사용됩니다.

다음은 간단한 스택 구현의 예입니다.

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    std::cout << s.top() << std::endl; // 输出3

    s.pop();

    std::cout << s.top() << std::endl; // 输出2

    while (!s.empty()) {
        s.pop();
    }

    return 0;
}

2. Queue 구현

Queue는 컨테이너 클래스 std::queue를 사용하여 구현할 수 있습니다.

std::queue도 템플릿 클래스이므로 요소 유형과 기본 컨테이너 유형을 지정해야 합니다. 기본 컨테이너 유형이 지정되지 않은 경우 기본적으로 std::deque가 기본 컨테이너로 사용됩니다.

다음은 간단한 대기열 구현 예입니다.

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    std::cout << q.front() << std::endl; // 输出1

    q.pop();

    std::cout << q.front() << std::endl; // 输出2

    while (!q.empty()) {
        q.pop();
    }

    return 0;
}

요약

위의 소개에서 볼 수 있듯이 스택과 대기열은 많은 실제 문제를 해결하는 데 도움이 될 수 있는 매우 실용적인 데이터 구조입니다. 프로그래밍에서 이 두 가지 데이터 구조의 사용 및 구현 원칙을 익히면 프로그램의 효율성과 신뢰성을 향상시킬 수 있습니다.

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