[자료구조] 3. Queue

1. 정의

Queue의 가장 큰 특징은, FIFO구조를 가지고 있다는 것이다. Stack구조와 마찬가지로 데이터를 쌓아서 저장한다. 다만 Stack에서는 데이터의 입출력 모두 Top에서 일어나는데 반면, Queue에서는 입력은 back(rear)에서 출력은 front에서 발생하게 된다. 이 때, Queue에서의 입력을 Enqueue라고 말하며, 출력을 Dequeue라고 말한다.(하지만 Insert, Delete를 쓰기도 하며, Stack과 동일하게 push,pop을 쓰기도 한다.) 흔히, Queue를 설명 할 떄, 줄 서기를 비유한다. 매표소에 일렬로 선 줄처럼 먼저 온사람이 먼저 티켓을 사는 구조라고 생각하면 된다.

※ FIFO : First-In-First-Out, 즉 가장 먼저 들어온 데이터가 먼저 빠져나가짐을 의미한다.

<The Concept of Queue>

2. 종류

1) Queue by Array

일반 배열을 이용해 Queue의 시스템을 구현하는 것이다. 즉 동적할당을 사용하지 않아, 처음부터 Queue의 크기를 정해야한다는 점이 단점이다. 마찬가지로, 배열로 구성한 Queue에 데이터 삽입과 삭제를 반복하면, front와 back의 인덱스가 증가해 활용할 수 있는 Queue의 크기가 작아진다는 문제점이 있다. 이 때문에 주로 Circular Queue를 구성해 문제를 해결한다.

2) Queue by List

Linked List처럼 List를 이용해 Queue를 구성하는 것이다. 즉 메모리가 허용하는 한, Queue의 크기를 늘릴 수 있을 것이다.

3) Circular Queue

Circular Linked List처럼 Queue의 Front와 Back을 연결시킨다. 이 방법은 List를 이용해 구현할 때보다, 크기가 한정된 Array를 사용해 구성할 때 자주 구현하는듯 하다.

<The Concept of Circular Queue>

3. 구현

#include<stdio.h>
#include<stdlib.h>
 
/*Queue에 사용할 Node*/
typedef struct _node *nodeptr;
typedef struct _node{
    int data;
    nodeptr link;
}node;
 
/*Queue의 Front와 Back을 포인터를 이용해 표시한다.*/
nodeptr Head,Tail;
 
void Enqueue(int);
void Dequeue();
 
int main(void){
    int n,i,temp;
 
    printf("Input the number of data : ");
    scanf("%d",&n);
 
    i=0;
 
    while(i!=n){
        scanf("%d",&temp);
        
        Enqueue(temp);
 
        i++;
    }
    i++;
    while(i){
        Dequeue();
        i--;
    }
 
    return 0;
}
 
/*Queue에 새로운 데이터를 Back에 추가*/
void Enqueue(int data){
    nodeptr tempnode;
 
    tempnode=(nodeptr)malloc(sizeof(node));
    tempnode->data=data;
    tempnode->link=NULL;
    
    if(!Head) Head=tempnode;
    if(Tail) Tail->link=tempnode;
    Tail=tempnode;
 
    return;
}
 
/*Queue의 Front가 비어있지 않다면, Front의 node를 삭제*/
void Dequeue(){
    nodeptr temp;
 
    if(Head){
        temp=Head->link;
        free(Head);
        Head=temp;
    }
    else{
        printf("Queue is Empty!\n");
    }
    return;
}