C의 순환 대기열: 구현 방법
게시 됨: 2020-10-23데이터는 마지막 요소가 첫 번째 요소에 연결되는 원형 패턴의 원형 대기열에 배열됩니다. FIFO(선입선출) 방식으로 작업이 실행되는 선형 대기열과 달리 순환 대기열 작업 실행 순서는 변경될 수 있습니다. 삽입 및 삭제 작업은 모든 위치에서 수행할 수 있습니다.
순환 대기열은 선형 대기열보다 효율적입니다. 원형 대기열의 그래픽 표현에서 전면 및 후면 위치가 연결되어 작업이 항상 FIFO 기반으로 실행되는 원으로 만드는 것을 관찰할 수 있습니다. 모든 새로운 요소는 리어 엔드에서 추가되고 프론트 엔드에서 삭제됩니다. 순환 대기열은 활용도가 더 높고 시간 복잡도가 O(1)입니다.
원천
목차
순환 대기열의 응용
- CPU 스케줄링: 순환 대기열은 선형 대기열에 있는 빈 메모리 공간을 사용합니다.
- 교통 시스템: 교통 시스템에서 원형 대기열의 도움으로 신호등은 설정된 시간 간격으로 작동됩니다.
- 메모리 관리: 운영 체제는 실행할 준비가 되어 있거나 특정 이벤트가 발생하기를 기다리는 프로세스 라인을 유지하는 경우가 많습니다.
배우기: 버블 정렬을 위한 C 프로그램: C의 버블 정렬
설명이 포함된 샘플 코드
1행: // (1) 전처리기
2행: // 대기열 제한을 5개 요소로 설정
3행: #include<stdio.h>
4행: #define LIM 5
5행: // (2) 큐 데이터 유형 선언
6행: // 데이터는 데이터를 보유합니다. delPos, 삭제할 위치; 길이, 아니. 의
7행: // 현재 큐에 있는 요소
8행: typedef 구조체 큐 {
9행: int data[LIM], delPos, length;
10행: } Q;
11행: // (3) 전역 선언
12행: // 구조체 큐 유형의 함수 및 전역 변수 q
13행: Q q;
14행: ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ()를 무효화합니다.
15행: // (4) 초기화 후 UI 함수 호출
16행: int main()
17행: {
18행: initQ();
19행: ui_Q_Ops();
20행: 0을 반환합니다.
21행: }
22행: // (5) 대기열 초기화
23행: initQ() 무효화
24행: {
25행: q.length = 0;
26행: q.delPos = 0;
27행: }
28행: // (6) 메뉴 기반 루프가 올바른 기능을 호출합니다.
29행: ui_Q_Ops() 무효화
30행: {
31행: int 선택=0;
32행: 문자 입력[16];
33행: while(choice!=4){
34행: printf(" \n ———————\n ");
35행: printf(" 1. 대기열에 삽입 \n ");
36행: printf(" 2. 대기열에서 삭제 \n ");
37행: printf(" 3. 대기열 항목 표시 \n ");
38행: printf(" 4. 프로그램 종료 \n ");
39행: printf(" 선택사항을 입력하십시오 : ");
40행: if (fgets(input, 15, stdin) != NULL){
41행: if (sscanf(입력, "%d", &choice) == 1){
42행: 스위치(선택){
43행: 사례 1: insertQel();
44행: 중단;
45행: 사례 2: deleteQel();
46행: 중단;
47행: 사례 3: displayQels();
48행: 중단;
49행: 사례 4: 반환;
50행: 기본값: printf("잘못된 선택\n ");
51행: 계속
52행: }
53행: } else
54행: printf(" 잘못된 선택 \n ");
55행: }
56행: }
57행: }
58행: // (7) 대기열에 삽입
59행: // 길이가 MAX Limit와 같으면 대기열이 가득 차고 그렇지 않으면 삽입
60행: // MAX Limit에 의해 합 길이와 delPos 모듈러스로 원형 달성
61행: // 및 증분 길이
62행: insertQel() 무효화
63행: {
64행: int el, inspos;
65행: 문자 입력[16];
66행: if (q.length == LIM){
67행: printf(" 대기열이 가득 찼습니다. \n ");
68행: 반환;
69행: }
70행: inspos = (q.delPos + q.length) % LIM;
71행: printf(" 삽입할 요소를 입력하세요: ");
72행: if (fgets(input, 15, stdin) != NULL){
73행: if (sscanf(입력, "%d", &el)){
74행: q.data[inspos] = el;
75행: q.length++;
76행: } else
77행: printf("잘못된 입력 \n ");
78행: }
79행: }
80행: // (8) 대기열에서 삭제
81행: // Length가 0이면 큐가 비어 있고, 그렇지 않으면 delPos에서 삭제합니다.
82행: // 길이 감소
83행: deleteQel() 무효화
84행: {
85행: if (q.length == 0){
86행: printf(" 대기열이 비어 있습니다. \n ");
87행: } else {
88행: printf("삭제된 요소 %d \n ", q.data[q.delPos]);
89행: q.delPos = (q.delPos + 1) % LIM;
90행: q.length-;
91행: }
92행: }
93행: // (9) 대기열 요소 표시
94행: // delPos에서 시작하는 루프를 실행하는 순환 방식으로 표시
95행: // 최대 한계에 따라 반복자와 모듈러스 추가
96행: displayQels() 무효화
97행: {
98행: int i;
99행: if (q.length == 0){
100행: printf(" 대기열이 비어 있습니다. \n ");
101행: } else {
102행: printf(" 대기열의 요소는 다음과 같습니다. ");
103행: for(i = 0; i < q.length; i++){
104행: printf("%d ", q.data[(q.delPos+i)%LIM]);
105행: }
106행: printf(" \n ");
107행: }
108행: }
109행:
출력:
순환 대기열의 작업
1. insertQel() – 순환 대기열에 요소 삽입
순환 대기열에서 enQueue() 함수는 요소를 순환 대기열에 삽입하는 데 사용됩니다. 원형 대기열에서 새 기능은 항상 뒤쪽 위치에 삽입됩니다. enQueue() 함수는 하나의 정수 값을 매개변수로 사용하여 순환 큐에 삽입합니다. 순환 큐에 요소를 삽입하기 위해 다음 단계가 구현됩니다.
1단계 – 길이가 MAX Limit와 동일한지 확인합니다. true이면 대기열이 FULL임을 의미합니다. FULL이면 "Queue is full"을 표시하고 기능을 종료합니다.
2단계 – 전체가 아닌 경우 MAX Limit 및 증분 길이에 의해 합계 길이와 delPos 모듈러스로 순환적으로 달성된 값을 삽입합니다.
2. deleteQel() – 순환 대기열에서 요소 삭제
순환 대기열에서 deQueue()는 순환 대기열에서 요소를 삭제하는 데 사용되는 함수입니다. 순환 큐에서 요소는 항상 맨 앞 위치에서 삭제됩니다. deQueue() 함수는 어떤 값도 매개변수로 사용하지 않습니다. 순환 대기열에서 요소를 삭제하기 위해 다음 단계가 구현됩니다.
1단계 – 대기열이 비어 있는지 확인합니다. (앞 == -1 && 뒤 == -1)
2단계 – EMPTY인 경우 "Queue is empty"를 표시하고 기능을 종료합니다.
3단계 – 비어 있지 않은 경우 위치에 따라 삭제된 요소를 표시합니다. 모든 요소가 추가되면 다음 위치 모드 대기열 제한으로 이동합니다.
3. displayQels() – 순환 대기열에 있는 대기열 요소를 표시합니다. 순환 대기열의 요소를 표시하기 위해 다음 단계가 구현됩니다.
1단계 – 대기열이 비어 있는지 확인합니다.
2단계 – 길이가 0이면 EMPTY이며 "Queue is empty"를 표시하고 기능을 종료합니다.
3단계 – 비어 있지 않은 경우 정수 변수 'i'를 정의합니다.
4단계 – i를 0으로 설정합니다.
5단계 – 다시 위치에 따라 요소를 표시하고 값을 1씩 증가시킵니다(i++). 'i <q.length'가 FALSE가 될 때까지 동일하게 반복합니다.
순환 대기열은 연결 목록을 사용하여 구현할 수도 있습니다. 다음은 알고리즘입니다.
- 대기열에 넣기 위한 알고리즘:
if (FRONT == NULL) // 빈 큐에 삽입
전면 = 후면 = newNode
종료
또 다른
REAR -> next = newNode // 마지막 요소 뒤에 삽입
후면 = newNode
다른 끝
후면 -> 다음 = 전면
대기열 종료
- 대기열에서 빼기 위한 알고리즘:
if(FRONT == NULL) // 언더플로 조건
"대기열 언더플로" 인쇄
큐에서 종료
종료
else if(FRONT == REAR) // 큐에는 하나의 노드만 포함됩니다.
온도 = FRONT -> 데이터
무료(임시)
FRONT = FRONT -> 다음
후면 -> 다음 = 전면
종료
else if (FRONT == N – 1) // FRONT가 마지막 노드인 경우
front = 0 // FRONT를 첫 번째 노드로 만듭니다.
종료
큐에서 종료
또한 읽기: Python 대 C: 완전한 병렬 비교
결론
데이터 구조와 알고리즘은 C 프로그래밍뿐만 아니라 다른 언어에서도 매우 중요합니다. 그 가치는 전례가 없으며 그러한 중요한 주제의 경우 전문가가 설계하고 멘토링하는 과정에 투자하는 것이 좋습니다. 그러면 포트폴리오에 탁월한 가치를 더할 수 있습니다. upGrad는 귀하의 기술을 향상시킬 뿐만 아니라 기초의 강력한 기둥을 구축하는 강력하고 풍부한 과정을 다양하게 제공합니다.
평판이 좋은 IIIT-B가 설계한 이 곳에서 그들은 프리미엄 품질의 콘텐츠를 제공할 뿐만 아니라 동일한 경력 경로에서 진화하는 사람들 및 업계 전문가들과 연결할 수 있는 강력한 네트워크의 일부가 됩니다. 당신의 의심을 해결하고 매번 당신을 지원합니다.
그들의 사고 방식과 사고 과정을 알아가는 것이 도움이 될 것입니다. upGrad에서 얻을 수 있는 독특한 점 중 하나는 EMI 옵션을 선택하고 간편하게 사용할 수 있다는 것입니다.
이러한 C 프로젝트를 실행하는 데 훌륭한 학습 기회가 있기를 바랍니다. 더 자세히 알아보고 업계 전문가의 멘토링이 필요한 경우 upGrad & IIIT Banglore의 전체 스택 소프트웨어 개발 PG 디플로마를 확인하십시오.