C의 큐 - C 튜토리얼

컴퓨터 과학에서 큐는 '선입 선출'(FIFO) 원칙에 따라 구성 요소가 한쪽 끝에 배치되고 다른 쪽 끝에서 제거되는 선형 데이터 구조입니다. 이 데이터 구조는 동작 순서를 제어하거나 데이터를 저장하는 데 활용될 수 있습니다. C는 배열이나 연결 목록 형태로 통합된 대기열 기능을 갖춘 컴퓨터 언어입니다.

형질:

큐는 배열이나 연결 리스트로 구성할 수 있는 선형 데이터 구조의 한 유형입니다.
요소는 대기열의 앞쪽에서 제거되는 동안 뒤쪽으로 재배치됩니다.
Enqueue(뒤에 요소 추가)와 Dequeue(앞에서 요소 제거)는 두 가지 대기열 작업입니다.
요소가 자주 추가되고 제거되면 메모리 낭비를 방지하기 위해 대기열이 순환 대기열로 구축될 수 있습니다.

배열 사용:

배열을 사용하여 C에서 대기열을 구현하려면 먼저 대기열의 최대 크기를 정의하고 해당 크기의 배열을 선언합니다. 앞과 뒤의 정수는 각각 1로 설정되었습니다. 앞 변수는 큐의 앞 요소를 나타내고, 뒤 변수는 뒤 요소를 나타냅니다.

새 요소를 대기열의 최종 위치로 푸시하기 전에 back 변수를 1만큼 늘려야 합니다. 이제 대기열이 가득 차서 뒤쪽 위치가 대기열의 최대 용량에 도달하면 다른 추가 요소를 추가할 수 없습니다. 큐의 맨 앞에 요소를 추가하고 큐에서 요소를 제거하기 위해 앞의 변수를 1만큼 늘립니다. 전면과 후면 위치가 동일하고 더 이상 구성 요소를 삭제할 수 없으면 대기열이 비어 있다고 말할 수 있습니다.

Java에서 int를 문자열로

다음은 배열을 사용하는 C로 작성된 대기열의 인스턴스입니다.

C 프로그래밍 언어:

 #define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf(&apos;Queue is full&apos;); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front &gt; rear) { printf(&apos;Queue is empty&apos;); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); return 0; }

코드의 출력은 다음과 같습니다:

산출:

업캐스팅

 10 20 30 Queue is empty-1

설명:

먼저, 세 개의 요소 10, 20, 30을 대기열에 추가합니다.
그런 다음 대기열의 첫 번째 요소인 10을 대기열에서 제거하고 인쇄합니다.
다음으로, 큐의 첫 번째 요소인 20을 다시 큐에서 빼내고 인쇄합니다.
그런 다음 큐의 앞부분 요소인 30을 다시 큐에서 빼내고 인쇄합니다.
마지막으로 'Queue isempt'를 출력하고 -1을 반환하는 빈 큐에서 큐를 제거합니다.

연결 목록 사용:

프로그래밍 언어 C에서 대기열을 구성하는 또 다른 대체 접근 방식은 연결된 목록을 사용하는 것입니다. 큐의 각 노드는 이 방법을 사용하여 큐의 다음 노드에 대한 포인터와 요소 값을 포함하는 노드로 표현됩니다. 대기열의 첫 번째 노드와 마지막 노드를 각각 추적하기 위해 전면 포인터와 후면 포인터가 사용됩니다.

요소 값으로 새 노드를 설정하고 다음 포인터를 NULL로 설정하여 대기열에 요소를 추가합니다. 새 노드에 대해 대기열이 비어 있으면 전면 포인터와 후면 포인터를 설정합니다. 그렇지 않은 경우 후면 포인터를 업데이트하고 이전 후면 노드의 다음 포인터가 새 노드를 가리키도록 설정합니다.

대기열에서 노드를 삭제할 때 이전 노드가 먼저 삭제된 다음 전면 포인터가 대기열의 다음 노드로 업데이트되고 마지막으로 제거된 노드가 점유하고 있던 메모리가 해제됩니다. 제거 후 전면 포인터가 NULL이면 큐는 비어 있습니다.

자바는 인스턴스입니다

다음은 연결된 목록을 사용하여 C로 구현된 대기열의 예입니다.

C 프로그래밍 언어:

 #include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node-&gt;data = element; new_node-&gt;next = NULL; if (front == NULL &amp;&amp; rear == NULL) { front = rear = new_node; return; } rear-&gt;next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf(&apos;Queue is empty&apos;); return -1; } struct Node* temp = front; int element = temp-&gt;data; if (front == rear) { front = rear = NULL; } else { front = front-&gt;next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); printf(&apos;%d &apos;, dequeue()); return 0; }

코드의 출력은 다음과 같습니다:

산출:

 10 20 30 Queue is empty-1

설명:

먼저, 세 개의 요소 10, 20, 30을 대기열에 추가합니다.
그런 다음 대기열의 첫 번째 요소인 10을 대기열에서 제거하고 인쇄합니다.
다음으로, 큐의 첫 번째 요소인 20을 다시 큐에서 빼내고 인쇄합니다.
그런 다음 큐의 앞부분 요소인 30을 다시 큐에서 빼내고 인쇄합니다.
마지막으로 빈 대기열에서 대기열을 빼려고 시도합니다. 그러면 'Queue isempt'라는 메시지가 인쇄되고 -1이 반환됩니다.

장점:

대기열은 너비 우선 검색 및 작업 예약과 같이 요소를 정확한 순서로 처리해야 하는 알고리즘을 구현하는 데 특히 유용합니다.
큐 작업은 O(1) 시간 복잡도를 갖기 때문에 거대한 큐에서도 빠르게 실행될 수 있습니다.
대기열은 배열이나 연결 목록을 사용하여 간단하게 구현할 수 있으므로 특히 유연합니다.

단점:

스택과 달리 큐는 단일 포인터로 구성할 수 없으므로 큐 구현이 약간 더 복잡해집니다.
대기열이 배열로 구성된 경우 너무 많은 요소가 추가되면 곧 채워져 성능 문제가 발생하거나 충돌이 발생할 수 있습니다.
연결된 목록을 활용하여 대기열을 구현하는 경우 각 노드의 메모리 오버헤드가 상당할 수 있으며, 특히 작은 요소의 경우 더욱 그렇습니다.

결론:

중요한 데이터 구조인 대기열을 사용하는 애플리케이션에는 운영 체제, 네트워킹, 게임 등이 포함됩니다. 배열이나 연결 목록을 사용하여 생성하기가 간단하므로 특정 순서로 요소를 처리해야 하는 알고리즘에 이상적입니다. 그러나 큐에는 메모리 소비 및 구현 복잡성과 같은 특정 애플리케이션에 대한 데이터 구조를 선택할 때 고려해야 하는 단점이 있습니다.