C 언어를 사용하여 배열 기반 대기열을 구현하는 방법

프로그래밍에서 큐는 일반적으로 사용되는 데이터 구조입니다. 많은 프로그래밍 언어에는 Java의 Queue 및 Python의 deque와 같은 자체 큐 구현이 있습니다. 그러나 C 언어에는 기성 대기열 구현이 없습니다. 따라서 C 언어에서는 배열을 정의하고 포인터와 기타 트릭을 사용하여 큐를 구현해야 합니다.

이번 글에서는 C언어를 이용하여 배열 기반의 큐를 구현하는 방법을 소개하겠습니다.

1. 큐 구조 정의

큐 구조를 정의하여 큐 작업을 구현할 수 있습니다. 이 큐 구조에는 큐 크기, 헤드 및 테일 포인터, 요소 데이터 등과 같은 정보가 포함됩니다.

#define MAX_SIZE 100

typedef struct queue {
    int size;
    int front;
    int rear;
    int data[MAX_SIZE];
} Queue;

위 코드에서는 큐의 최대 크기를 나타내기 위해 MAX_SIZE 상수를 정의하고, 구조를 정의하여 Queue라는 큐를 선언했습니다.

그 중 size는 큐의 크기를 나타내고, front는 큐 헤드 포인터를 나타내고, Rear는 큐 tail 포인터를 나타내고, data는 요소를 저장하는 배열입니다.

2. 큐 초기화 작업

큐 구현에서는 큐의 올바른 사용을 보장하기 위해 큐 초기화 작업이 먼저 수행되어야 합니다.

void init(Queue *q) {
    q->size = 0;
    q->front = 0;
    q->rear = -1;
}

위 코드에서는 큐 구조를 가리키는 포인터 q를 매개변수로 받아들이고 큐의 크기를 0으로, 헤드 포인터를 0으로, 테일 포인터를 0으로 설정하는 초기화 함수 init를 정의합니다. - 1, 대기열이 비어 있음을 나타냅니다.

3. 요소 대기열에 넣기 작업

큐의 대기열에 넣기 작업은 대기열 끝에 요소를 배치하는 것입니다. 여기서 구현은 요소를 배열 데이터 끝에 추가하고 후면 포인터의 위치를 ​​업데이트하는 것입니다. .

int enqueue(Queue *q, int value) {
    if(q->size == MAX_SIZE) {
        return 0;
    }
    q->rear++;
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

위 코드에서 먼저 대기열이 꽉 찼는지 확인합니다. 꽉 차 있으면 0을 반환하여 삽입이 실패했음을 나타냅니다. 그렇지 않으면 후면 포인터를 한 비트 뒤로 이동하고 요소 값을 데이터 끝에 할당합니다. 배열, 큐 크기가 1만큼 증가하고 마지막으로 삽입 성공을 나타내기 위해 1이 반환됩니다.

4. 요소 대기열 제거 작업

큐의 대기열 제거 작업은 대기열의 선두에 있는 요소를 꺼내고 전면 포인터의 위치를 ​​업데이트하는 것입니다. 여기서 구현된 아이디어는 데이터의 앞부분에 있는 요소 값을 반환하고 앞 포인터를 1비트 뒤로 이동하며 동시에 큐의 크기를 업데이트하는 것입니다.

int dequeue(Queue *q) {
    if(q->size == 0) {
        return -1;
    }
    int value = q->data[q->front];
    q->front++;
    q->size--;
    return value;
}

위 코드에서는 먼저 큐가 비어 있는지 확인합니다. 비어 있으면 -1을 반환하여 큐가 비어 있음을 나타냅니다. 그렇지 않으면 데이터의 맨 앞 위치에 있는 요소 값을 반환하고 맨 앞으로 이동합니다. 포인터를 1비트 뒤로 보냅니다. 큐의 크기를 1만큼 줄이고 요소 값을 반환합니다.

5. 큐 구현 테스트

이제 큐의 다양한 작업을 구현했으므로 테스트해 보겠습니다.

#include <stdio.h>

int main() {
    Queue myQueue;
    init(&myQueue);
    enqueue(&myQueue, 1);
    enqueue(&myQueue, 2);
    enqueue(&myQueue, 3);
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    printf("%d\n", dequeue(&myQueue));
    return 0;
}

위 테스트 코드에서는 먼저 myQueue라는 큐를 정의하고 init 함수가 이를 초기화합니다. . 그런 다음 enqueue 함수를 사용하여 숫자 1, 2, 3을 대기열에 삽입하고 dequeue 함수를 사용하여 대기열에서 요소를 제거하여 화면에 출력합니다.

여기서 출력되는 내용은 다음과 같습니다.

1
2
3

6. Summary

이 문서에서는 C 언어를 사용하여 배열 기반 대기열을 구현하는 방법을 배웠습니다. 대기열 구조 및 관련 작업 기능을 정의함으로써 대기열의 요소를 쉽게 추가, 삭제 및 액세스할 수 있습니다. 큐를 구현하기 위해 포인터를 사용하는 것은 번거롭지만 이 방법은 큐의 원리를 더 잘 이해하는 데 도움이 될 수 있으며 데이터 구조 및 알고리즘을 학습하는 데 큰 도움이 됩니다.

위 내용은 C 언어를 사용하여 배열 기반 대기열을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!