큐는 작업 순서가 FIFO(선입 선출)인 선형 데이터 구조입니다.
배열은 연속 메모리 위치에 저장된 동일한 데이터 유형의 요소를 포함하는 데이터 구조입니다.
대기열에서 삽입 및 삭제 작업은 대기열의 반대쪽 끝에서 수행됩니다. 구현은 스택에 비해 약간 더 복잡합니다.
queue의 배열 구현에서 top과 end 두 개의 변수를 사용하여 크기가 n인 배열 큐를 만듭니다.
이제 처음에는 배열이 비어 있습니다. 즉, 위쪽과 끝이 모두 배열의 0 인덱스에 있습니다. 그리고 요소가 대기열에 추가됨에 따라 (삽입) 최종 변수의 값이 증가합니다. 끝의 값은 최대 n, 즉 배열의 최대 길이까지 증가할 수 있습니다.
대기열에서 요소를 삭제해야 하는 경우 (삭제) , 상위 변수의 값이 증가합니다. top의 값은 end의 값까지 올라갈 수 있습니다.
큐 작업 구현
대기열 - 큐에 요소를 추가하는 작업입니다. 큐에 요소를 추가하기 전에 큐가 가득 찼는지 여부를 확인합니다. 확인 조건이 종료됩니다. n보다 작으면 queue[end]에 요소를 저장할 수 있습니다. 끝을 1 증가시킵니다.
오버플로 조건은 배열이 가득 찼을 때입니다. 즉 end ==n입니다.
큐에서 빼기 - 큐의 요소를 삭제하는 작업입니다. 대기열의 요소를 삭제하기 전에 대기열이 비어 있는지 여부를 확인합니다. Queue가 비어있는지 확인하는 조건으로 top과 end의 값을 확인한다. top ==end이면 배열이 비어 있습니다.
요소가 있으면 배열을 큐에서 빼냅니다. 배열의 왼쪽에 있는 모든 요소를 하나씩 이동합니다.
앞면 - 큐의 첫 번째 요소 추출, 즉 array[top]. 이 작업은 배열이 비어 있지 않은 경우에만 수행할 수 있습니다.
디스플레이 − 이 작업은 대기열의 모든 요소를 표시합니다. 즉, 대기열을 순회합니다.
알고리즘
ENQUEUE : Step 1 : if (end == n), print : “OVERFLOW”. Exit Step 2 : queue[end] = data and end++ DEQUEUE : Step 1 : If (top == 0), print : “empty Queue”. Exit Step 2 : shift all elements one position left. End-- ;
예시
#include <bits/stdc++.h> using namespace std; struct Queue { int top, end, n; int* queue; Queue(int c){ top = end = 0; n = c; queue = new int; } ~Queue() { delete[] queue; } void Enqueue(int data){ if (n == end) { printf("\nQueue is full\n"); return; } else { queue[end] = data; end++; } return; } void Dequeue(){ if (top == end) { printf("\nQueue is empty\n"); return; } else { for (int i = 0; i < end - 1; i++) { queue[i] = queue[i + 1]; } end--; } return; } void Display(){ int i; if (top == end) { printf("\nQueue is Empty\n"); return; } for (i = top; i < end; i++) { printf(" %d <-- ", queue[i]); } return; } void Front(){ if (top == end) { printf("\nQueue is Empty\n"); return; } printf("\nFront Element is: %d", queue[top]); return; } }; int main(void){ Queue q(4); q.Display(); q.Enqueue(12); q.Enqueue(89); q.Enqueue(65); q.Enqueue(34); q.Display(); q.Enqueue(92); q.Display(); q.Dequeue(); q.Dequeue(); q.Display(); q.Front(); return 0; }
출력
Queue is Empty 12 <-- 89 <-- 65 <-- 34 <-- Queue is full 12 <-- 89 <-- 65 <-- 34 <-- 65 <-- 34 <-- Front Element is: 65