C에서 큐 만들기
C의 대기열은 기본적으로 데이터 요소를 저장하고 조작하기 위한 선형 데이터 구조입니다. 선입선출(FIFO)의 순서를 따른다.
대기열에서 배열에 입력된 첫 번째 요소는 배열에서 제거되는 첫 번째 요소입니다.
예를 들어 버스표 예매 매점의 시나리오를 생각해 봅시다. 여기서는 C 프로그래밍 대기열의 방식을 따릅니다. 티켓은 선착순으로 배포됩니다. 즉, 먼저 입장하는 사람에게 티켓이 제공됩니다.
대기열은 양쪽 끝에서 열려 있습니다. 한쪽 끝은 데이터 삽입을 위해 제공되고 다른 쪽 끝은 데이터 삭제를 위해 제공됩니다.
큐는 C, Java, Python 등과 같은 프로그래밍 언어로 구현할 수 있습니다.
C에서 대기열과 관련된 작업
추상 데이터 구조인 대기열은 데이터 요소에 대한 조작을 위해 다음과 같은 작업을 제공합니다.
isEmpty(): 대기열이 비어 있는지 확인하려면isFull(): 큐가 꽉 찼는지 확인하기 위해dequeue(): 대기열의 전면에서 요소를 제거합니다.enqueue(): 큐의 끝에 요소를 삽입합니다.Front: 큐에서 첫 번째 요소를 가져오는 포인터 요소Rear: 큐에서 마지막 요소를 가져오는 포인터 요소
대기열 데이터 구조 작업
대기열은 선입선출 패턴을 따릅니다. 첫 번째 요소는 요소 목록에서 가장 먼저 꺼낸 요소입니다.
Front및Rear포인터는 큐의 첫 번째 요소와 마지막 요소의 레코드를 유지합니다.- 처음에는
Front = -1및Rear = -1을 설정하여 대기열을 초기화해야 합니다.\n - 요소(인큐)를 삽입하려면 큐가 이미 꽉 찼는지 확인해야 합니다. 즉, 오버플로우 조건을 확인해야 합니다. 큐가 가득차지 않으면 Rear 인덱스의 값을 1씩 증가시키고 요소를 Rear 포인터 변수의 위치에 배치해야 합니다. 대기열에 첫 번째 요소를 삽입하게 되면 Front 값을 0으로 설정해야 합니다.
- 대기열에서 요소(dequeue)를 제거하려면 대기열이 이미 비어 있는지 확인해야 합니다. 즉, Underflow에 대한 조건을 확인해야 합니다. 대기열이 비어 있지 않으면 Front 포인터 위치에 있는 요소를 제거하고 반환한 다음 Front 인덱스 값을 1씩 증가시켜야 합니다. 대기열에서 마지막 요소를 제거하게 되면 Front 및 Rear 인덱스 값을 -1로 설정합니다.
C에서 큐 구현
C의 대기열은 배열, 목록, 구조 등을 사용하여 구현할 수 있습니다. 아래에서 C의 배열을 사용하여 대기열을 구현했습니다.
예:
#include <stdio.h>
# define SIZE 100
void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;
main()
{
int ch;
while (1)
{
printf("1.Enqueue Operation\n");
printf("2.Dequeue Operation\n");
printf("3.Display the Queue\n");
printf("4.Exit\n");
printf("Enter your choice of operations : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("Incorrect choice \n");
}
}
}
void enqueue()
{
int insert_item;
if (Rear == SIZE - 1)
printf("Overflow \n");
else
{
if (Front == - 1)
Front = 0;
printf("Element to be inserted in the Queue\n : ");
scanf("%d", &insert_item);
Rear = Rear + 1;
inp_arr[Rear] = insert_item;
}
}
void dequeue()
{
if (Front == - 1 || Front > Rear)
{
printf("Underflow \n");
return ;
}
else
{
printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
Front = Front + 1;
}
}
void show()
{
if (Front == - 1)
printf("Empty Queue \n");
else
{
printf("Queue: \n");
for (int i = Front; i <= Rear; i++)
printf("%d ", inp_arr[i]);
printf("\n");
}
}
산출:
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 10
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 20
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 3
Queue:
10 20
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 2
Element deleted from the Queue: 10
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations: 3
Queue:
20
Stack을 이용한 Queue 구현
스택 데이터 구조는 대기열의 작업을 구현하는 데 사용할 수 있습니다. 이를 사용하여 대기열을 구현하려면 두 개의 스택이 필요합니다. 아래 예제를 살펴보기 전에 스택의 기능을 잘 이해하고 있는지 확인하십시오.
다음 방법 중 하나로 스택을 사용하여 대기열을 구현할 수 있습니다.
- 인큐 작업에 비용이 많이 들게 함
- 대기열 제거 작업 비용 증가
방법 1: 비용이 많이 드는 인큐 작업 만들기
동일한 것을 사용하여 대기열 작업을 구현하기 위해 S1과 S2의 두 스택을 가정합니다.
- S1이 비어 있지 않으면 모든 요소를 스택 2(S2)로 푸시합니다.
- 큐에 넣기 작업을 수행하기 위해 'x'를 큐에 입력할 요소로 가정합니다. 스택 S1에 'x'를 다시 밀어서 맨 위에 오도록 합니다.
- 또한 스택 S2의 모든 요소를 스택 S1로 다시 푸시합니다.
참고: 대기열에 넣기 작업의 시간 복잡도는 O(n)입니다.
- 대기열 제거 작업을 수행하려면 스택 S1에서 항목을 팝해야 합니다. 이제 첫 번째 삽입된 요소가 S1의 맨 아래가 아닌 맨 위에 있기 때문입니다.
참고: 대기열에서 빼기 작업의 시간 복잡도는 O(1)입니다.
Stack을 사용하여 Enqueue 및 Dequeue 작업의 시간 복잡성을 분석하면 Enqueue 작업이 Dequeue 작업보다 비용이 훨씬 많이 든다는 것을 알 수 있습니다.
따라서 위에서 언급한 바와 같이 Dequeue 작업이 호출될 때 제거되도록 첫 번째로 입력된 요소 또는 가장 오래된 입력된 요소를 스택 S1의 맨 위에 유지하도록 합니다.
방법 2: 비용이 많이 드는 대기열 제거 작업 만들기
동일한 것을 사용하여 대기열 작업을 구현하기 위해 S1과 S2의 두 스택을 다시 가정해 보겠습니다.
- Enqueue 연산을 구현하기 위해 새로 입력된 요소를 Stack S1의 맨 위에 삽입합니다. 따라서 스택을 사용한 Enqueue 작업의 시간 복잡도는 O(1)이 됩니다.
- dequeue 동작 구현을 위해 Stack S1과 S2의 Underflow 조건을 확인합니다. 두 스택이 모두 비어 있으면 오류가 발생합니다.
- 스택 S2가 비어 있고 S1도 비어 있지 않으면 스택 S1의 모든 요소가 스택 S2로 이동되고 스택 S2의 맨 위 요소가 팝 아웃되어 대기열 제거 작업에서 반환됩니다.
- 따라서 Stacks를 이용한 dequeue 연산의 시간 복잡도는 O(n)이 됩니다.
대기열 데이터 구조의 응용
- CPU 스케줄링
- 디스크 예약
- 파일 IO 등과 같은 프로세서 간의 비동기 데이터 전송
- 폭 우선 검색 알고리즘(BFS)
결론
이 기사에서 우리는 대기열 데이터 구조의 작동 방식을 이해했으며 스택 데이터 구조를 사용하여 대기열을 구현하는 방법도 설명했습니다.
참조
- C의 대기열
- 스택을 사용한 대기열