큐가 뭔가요!( C,Queue)[2]

본 포스트는 c언어를 중심으로 작성되었습니다.

 

큐가 뭔가요!( C,Queue)[2]

 

저번 포스트에 이어 계속 포스트 해왔던대로 이번엔 연결리스트를 통한 구현을 해보겠습니다. 

 

저 또한 의문이 들었습니다. 순차자료구조, 연결자료구조 이거 두개 다 뭐 구현이 가능한데? 왜 나눠서 구분 짓고 이럴땐 이렇게 사용하고 저럴땐 저렇게 사용할까? 라는 의문을 가져보았습니다.

 

구글링을 열심히 해본결과로는 순차자료구조를 이용해 구현한 큐는 치명적인 단점이 존재합니다. 앞서 포스트에서도 기술했듯이 배열의 크기가 고정되므로 큐의 길이를 유동적으로 변화 시킬 수 없으며 데이터가 없어도 항상 고정된 크기를 가져야 하기 때문에 메모리누수 문제가 심각하다는 이유입니다.

 

즉,

<- out

first data

--

last data

<-- in

 

앞서 말씀드렸듯이 선입선출 방식을 따릅니다. 본 포스트가 이해가 잘 가시지 않는 다면 앞의 포스트를 보고 오시는것을 추천 드립니다. 

 

개인적인 소견은 큐의 구현방식이 조금 더 익숙하다 생각합니다. 사회적 현상으로 미뤄볼 때 먼저 들어온 사람이 먼저 나가는 것이 꽤나 당연하기 때문이여서 입니다. 물론 후입선출 방식 또한 이렇게 생각할 수 있으나, 일반적인 방식을 생각했습니다.

 

그렇다면 연결리스트를 사용해서 구현해야하는 이유는 뭔지 생각해보았습니다.

 

연결리스트는 우선 크기 제한이 없습니다. 조금 더 효율적으로 구현하면 원형연결리스트 또한 염두에 둘 수 있지만,  1차원 연결리스트만 구현해볼 생각입니다. 크기 제한이 없다는것 즉, 메모리의 누수가 발생하지 않으며, 유동적으로 사용할 수 있기 때문에 최적화가 조금 더 잘 이뤄지지 않을까 에서 입니다. 물론 고정된 크기를 가지는 데이터의 모음으로 구현한다면 순차리스트를 사용하는 것이 조금 더 효율적일 수 있으나, 언제 어디서 데이터를 추가해야할 상황이 올지 모르기에 개인적으로는 연결리스트가 구현에 있어서 낫다고 생각합니다.

 

그렇다면 논리적구조는 어떤 형태를 띄고 있을지 먼저 보겠습니다. 

 

1번지 1	2번지 주소->	2번지 2	3번지주소->	3번지 3	4번지주소->	4번지 4	null
first 포인터	ㅇㅇㅇㅇㅇㅇ	ㅇㅇㅇㅇㅇ	ㅇㅇㅇㅇㅇ	ㅇㅇㅇㅇㅇ	ㅇㅇㅇㅇㅇ	last포인터	ㅇㅇㅇㅇㅇ

 

 

위와 같습니다. 첫번째 포인터와 마지막 포인터만 있다면 쉽게 구현할 수 있습니다. 마지막 노드의 링크는 null입니다.

 

그렇다면 코드로 넘어가 구현해보도록 하겠습니다.

 

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef char element;
typedef struct Qnode
{
    element data;
    struct Qnode *link;
}QNode;
 
typedef struct
{
    QNode *first, *last;
}QueueType;
 
QueueType *createdlinkedQueue()
{
    QueueType *Q;
    Q = (QueueType*)malloc(sizeof(QueueType));
    Q->first = NULL;
    Q->last = NULL;
    return Q;
}
 
int isEmpty(QueueType *Q)
{
    if (Q->first == NULL)
    {
        printf("연결리스트가 비어있습니다"); return 1;
    }
    else return 0;
}
 
void enQueue(QueueType *Q, element *indata)
{
    QNode *newNode = (QNode*)malloc(sizeof(QNode));
    newNode->data = indata;
    newNode->link = NULL;
    if (Q->first == NULL)
    {
        Q->first = newNode;
        Q->last = newNode;
    }
    else
    {
        Q->last->link = newNode;
        Q->last = newNode;
    }
}
 
element deQueue(QueueType *Q)
{
    QNode *del = Q->first;
    element wasdata;
    if (isEmpty(Q)) return 1;
    else
    {
        wasdata = del->data;
        Q->first = Q->first->link;
        if (Q->first == NULL)
        {
            Q->last = NULL;
        }
        free(del);
        return wasdata;
    }
}
 
element search(QueueType *Q)
{
    element wasdata;
    if (isEmpty(Q)) return 1;
    else
    {
        wasdata = Q->first->data;
        return wasdata;
    }
}
 
void Print(QueueType *Q)
{
    QNode *dbd = Q->first;
    printf("연결리스트 :");
    while (dbd)
    {
        printf("%3c", dbd->data);
        dbd = dbd->link;
    }
}
 
void main(void)
{
    QueueType *Q = createdlinkedQueue();
    element data;
    printf("연결리스트 구현");
    printf("\n INSERT A -> "); enQueue(Q, 'A'); Print(Q);
    printf("\n INSERT B -> "); enQueue(Q, 'B'); Print(Q);
    printf("\n INSERT C -> "); enQueue(Q, 'C'); Print(Q);
 
    print("\n 데이터 찾기");
 
}

위와 같이 연결리스트를 이용한 큐를 구현할 수 있습니다.

 

연결리스트는 코드를 적는 과정 중에서 -> 를 이용해, 보다 복잡함을 느낍니다. 이보다 더 간략하게 표현할 수 있는 방법을 없을까해도 화살표 만한게 없더라구요.. ㅋㅋㅋㅋ

 

봐주셔서 감사하고 댓글 / 피드백 환영합니다!