Queue - 원형 큐, 연결리스트

 

큐는 먼저 들어온 데이터가 먼저 나가는 구조로 (FIFO)  스택과 반대되는 개념이라고 볼 수 있다.

 

출처:https://ko.wikipedia.org/wiki

큐에서 자료를 넣는 연산은 Enqueue, 자료를 꺼내는 연산을 Dequeue라고 한다.

 

단순히 스택과 반대되는 개념이므로 쉽게 생각할 수도 있지만, 한가지 생각할 점이 있다.

Back 방향  데이터가 삽입되고, Rear가 그 위치를 나타낸다. 

Front 방향으로 데이터가 꺼내지고, 그 위치를 Front가 가리킨다. 

 

1. 단순 배열 기반 큐

 

배열은 크기가 미리 정해져 있기 때문에, 이를 기반으로 한 큐를 구현하면, 같은 한계를 지닌다.

출처:https://velog.io/@gillog/%ED%81%90Queue

다음과 같이 배열의 크기가 6인 상황에서 모든 데이터를 Dequeue한다고 생각해보자.

그렇다면, 이제 Rear가 가리킬 수 있는 것은 배열의 마지막 인덱스 뿐이고, 넣을 수 있는 자료도 1개뿐 일것이다. 

그렇게 되면, 앞에 5개의 공간이 낭비된다.이처럼 단순 배열을 기반으로 queue를 구현하면,  크기가 6인 배열에 자료를 1개 밖에 담을 수 없는 것처럼 매우 비효율적인 부분이 발생한다.

 

이러한 단점을 보완하는 구조가 원형 큐이다.

 

2. 원형 큐 

 

출처: https://www.geeksforgeeks.org/introduction-to-circular-queue/

위와 같이 배열을 순환하면서 자료를 넣고, 빼는 구조를 원형 큐라고한다.

단순 배열기반 큐와 마찬가지로 Rear방향으로 자료가 삽입되고, front방향으로 자료가 꺼낸다.

원형큐를 단순히 구현하기 전에, 원형 큐에서 생각해볼 문제가 하나 있다.

 

2.1 원형 큐의 full? empty?

 

 원형큐가 가득찬 상태와 빈 상태를 어떻게 나타낼 것인가 하는 문제이다.

 Rear == Front인 상태를 빈 상태로 생각할 수도 있지만, 원형 큐에서 Rear이 배열을 한바퀴 돈다면, Rear==Front가 되어 

가득찬 상태일 수 도 있다.

Rear + 1 == Front인 상태도 마찬가지로 가득찬 상태와 빈상태를 구분할 수 없다. 

즉, 원형큐를 그냥 처음부터 채운다면, Rear과 Front의 위치로 가득찬 상태와 빈 상태를 구분할 수 없다는 것이다.

 

이를 해결하는 방법은 배열의 처음부터 값을 채우지 않고, 한칸을 비워두고 시작하는 것이다.  이러한 상태에서는

Rear == Front는 빈상태, Rear + 1 == Front인 상태는 가득찬 상태로 정의할 수 있다.

데이터를 한개 낭비하지만, 이를 통해 얻는 이점이 크다.

 

2.2 구현 

 

헤더

#ifndef __Cir_queue_h

#define __Cir_queue_h

#define MAX_LEN 100

typedef int data;

typedef struct _Cqueue{

    int frount;

    int re;

    data qudata[MAX_LEN];

}Cqueue;

typedef Cqueue Queue;

void QueInit(Queue* qp);

int QEmpty(Queue* qp);

void Enqueue(Queue* qp, data data);

data Dequeue(Queue* qp);

data peek(Queue* qp);

#endif

소스

#include "Circular_Queue.h"

#include <stdlib.h>

#include <stdio.h>

void QueInit(Queue* qp){

    qp->frount =0; //q배열의 인덱스

    qp->re =0; // 원형의 첫 인덱스는 0

}

int QEmpty(Queue* qp){

    if(qp->re  == qp->frount ) return 1;

    else 0;

}

void Enqueue(Queue* qp, data data){

    if(((qp->re)%MAX_LEN) +1 == qp->frount){

        printf("Queue is full");

        exit(-1);

    }else{

        qp->qudata[(++qp->re)%MAX_LEN] = data;

    }

}

data Dequeue(Queue* qp){

    if(QEmpty(qp)){

        printf("Queue is Empty");

        exit(-1);

    }

    data remove = qp->qudata[++(qp->frount)%MAX_LEN];

    return remove;

   

}

