데이터 구조는 구조화된 방식으로 구성된 데이터의 모음입니다. 아래 설명과 같이 두 가지 유형으로 나뉩니다 -
-
선형 데이터 구조 − 데이터는 선형 방식으로 구성됩니다. 예를 들어 배열, 구조, 스택, 대기열, 연결 목록이 있습니다.
-
비선형 데이터 구조 − 데이터는 계층적 방식으로 구성됩니다. 예를 들어, 나무, 그래프, 세트, 테이블.
대기열
삽입은 후단에서, 삭제는 전단에서 수행되는 선형 데이터 구조입니다.
대기열의 순서는 FIFO – First In First Out
입니다.작업
- 삽입 – 대기열에 요소 삽입
- 삭제 – 대기열에서 요소를 삭제합니다.
조건
-
Queue over flow - 전체 대기열에 요소를 삽입하려고 합니다.
-
Queue under flow − 빈 대기열에서 요소를 삭제하려고 합니다.
알고리즘
다음은 삽입 알고리즘입니다( ) -
- 대기열 오버플로를 확인합니다.
if (r==n)
printf ("Queue overflow") - 그렇지 않으면 대기열에 요소를 삽입하세요.
q[r] = item r++
다음은 삭제( ) 알고리즘입니다. -
- 흐름 중인 대기열을 확인합니다.
if (f==r)
printf ("Queue under flow") - 그렇지 않으면 대기열에서 요소를 삭제합니다.
item = q[f] f++
다음은 디스플레이( )에 대한 알고리즘입니다. -
- 대기열이 비어 있는지 확인합니다.
if (f==r)
printf("Queue is empty") - 그렇지 않으면 'f'에서 'r'까지의 모든 요소를 인쇄합니다.
for(i=f; i<r; i++)
printf ("%d", q[i]); 프로그램
다음은 배열을 사용하여 큐를 구현하는 C 프로그램입니다 -
#include<limits.h>
#include<stdio.h>
#include <stdlib.h>
struct Queue {
int front, rear, size;
unsigned capacity;
int* array;
};
struct Queue* createQueue(unsigned capacity){
struct Queue* queue = (struct Queue*)malloc(
sizeof(struct Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->array = (int*)malloc(
queue->capacity * sizeof(int));
return queue;
}
//if queue is full
int isFull(struct Queue* queue){
return (queue->size == queue->capacity);
}
// Queue is empty
int isEmpty(struct Queue* queue){
return (queue->size == 0);
}
void Equeue(struct Queue* queue, int item){
if (isFull(queue))
return;
queue->rear = (queue->rear + 1)
% queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
printf("%d entered into queue\n", item);
}
int Dqueue(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)
% queue->capacity;
queue->size = queue->size - 1;
return item;
}
// Function to get front of queue
int front(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// Function to get rear of queue
int rear(struct Queue* queue){
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
int main(){
struct Queue* queue = createQueue(1000);
Equeue(queue, 100);
Equeue(queue, 200);
Equeue(queue, 300);
Equeue(queue, 400);
printf("%d is deleted element from queue\n\n",
Dqueue(queue));
printf("1st item in queue is %d\n", front(queue));
printf("last item in queue %d\n", rear(queue));
return 0;
} 출력
위의 프로그램을 실행하면 다음과 같은 결과가 나온다 -
100 entered into queue 200 entered into queue 300 entered into queue 400 entered into queue 100 is deleted element from queue 1st item in queue is 200 last item in queue 400