큐(Queue)

큐(Queue)

원형 큐(Circular Queue)

원형 큐는 배열의 선형 큐의 머리와 꼬리를 연결한 큐이다. 기본적으로 원리는 다음과 같다. 

Enqueue

Dequeue

이렇듯 추가를 하면  R(Rear)이 다음 인덱스를 가리키고 그 곳에 데이터를 추가한다. 삭제를 할 경우에는 F(Front)가 다음 인덱스로 이동한다. 

여기서 위의 경우에는 Empty와 Full을 구분하기가 어렵다. 그래서 배열의 길이가 n일 때 n-1개 채울 경우 꽉 찬 것으로 간주한다.

원형 큐의 구현

헤더파일

#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__
 
#define TRUE    1
#define FALSE    0
 
#define QUE_LEN    100
typedef int Data;
 
typedef struct _cQueue
{
    int front;
    int rear;
    Data queArr[QUE_LEN];
} CQueue;
 
typedef CQueue Queue;
 
void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);
 
void Enqueue(Queue * pq, Data data);                                                                       
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);
 
#endif

소스파일

#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"
 
void QueueInit(Queue * pq)
{
    pq->front = 0;
    pq->rear = 0;
}
 
int QIsEmpty(Queue * pq)
{
    if(pq->front == pq->rear)
        return TRUE;
    else
        return FALSE;
}
 
int NextPosIdx(int pos)
{
    if(pos == QUE_LEN-1)
        return 0;
    else
        return pos+1;
}
 
void Enqueue(Queue * pq, Data data)
{
    if(NextPosIdx(pq->rear) == pq->front)                                                                    
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
 
    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;
}
 
Data Dequeue(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
 
    pq->front = NextPosIdx(pq->front);
    return pq->queArr[pq->front];
}
 
Data QPeek(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
 
    return pq->queArr[NextPosIdx(pq->front)];
}

main.c

#include <stdio.h>
#include "CircularQueue.h"
 
int main(void)
{
    Queue q;
    QueueInit(&q);
 
    Enqueue(&q, 1);  Enqueue(&q, 2);
    Enqueue(&q, 3);  Enqueue(&q, 4);                                                                       
    Enqueue(&q, 5);
 
    while(!QIsEmpty(&q))
        printf("%d ", Dequeue(&q)); 
 
    return 0;
}

연결리스트 기반 구현

헤더파일

#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__
 
#define TRUE    1
#define FALSE    0
 
typedef int Data;
 
typedef struct _node
{
    Data data;
    struct _node * next;
} Node;
 
typedef struct _lQueue
{
    Node * front;
    Node * rear;
} LQueue;
 
typedef LQueue Queue;
 
void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);
 
void Enqueue(Queue * pq, Data data);                                                                       
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);
 
#endif

소스파일

#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"
 
void QueueInit(Queue * pq)
{
    pq->front = NULL;
    pq->rear = NULL;
}
 
int QIsEmpty(Queue * pq)
{
    if(pq->front == NULL)
        return TRUE;
    else
        return FALSE;
}
 
void Enqueue(Queue * pq, Data data)
{
    Node * newNode = (Node*)malloc(sizeof(Node));                                                                    
    newNode->next = NULL;
    newNode->data = data;
 
    if(QIsEmpty(pq))
    {
        pq->front = newNode;
        pq->rear = newNode;
    }
    else
    {
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}
 
Data Dequeue(Queue * pq)
{
    Node * delNode;
    Data retData;
 
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
 
    delNode = pq->front;
    retData = delNode->data;
    pq->front = pq->front->next;
 
    free(delNode);
    return retData;
}
 
Data QPeek(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Error!");
        exit(-1);
    }
 
    return pq->front->data;
}

main.c

#include <stdio.h>
#include "ListBaseQueue.h"
 
int main(void)
{
    Queue q;
    QueueInit(&q);
 
    Enqueue(&q, 1);  Enqueue(&q, 2);                                                                    
    Enqueue(&q, 3);  Enqueue(&q, 4);
    Enqueue(&q, 5);
 
    while(!QIsEmpty(&q))
        printf("%d ", Dequeue(&q)); 
 
    return 0;
}

---------------------------------------------------------------

이 글은 윤성우의 열혈 자료구조를 보고 정리한 글 입니다.