Goal

  • Queue(큐)의 개념을 이해한다.
  • Queue를 C언어로 구현한다.

Queue(큐) 개념

  • 큐는 스택과 마찬가지로 일종의 리스트
  • 데이터 삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서만 일어난다
  • 삽입이 일어나는 쪽을 rear, 삭제가 일어나는 쪽을 front라고 부른다.
  • FIFO(First-in, First-Out)

image.png

Queue(큐)에서 지원하는 연산

  • insert, enqueue, offer, push : queue의 rear에 새로운 원소를 삽입하는 연산

  • remove, dequeue, poll, pop : queue의 front에 있는 원소를 queue로부터 삭제하고 반환하는 연산

  • peek, element, front : 큐의 front에 있는 원소를 제거하지 않고 반환하는 연산

  • is_empty : 큐가 비었는지 검사

Queue(큐)의 응용

  • cpu 스케쥴링 : multitasking 환경에서 프로세스들은 큐에서 cpu가 할당되기를 기다린다.

  • 데이터 버퍼 : 네트워크를 통해 전송되는 패킷들은 도착한 순서대로 버퍼에 저장되어 처리되기를 기다린다

  • 자원을 공유하는 대부분의 경우에 큐가 사용 된다

![image.png](https://images.velog.io/post-images/p
a324/88b5f5b0-9fa4-11e9-8684-dd86c4efd59d/image.png)

Queue(큐)의 구현

배열 혹은 연결리스트를 이용해서 구현할 수 있다.

1.Linked List로 구현

  • rear에서는 삽입, front에서는 삭제가 일어난다. 따라서 연결리스트의 앞쪽을 front, 뒤쪽을 rear로 하는것이 유리하다.

  • 삽입을 하기 위해서는 마지막 노드의 주소를 항상 기억해야 한다.

※동적메모리 할당
변수를 선언하는 대신 프로그램의 요청으로 메모리를 할당할 수 있다. 이것을 동적메모리 할당 (dynamic memory allocation)이라고 부른다.
malloc 함수를 호출하여 동적메모리할당을 요청하면 요구하는 크기의 메모리를 할당하고 그 시작 주소를 반환한다.

int * p;
p = (int *)malloc(40); // malloc이 반환하는 주소는 타입이 없는 주소(void *)이다. 정수들을 저장하기 위해서 이것을 int *로 변환한다.
if(p == NULL) {
   /* 동적 메모리 할당이 실패 */
   /* 적절한 조치를 취한다. */
}
p[0] = 12;
p[1] = 24;
*(p+2) = 36;

※ Queue(큐) 구현

//큐 - 연결리스트 이용
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node //노드 정의
{
    int data;
    struct Node *next;
}Node;


typedef struct Queue //Queue 구조체 정의
{
    Node *front; //맨 앞(꺼낼 위치)
    Node *rear; //맨 뒤(보관할 위치)
    int count;//보관 개수
}Queue;

void InitQueue(Queue *queue);//큐 초기화
int IsEmpty(Queue *queue); //큐가 비었는지 확인
void Enqueue(Queue *queue, int data); //큐에 보관
int Dequeue(Queue *queue); //큐에서 꺼냄

int main(void)
{
    int i;
    Queue queue;

    InitQueue(&queue);//큐 초기화
    for (i = 1; i <= 5; i++)//1~5까지 큐에 보관
    {
        Enqueue(&queue, i);
    }
    while (!IsEmpty(&queue))//큐가 비어있지 않다면 반복
    {
        printf("%d ", Dequeue(&queue));//큐에서 꺼내온 값 출력
    }
    printf("\n");
    return 0;
}

void InitQueue(Queue *queue)
{
    queue->front = queue->rear = NULL; //front와 rear를 NULL로 설정
    queue->count = 0;//보관 개수를 0으로 설정
}

int IsEmpty(Queue *queue)
{
    return queue->count == 0;    //보관 개수가 0이면 빈 상태
}

void Enqueue(Queue *queue, int data)
{
    Node *now = (Node *)malloc(sizeof(Node)); //노드 생성
    now->data = data;//데이터 설정
    now->next = NULL;

    if (IsEmpty(queue))//큐가 비어있을 때
    {
        queue->front = now;//맨 앞을 now로 설정       
    }
    else//비어있지 않을 때
    {
        queue->rear->next = now;//맨 뒤의 다음을 now로 설정
    }
    queue->rear = now;//맨 뒤를 now로 설정   
    queue->count++;//보관 개수를 1 증가
}

int Dequeue(Queue *queue)
{
    int re = 0;
    Node *now;
    if (IsEmpty(queue))//큐가 비었을 때
    {
        return re;
    }
    now = queue->front;//맨 앞의 노드를 now에 기억
    re = now->data;//반환할 값은 now의 data로 설정
    queue->front = now->next;//맨 앞은 now의 다음 노드로 설정
    free(now);//now 소멸
    queue->count--;//보관 개수를 1 감소
    return re;
}

[참조]