큐는 작업 순서가 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