[자료구조 - C언어] 자료구조 제18강: 큐(queue)의 개념과 구현(1)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 큐(Queue)

• 큐는 일종의 리스트
  • 일반 리스트: 아무 곳에서나 삽입/삭제 가능
  • 스택: 삽입과 삭제가 한쪽 끝에서만 이루어짐
  • 큐: 삽입은 한 쪽 끝에서, 삭제는 반대쪽 끝에서 일어남
    • 삽입이 일어나는 쪽을rear, 삭제가 일어나는 쪽을 front라고 부름
• FIFO(First-In, First-Out): 가장 먼저 들어간 애가 가장 먼저 나옴

 

2. 큐가 지원하는 연산

• 큐는 스택처럼 연산을 하나의 통일된 이름으로 부르지 않고, 다양한 이름으로 부른다.
• enqueue: 큐의 rear에 새로운 원소를 삽입하는 연산
  • insert, offer, push
• dequeue: 큐의 front에 있는 원소를 큐로부터 삭제하고 반환하는 연산
  • remove, poll, pop
• peek: 큐의 front에 있는 원소를 제거하지 않고 반환하는 연산 → 큐에 변화 없음
  • element, front
• is_empty: 큐가 비었는지 검사

 

3. 큐의 응용

• CPU 스케쥴링
  • 멀티태스킹 환경(= 동시에 여러 프로그램이 실행되는 것처럼 느끼는 환경)에서 프로세스들은 큐에서 CPU가 할당되기를 기다린다.
    • 각각의 프로세스들은 아주 짧은 시간동안 실행→ 대기를 반복(큐에서)
• 데이터 버퍼
  • 네트워크를 통해 전송되는 패킷(packet)들은 도착한 순서대로 버퍼에 저장되어 처리되기를 기다린다.
• 그 외에도 자원을 공유하는 대부분의 경우에 큐가 사용됨

 

4. 연결 리스트를 이용한 큐의 구현

4-1. 큐의 front와 rear

• 연결 리스트의 첫 번째 노드를 front(삭제)
  • 연결 리스트의 첫 번째 노드에서는 삽입과 삭제에 무리가 없다.
    • add_first, remove_first 가능
• 연결 리스트의 마지막 노드를 rear(삽입)
  • 연결 리스트의 마지막 노드에서는 삽입은 할 수 있지만 삭제에는 무리가 있다.
    • 노드를 삭제하려면 그 앞 노드의 주소를 알아야 하는데
    • 단방향 연결 리스트에서 앞 노드의 주소를 알기 위해서는 연결 리스트 전체를 순회해야 하기에 무리가 있다.

4-2. 연결 리스트로 구현한 큐

• queueADT.h

//  queueuADT.h

#ifndef QUEUEADT_H
#define QUEUEADT_H

#include <stdbool.h>

typedef int Item;
typedef struct queue_type *Queue;

Queue create();
void destroy(Queue q);
void make_empty(Queue q);
bool is_emtpy(Queue q);
void enqueue(Queue q, Item i);
Item dequeue(Queue q);
Item peek(Queue q);
//큐를 사용할 때는 현재 큐 안에 몇개의 데이터가 있는지를 알아야 하는 상황이 빈번하다.
int get_size(Queue q);

#endif /* QUEUEADT_H */

• queueADT_linkedlist.c

//  queueuADT_linkedlist.c

#include <stdio.h>
#include <stdlib.h>
#include "queueuADT.h"

struct node{
    Item data;
    struct node *next;
};

struct queue_type{
    struct node *front;    //연결 리스트의 첫 번째 주소
    struct node *rear;      //연결 리스트의 마지막 주소
    int size;                         //노드의 개수
};

//오류 발생시 메세지 출력 함수
void terminate(const char *message){
    printf("%s\\n", message);
    exit(EXIT_FAILURE);
}

//큐의 사이즈를 리턴하는 함수
int get_size(Queue q){
    return q->size;
}

//큐를 생성하고 주소를 리턴하는 함수
Queue create(){
    Queue q = (Queue)malloc(sizeof(struct queue_type));
    if(q==NULL)
        terminate("Error in create: queue could not be created.");
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
    return q;
}

//동적 메모리 할당으로 생성한 큐를 제거하는 함수
//가비지를 만들지 않기 위해서
void destroy(Queue q){
    //각각의 노드를 먼저 free
    make_empty(q);
    free(q);
}

void make_empty(Queue q){
    while(!is_empty(q))
        dequeue(q);
    q->size = 0;
}

//큐가 비었는지 검사
bool is_empty(Queue q){
    return q->front == NULL;
    //or return q->size==0;
}

//큐의 rear에 새로운 item 삽입 함수
void enqueue(Queue q, Item i){
    struct node *new_node = malloc(sizeof(struct node));
    if(new_node == NULL)
        terminate("Error in enqueue: queue is full.");
    
    //노드에 데이터 삽입, 초기화
    new_node->data = i;
    new_node->next = NULL;
    
    //큐가 empty인 경우
    //- 처음으로 어떤 값이 enqueue될 때
    if(q->front == NULL){
        q->front = new_node;
        q->rear = new_node;
    }
    //큐가 empty가 아닌 경우
    //- rear가 큐의 마지막 노드를 가리키고 있을 때
    else{
        q->rear->next = new_node;
        q->rear = new_node;
    }
    q->size++;
}

//큐의 front의 값 삭제하는 함수
//remove_first와 유사
Item dequeue(Queue q){
    struct node *old_front;
    Item i;
    
    if(is_empty(q))
        terminate("Error in dequeue: queue is empty.");
    
    //front가 2번째 노드를 가리키게 하고
    //1번째 노드의 데이터를 리턴, free
    old_front=q->front;
    i = old_front->data;    //리턴할 값 저장
    q->front = old_front->next;
    
    //삭제할 노드가 유일한 노드라면
    if(q->front==NULL)
        q->rear = NULL;
    
    free(old_front);
    q->size--;
    return i;
}

//큐의 front값을 반환만 하는 함수
Item peek(Queue q){
    if(is_empty(q))
        terminate("Error in peek: queue is empty.");
    return q->front->data;
}

//임의 생성 함수
void print_queue(Queue q){
    struct node *tmp = malloc(sizeof(struct node));
    tmp = q->front;
    for(int i=0; i<q->size; i++){
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    printf("\\n");
    free(tmp);
}

• main.c

//  main.c

int main(){
    Queue q = create();
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    printf("enqueue: ");
    print_queue(q);
    printf("dequeue: ");
    dequeue(q);
    print_queue(q);
    printf("peek: %d\\n", peek(q));
}

//enqueue: 1 2 3 
//dequeue: 2 3 
//peek: 2

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://youtu.be/_aU2e70gYlo