6. 큐 - 큐의 구조 / 큐의 구현 / 배열을 이용한 구현 / 연결 리스트를 이용한 구현 / 큐 삽입 과정 / 큐 삽입 함수 / 큐 추출 과정

큐

큐(Queue)는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료 구조(Data Structure)이다. 이러한 특성 때문에 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용된다. 큐는 크게 2가지 함수로 구성된다.

• push : 큐에 데이터를 넣는다.
• pop : 큐에서 데이터를 빼낸다.

C언어를 이용해 큐 자료구조를 직접 구현해 보고, 큐 자료구조의 개념과 활용 방법을 이해한다.

 

큐는 다음과 같은 명령어 세트가 존재할때, 그림과 같이 동작한다.

 

큐의 구현

큐(Queue)는 배열을 이용한 구현 방법, 연결리스트를 이용한 구현 방법이 있다. 가장 기본적인 형태의 자료구조로 구현 난이도는 낮은 편이다. 먼저 배열을 이용한 구현 방법은 다음과 같다.

 

배열을 이용한 큐 구현

큐의 선언

#include <stdio.h>
#define SIZE 1000
#define INF 9999999

int queue [SIZE];
int front = 0;
int rear = 0; // 앞과 뒤가 전부 '0'인덱스를 가리키게 함

큐 삽입 함수

void push (int data){
    if(rear >=SIZE){
        printf("스택 오버플로우가 발생했습니다.\n");
        return;
    }
    queue[rear++] = data; //rear에 +1한 위치에 data를 넣음
}

큐 추출 함수

void pop(int data){
    if(front == rear){
        printf("스택 언더플로우가 발생했습니다.\n");
        return -INF;
    }
    return queue[front++];
}

-> queue에서 front에 해당하는 값을 꺼낸 뒤, front를 1 더해서 하나의 값이 꺼내졌다는 것을 확인 할 수 있게 한다.

 

큐 전체 출력 함수

void show(){
    printf("---큐의 앞---\n");
    
    for(int i = front; i < rear; i++){
        printf("%d %d\n", queue[i],i);
    }
    printf("---큐의 뒤---\n");
}

 

완성된 큐 사용하기

int main(void){
    push(7);
    push(5);
    push(4);
    pop(); 
    push(6);
    pop();
    show();
    system("pause");
    return 0;
}

---큐의 앞---
4
6
---큐의 뒤---

 

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

 

큐의 선언

typedef struct Node{
    int data;
    Node *next;
}Node;

typedef struct Queue{
    Node *front;
    Node *rear;
    int count; //큐에 포함된 원소들의 갯수
}Queue;

큐에서 스택과 구성이 다른점은, 노드가 2개(front, rear)가 들어간다. 

 

큐 삽입 과정

 

큐 삽입 함수

void push(Queue *queue, int data){
    Node *node =(Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if(queue->count == 0){ //큐가 현재 비어있는경우(초기세팅)
        queue->front = node; //front에 새 노드를 넣어줌
    }
    else{
        queue->rear->next = node;
    }
    queue->rear = node;
    count++;
}

 

큐 추출 과정

 

큐 추출 함수

void pop(Queue *queue){
    if(queue->count ==0){
        printf("스택 언더플로우가 발생했습니다\n");
        return -INF;
    }
    Node *node = queue->front;
    int data = node->data;
    queue->front = node->next;
    free(node);
    queue->count--;
    return data;
}

 

큐 전체 출력 함수

void show(Queue *queue){
    Node *cur = queue->front;
    if(queue->count == 0){
        printf("스택 언더플로우가 발생했습니다");
        return -INF;
    }
    printf("---큐의 앞---\n");
    while(cur != NULL){ 
        printf("%d\n",cur->data);
        cur = cur->next;
    }
    printf("---큐의 뒤---\n");
}

 

완성된 큐 사용하기

int main(void){
    Queue queue;
    queue.front = queue.rear = NULL;
    queue.count = 0;
    push(&queue, 7);
    push(&queue, 5);
    push(&queue, 4);
    pop(&queue);
    push(&queue, 6);
    pop(&queue);
    show(&queue);
    system("pause");
    return 0;
}

---큐의 앞---
4
6
---큐의 뒤---