c circular queue data structure
C ++ 순환 대기열 데이터 구조에 대한이 자습서에서는 순환 대기열이란 무엇이며 구현 및 응용 프로그램과 함께 기본 작업은 무엇인지 설명합니다.
순환 대기열은 앞에서 논의한 기본 대기열의 확장입니다. '링 버퍼'라고도합니다.
C ++의 순환 대기열이란 무엇입니까?
순환 대기열은 데이터 항목을 저장하는 데 사용되는 선형 데이터 구조입니다. FIFO (First In, First Out) 접근 방식을 따라 작업을 수행하고 대기열의 마지막 위치가 원을 형성하기 위해 첫 번째 위치로 다시 연결됩니다.
학습 내용 :
C ++의 순환 대기열
다음 다이어그램은 순환 대기열을 보여줍니다.
위 이미지는 크기 10의 원형 데이터 구조를 보여줍니다. 처음 6 개 요소는 이미 대기열에 있으며 첫 번째 위치와 마지막 위치가 결합 된 것을 볼 수 있습니다. 이러한 배열로 인해 공간이 선형 대기열에서 발생하는 것처럼 낭비되지 않습니다.
유튜브 비디오를 다운로드하는 안전한 프로그램
큐가 가득 찬 후 선형 큐에서 다른 쪽 끝에서 요소를 삭제하고 큐의 상태는 여전히 가득 찬 것으로 표시되며 더 많은 요소를 삽입 할 수 없습니다.
순환 대기열에서 대기열이 가득 차면 마지막 위치와 첫 번째 위치가 연결되어 앞쪽에서 요소를 제거 할 때 요소를 삭제하여 비워진 뒤쪽에 요소를 삽입 할 수 있습니다.
다음 섹션에서는 순환 대기열의 기본 작업에 대해 알아 봅니다.
기본 작동
순환 대기열의 몇 가지 기본 작업은 다음과 같습니다.
앞: 순환 대기열의 앞 위치를 반환합니다.
후방: 순환 대기열의 뒤쪽 위치를 반환합니다.
대기열에 넣기 : 대기열에 넣기 (값)는 순환 대기열에 요소를 삽입하는 데 사용됩니다. 요소는 항상 대기열의 뒤쪽 끝에 삽입됩니다.
순환 대기열에 새 요소를 삽입하려면 다음 단계의 순서를 따릅니다.
#1) 순환 대기열이 가득 찼는 지 확인합니다. test ((후면 == SIZE-1 && 전면 == 0) || (후면 == 전면 -1)), 여기서‘SIZE '는 순환 대기열의 크기입니다.
#두) 순환 대기열이 가득 차면 'Queue is full'이라는 메시지가 표시됩니다. 대기열이 꽉 찼다면 (후면 == SIZE – 1 && 전면! = 0) 확인하십시오. 참이면 rear = 0을 설정하고 요소를 삽입합니다.
대기열에서 빼기 : 대기열 제거 기능은 대기열에서 요소를 삭제하는 데 사용됩니다. 순환 대기열에서 요소는 항상 프런트 엔드에서 삭제됩니다. 다음은 순환 대기열에서 대기열에서 빼기 작업의 순서입니다.
단계 :
#1) 순환 대기열이 비어 있는지 확인 : (front ==-1)인지 확인합니다.
mkv 파일을 보는 방법
#두) 비어 있으면 'Queue is empty'메시지를 표시합니다. 대기열이 비어 있지 않으면 3 단계를 수행하십시오.
#삼) (전면 == 후면) 확인하십시오. true이면 front = rear = -1로 설정하고, 그렇지 않으면 (front == size-1)인지 확인하고, true이면 front = 0으로 설정하고 요소를 반환합니다.
삽화
이 섹션에서는 순환 대기열에서 요소를 추가 / 제거하는 자세한 그림을 살펴 보겠습니다.
아래와 같이 5 개 요소의 다음 순환 대기열을 고려하십시오.
다음으로 항목 1을 대기열에 삽입합니다.
다음으로 값이 3 인 항목을 삽입합니다.
큐를 가득 채우는 요소를 삽입하면 다음과 같은 표현이됩니다.
이제 아래에 표시된 것처럼 두 요소 즉, 항목 1과 항목 3을 대기열에서 삭제합니다.
다음으로, 아래와 같이 순환 대기열에 요소 11을 삽입하거나 대기열에 넣습니다.
다시 순환 대기열에 요소 13을 삽입하겠습니다. 대기열은 아래와 같이 표시됩니다.
순환 대기열에서 원 안에 요소를 이동하거나 삽입하는 것을 볼 수 있습니다. 따라서 큐가 가득 차게 될 때까지 큐의 전체 공간을 사용할 수 있습니다.
이행
C ++를 사용하여 순환 대기열을 구현해 보겠습니다.
#include using namespace std; class Queue { public: // Initialize front and rear int rear, front; // Circular Queue int size; int *circular_queue; Queue(int sz) { front = rear = -1; size = sz; circular_queue = new int(sz); } void enQueue(int elem); int deQueue(); void displayQueue(); }; /* Function to create Circular queue */ void Queue::enQueue(int elem) { if ((front == 0 && rear == size-1) || (rear == (front-1)%(size-1))) { cout<<'
Queue is Full'; return; } else if (front == -1) { /* Insert First Element */ front = rear = 0; circular_queue(rear) = elem; } else if (rear == size-1 && front != 0) { rear = 0; circular_queue(rear) = elem; } else { rear++; circular_queue(rear) = elem; } } // Function to delete element from Circular Queue int Queue::deQueue() { if (front == -1) { cout<<'
Queue is Empty'; return -1; } int data = circular_queue(front); circular_queue(front) = -1; if (front == rear) { front = -1; rear = -1; } else if (front == size-1) front = 0; else front++; return data; } //display elements of Circular Queue void Queue::displayQueue() { if (front == -1) { cout<<'
Queue is Empty'<= front) { for (int i = front; i <= rear; i++) cout< 위에 표시된 것은 순환 대기열 작업의 출력입니다. 먼저 요소를 추가 한 다음 두 요소를 대기열에서 빼거나 제거합니다. 다음으로 순환 대기열에 3 개의 요소를 더 삽입하거나 대기열에 넣습니다. 선형 대기열과 달리 요소는 대기열 끝에 추가됩니다.
연결된 목록 구현
이제 순환 대기열의 연결 목록 구현에 대해 논의하겠습니다. 다음은 C ++에서 순환 대기열의 연결 목록 구현입니다. 각 노드를 나타 내기 위해 struct를 사용합니다. 작업은이 경우 링크드리스트 노드에 대해 수행해야한다는 점을 제외하면 앞에서 설명한 것과 동일합니다.
출력에는 대기열에 넣기 작업, 대기열에서 빼기 및 두 번째 대기열에 넣기 작업 후 순환 대기열이 표시됩니다.
#include using namespace std; struct Node { int data; struct Node* link; }; struct PQueue { struct Node *front, *rear; }; /* this functions performs enqueue operation for circular queue */ void enQueue(PQueue *pq,int elem) { struct Node *temp = new Node; temp->data = elem; if (pq->front == NULL) pq->front = temp; else pq->rear->link = temp; pq->rear = temp; pq->rear->link = pq->front; } // This function performs dequeue operation for Circular Queue int deQueue(PQueue *pq) { if (pq->front == NULL) { cout<<'Queue is empty!!'; return -1; } int elem; // item to be dequeued // item is the last node to be deleted if (pq->front == pq->rear) { elem = pq->front->data; free(pq->front); pq->front = NULL; pq->rear = NULL; } else //more than one nodes { struct Node *temp = pq->front; elem = temp->data; pq->front = pq->front->link; pq->rear->link= pq->front; free(temp); } return elem ; } //display elements of Circular Queue void displayQueue(struct PQueue *pq) { struct Node *temp = pq->front; while (temp->link != pq->front) { cout<data<<' '; temp = temp->link; } cout<data; } //main program int main() { // Create a circular queue and initialize front and rear PQueue *pq = new PQueue; pq->front = pq->rear = NULL; // Insert/enqueue elements in Circular Queue enQueue(pq, 1); enQueue(pq, 3); enQueue(pq, 5); cout<<'
Circular Queue elements after enqueue operation: '; // Display elements in Circular Queue displayQueue(pq); // Delete/dequeue elements from Circular Queue cout<<'
Dequeued Item: '< 산출:
다음 구현은 연결 목록을 사용하여 순환 대기열을 보여주는 Java 프로그램입니다.
import java.util.* ; class Main { // Node structure static class Node { int data; Node link; } static class CQueue { Node front, rear; } // Enqueue operation for circular queue static void enQueue(CQueue cq, int value) { Node temp = new Node(); temp .data = value; if (cq .front == null) cq .front = temp; else cq .rear .link = temp; cq .rear = temp; cq .rear .link = cq .front; } // Dequeue operation for Circular Queue static int deQueue(CQueue cq) { if (cq .front == null) { System.out.printf ('Queue is empty!!'); return Integer.MIN_VALUE; } int value; // Value to be dequeued // the last node to be deleted if (cq.front == cq.rear) { value = cq.front.data; cq.front = null; cq.rear = null; } else { // There are more than one nodes Node temp = cq.front; value = temp.data; cq.front = cq.front.link; cq.rear.link= cq.front; } return value ; } // display the elements of Circular Queue static void displayQueue( CQueue cq) { Node temp = cq.front; while (temp.link != cq.front) { System.out.printf('%d ', temp.data); temp = temp.link; } System.out.printf('%d', temp.data); } /* main program */ public static void main(String args()) { // Create a queue and initialize front and rear CQueue cq = new CQueue(); cq.front = cq.rear = null; // Insert/enqueue elements in Circular Queue enQueue(cq, 2); enQueue(cq, 4); enQueue(cq, 6); System.out.print('
Circular Queue elements after Enqueue Operation:'); // Display elements in Circular Queue displayQueue(cq); // Delete/dequeue elements from Circular Queue System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.printf('
Dequeued Item = %d', deQueue(cq)); System.out.print('
Circular Queue elements after Dequeue Operation:'); displayQueue(cq); enQueue(cq, 8); enQueue(cq, 10); System.out.print('
Circular Queue elements after second Enqueue Operation:'); displayQueue(cq); } } 산출:
위 프로그램의 출력은 이전 프로그램과 유사합니다.
응용
순환 대기열의 몇 가지 응용 프로그램에 대해 살펴 보겠습니다.
- CPU 스케줄링 : 일부 이벤트가 발생하거나 실행을 위해 다른 프로세스가 완료되어야하는 운영 체제 프로세스는 모든 조건이 충족되거나 모든 이벤트가 발생할 때 차례로 실행되도록 순환 대기열에 유지되는 경우가 많습니다.
- 메모리 관리: 위의 논의에서 이미 언급했듯이 일반 대기열을 사용하면 메모리 공간이 낭비됩니다. 메모리 관리를 위해 순환 대기열을 사용하면 최적의 메모리 사용에 도움이됩니다.
- 컴퓨터 제어 교통 신호 시스템 : 컴퓨터 화 된 교통 신호는 종종 순환 대기열에 추가되어 지정된 시간 간격이 경과 한 후에 자체적으로 반복됩니다.
결론
순환 큐는 요소를 삭제하고 공간이 비워도 후면 포인터가 큐 끝에있을 때 요소를 삽입 할 수없는 일반 큐의 주요 단점을 수정합니다. 원형 대기열에서 요소는 원형으로 배열되어 공간이 전혀 낭비되지 않습니다.
순환 대기열의 주요 작업도 확인했습니다. 순환 대기열은 신호가 차례로 빛나는 교통 신호 시스템과 같은 스케줄링 목적 및 애플리케이션에 주로 유용합니다.
시니어 개발자를위한 j2ee 인터뷰 질문
다음 자습서에서는 단순히 'deque'라고하는 이중 종단 대기열에 대해 알아 봅니다.
추천 도서