data peek(Queue* qp){

    if(QEmpty(qp)){

        printf("Queue is empty");

        exit(-1);

    }

    return qp->qudata[qp->re];

}

int NextPost(int pos){

    if(pos == MAX_LEN -1)

    return 0;

    else pos+1;

   

   

}

 

자바 

class MyAQueue{
    private final int MAX_LEN =100;
    Object[] arr =new Object[MAX_LEN];
    private int frount;
    private  int Rear;

    MyAQueue(){
        frount = 0;
        Rear = 0;
    }
    void Enqueue(Object data){
        if(Rear +1 == frount){
            System.out.print("Queue is full");

        }
        Rear = ++Rear%MAX_LEN;
        arr[Rear] = data;
    }
    Object Dequeue(){
        if(isEmpty()){
            System.out.print("삭제할 데이터 없음");
        }
        frount  = ++frount%MAX_LEN;
        return arr[frount];
    }

    boolean isEmpty(){
        if(Rear == frount) return true;
        else return false;
    }

    Object peek(){
        if(isEmpty()){
            System.out.print("빈 큐");
        }
        return arr[Rear];
    }


}

3. 연결리스트 큐

 

연결리스트를 기반으로 큐를 만들면, 데이터를 낭비하지 않고, 크기 제한 없이 큐를 만들 수 있다.

 

헤더 

#ifndef __Linked_Q

#define __Linked_Q

typedef int data;

typedef struct _node

{

    data data;

    struct _node* next;

}node;

typedef  struct _LinkedQ{

    node* f;

    node* r;

    int size;

}LinkedQ;

typedef LinkedQ Que;

void QueInint(Que* pq);

int Qempty(Que* pq);

void Enqu(Que* pq, data data);

data Dqu(Que* pq);

data qpeek(Que* pq);

int size(Que* pq);

#endif

소스 

#include"LinkedQ.h"

#include<stdio.h>

#include<stdlib.h>

void QueInint(Que* pq){

    pq->f = NULL;

    pq->r = NULL;

    pq->size =0;

}

int Qempty(Que* pq){

if(pq->f == NULL ) return 1; //dqu 연산시 마지막 노드 삭제하면 pq->f ==null이지만, r은 모름..! 그래서

                            //empty는 f로 판단하는게 좋다.

else return 0;

}

void Enqu(Que* pq, data data){

    node* newnode = (node*)malloc(sizeof(node));

    newnode->data =data;

    newnode->next = NULL;

    if(pq->r==NULL){

        pq->f = newnode;

        pq->r = newnode;

    }else{

        pq->r->next = newnode;

        pq->r = newnode;

    }

    (pq->size)++;

}

data Dqu(Que* pq){

    if(Qempty(pq)){

        printf("빈 큐 \n");

        exit(-1);

    }

    node* remove = pq->f;

    data rdata = pq->f->data;

     

    pq->f = pq->f->next;

    free(remove);

    (pq->size)--;

    return rdata;

}

data qpeek(Que* pq){

    if(Qempty(pq)){

        printf("빈 큐 \n");

        exit(-1);

    }

    return pq->f->data;

}

int size(Que* pq){

    return pq->size;

}

 

연결리스트를 기반으로 큐를 만드는 것은 단순연결리스트의 구현과 비슷하므로 어려울 것이 없다.

단, 한가지 생각해볼 점은, empty를 어떻게 정의할 것이냐이다. 

qp -> f(front) == NULL 혹은 qp -> r (Rear) == NULL 중에 무엇을 택하는 것이 좋을까? 물론 둘다 NULL일때 Empty로 생각해도 상관은 없지만, 삭제하는 과정을 생각해보면, 둘 중 하나만 택해도 된다.

 

출처:https://www.log2base2.com/data-structures/queue/queue-using-linked-list.html

다음과 같이 노드가 추가되어 있을때, 노드를 계속 삭제해보자.

front = front->next를 가리키게 될 것이고, rear까지 삭제된다면, front = null이 된다.

이때, rear은 무엇을 가리키는지 알 수 없다. 하지만, 새로운 데이터가 추가된다면, 그 데이터를 가리킬 것이다.

따라서 front = null 상황만 빈상태로 정의해도 상관없다. 물론 포인터 변수를 null로 초기화해두지 않는 찝찝함이 있을 수 는 있지만, 상황에 따라 이런 경우도 있다고 한다.

 

참고자료:

-윤성우 열혈자료구조

 

https://velog.io/@gillog/%ED%81%90Queue

큐(Queue)