[Data Structure] Queue

자료구조 중 큐라고 하는 구조가 있다.

큐는 영어사전에 '(무엇을 기다리는 사람・자동차 등의) 줄' 이라고 나온다.

이 의미가 큐를 가장 잘 설명해주고있다고 생각한다.

그렇담 큐가 가지는 성질은 어떨지 대략 짐작이 갈것이다.

조금 더 자세히 살펴보자.

큐는 '줄'이라는 단어가 의미하듯 먼저 들어간 데이터가(first in) 먼저 나오는(first out) 구조이다.

흔히 줄여서 FIFO 라고 하는데, 선입선출 이라고 부르기도 한다. 

(비슷하게 스택구조는 FILO 구조이다.)

또한 큐는 스택의 전단(Front)과 후단(Rear)이라는 처음과 끝을 가리키는 지시자를 기본 요소로 가진다.

이 두 지시자를 가지고 큐의 삽입(Enqueue)과 제거(Dequeue)를 수행하고 관리하게 되는것이다.

일단 크기가 정해져있는 배열구조의 큐를 생각해보자.

 전단=후단 

    ↓                                                                   

[     ][     ][     ][     ][     ][     ][     ][     ][     ][     ]            //[    ]는 큐의 각 노드

맨 처음 큐의 구조는 요렇게 생겼을 것이다.

데이터가 하나도 없고, 전단과 후단이 가리키는 배열요소는 0으로 같다.

그러다가 데이터가 하나 들어오면,

 전단  후단 

    ↓     ↓                                                              

[  D ][     ][     ][     ][     ][     ][     ][     ][     ][     ]

이런모습이 되는데, 후단은 다음 빈 공간을 가리키고 있구나..  정도만 느끼고 넘어가자

그러면 데이터 다섯개를 더 넣어보자.

전단                                               후단 

    ↓                                                 ↓                                                              

[  D ][  D ][  D ][  D ][  D ][  D ][     ][     ][     ][     ]

그리고 세번의 제거연산을 했다.

데이터를 제거할 때, 전단이 가리키는 데이터를 지운 후 데이터를 하나씩 앞당긴다면 뒤엣일은 걱정하지 않아도 되겠지만, 비용부담이 너무 크고 덜닦인 엉덩이처럼 찝찝하다..

그래서 제거연산을 전단이 가리키는 배열요소를 하나씩 증가시키기로 하자.

                            전단                  후단 

                              ↓                       ↓                                                              

[     ][     ][     ][  D ][  D ][  D ][     ][     ][     ][     ]

이렇게 삽입, 제거를 반복하다가..

아래 그림과같이 되버렸다

                                            전단                           후단 

                                              ↓                                ↓                                                              

[     ][     ][     ][     ][     ][  D ][  D ][  D ][  D ][     ]

앗?!!  다음에 데이터를 넣으려고 한다면 후단이 배열의 범위를 넘어서 가리키기때문에

심각한 에러가 발생한다.

후단이 배열요소를 넘어서지 못하게 한다해도, 전단이 계속 앞으로 움직이니 큐에 저장할 수 있는 용량이 

줄어들고있다...  이것또한 문제로다.

그렇다면, 이 문제를 어떻게 해결하면 좋을까?

라는 생각중 가장 단순한 생각이 '후단을 배열요소의 처음으로 돌리면 되지' 일꺼같다.

오호! 데이터를 넣으면서 후단을 한번 돌려보자.

 후단                                     전단                            

    ↓                                        ↓                                                                                              

[     ][     ][     ][     ][     ][  D ][  D ][  D ][  D ][  D ]

해결완료 ㅎ

이처럼 후단이 배열의 끝까지 가게되면 배열요소의 처음으로 돌려놓아서

뱅글뱅글 돌도록(순환하도록) 만든 큐 구조를 순환큐 라고 부른다.

그런데 문제가 완전히 해결된게 아닌것같다.

후단을 처음으로 돌힌후, 계속 데이터를 집어넣어보자

                                             전단=후단                            

                                               ↓                                                                                              

[  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ]

엣?!! 전단이랑 후단이랑 같아졌다.

이것참 심각한 문제다.  이렇게 되버리면 큐가 가득찼는지 공간이 남았는지 알 수가 없다...

이를 해결하기위한 방법 중 가장 일반적인 방법은, 배열의 크기를 원하는 용량의 크기에 +1 하여 만드는것이다.

그러면 처음 생성시

전단=후단 

    ↓                                                                   

[     ][     ][     ][     ][     ][     ][     ][     ][     ][     ][|||]  //[|||]는 추가된 빈 노드

이런 모양이 되고,

제거연산 없이 데이터가 가득찬다면

  전단                                                                                후단

    ↓                                                                                    ↓

[  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ][|||]

이렇게 후단이 빈 공간을 가리키게 된다.

그리고 아까 문제가 됬던 부분까지 제거연산과 후단을 돌리기를 해보자

           후단           전단                                                   

            ↓                ↓                                                       

[  D ][|||][     ][  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ]

한번 더 삽입..

                    후단   전단                                                   

                     ↓       ↓                                                       

[  D ][  D  ][|||][  D ][  D ][  D ][  D ][  D ][  D ][  D ][  D ]

이처럼 후단과 전단 사이에 계속해서 하나의 빈공간이 남게되어 큐가 가득찼는지 남아있는지 확인하기가 쉽다.

..

여기까지 했다면 순환큐의 중요한 내용들은 모두 해결했다.

으흥.. 참 까다로운 구조다..

이것저것 신경써줘야 할께 많은 예민하고 고급스런 아이같다..

(하지만 활용도는 상당히 높다.)

좋아 모든 지식을 습득했으니 순환큐를 만들어보자

#include<iostream>

using namespace std;

typedef int ElementType;

class CircularQueue

{

private:

typedef struct tagNode

{

ElementType data;

} Node;

unsigned int front;

unsigned int rear;

unsigned int capacity;

Node* NodeArrayEntry;

public:

CircularQueue() //basic capacity : 10

{

front = 0;

rear = 0;

capacity = 10;

NodeArrayEntry = new Node[capacity+1];

}

CircularQueue(unsigned int capacity)

{

front = 0;

rear = 0;

this->capacity = capacity;

this->NodeArrayEntry = new Node[capacity+1];

}

//IsFull()과 IsEmpty()는 그림을 그려가며 확인해보면 이해가 쉽다.

bool IsFull()

{

if( front < rear)

return ((rear-front) == capacity) ? true : false;

else

return ( (rear+1) == front ) ? true : false;

}

bool IsEmpty()

{

return front == rear ? true : false;

}

bool Enqueue(ElementType enqueueData)

{

if(IsFull())

return false;

if(rear == capacity)

{

NodeArrayEntry[rear].data = enqueueData;

rear = 0;

}

else

NodeArrayEntry[rear++].data = enqueueData;

return true;

}

ElementType Dequeue()

{

//여기서는 비어있는데 디큐를 하면 그냥 강제종료시켜버렸지만, 필요에 따라 에러처리를 해보자

if(IsEmpty())

{

perror("Queue is empty now. can't dequeue from this CircularQueue\n");

exit(0);

}

unsigned int position=front;

if(front == capacity)

{

front = 0;

}

else

front++;

return NodeArrayEntry[position].data;

}

int getSize()

{

return capacity;

}

//이건 순환큐의 내용과는 그닥 상관없는 함수다

bool Resizing(unsigned int capacity)

{

char keyinput;

cout<<" [Worning!][CQ resizing will delete all data in queue.\n\tProcess anyway? (y/n)]";

cin>>keyinput;

if(keyinput == 'y')

{

front = 0;

rear = 0;

this->capacity = capacity;

delete [] NodeArrayEntry;

NodeArrayEntry = new Node[capacity+1];

return true;

}

else

return false;

}

~CircularQueue()

{

delete [] NodeArrayEntry;

}

}; //end of class CircularQueue

int main()

{

CircularQueue CQ;

ElementType tmpData =0;

unsigned int queuesize=CQ.getSize();

int switchVa = 0;

while(1)

{

cout<<"----------CircularQueue Test-----------\n"

<<"1. insert data to CQ\n"

<<"2. pick out from CQ\n"

<<"3. How much CQ's size\n"

<<"4. Resize\n"

<<"5. quit."<<endl;

cout<<"Choose one :";

cin>>switchVa;

switch(switchVa)

{

case 1:

cout<<" [Enqueue][write your data wanted to insert:]"; cin>>tmpData;

if(!CQ.Enqueue(tmpData))

cout<<" [Enqueue][CQ is Full now]"<<endl;

else

cout<<" [Enqueue][insert successfully]"<<endl;

break;

case 2:

cout<<" [Dequeue][data:]"<<CQ.Dequeue()<<endl;

break;

case 3:

cout<<" [Capacity][CQ size : "<<CQ.getSize()<<"]"<<endl;

break;

case 4:

unsigned int tmpCapacity;

cout<<" [Resizing][How much capacity you want? :]";cin>>tmpCapacity;

if( !CQ.Resizing(tmpCapacity))

{

cout<<" [Resizing][resizing failure]"<<endl;

break;

}

cout<<" [Resizing][success to resizing]"<<endl;

break;

case 5:

cout<<"Thanks for using my program"<<endl;

return 0;

default:

cout<<"plz choose number between 1 to 4"<<endl;

break;

}

}

return 0;

}

코드만 떡 붙여놨지만, 어렵지 않게 이해할 수 있을것이다.

스택에도 노드들을 엮어, 리스트처럼 관리하기도 했었다.

마찬가지로 큐 또한 링크드리스트와 혼합해서 링크드큐를 만들기도 하는데 링크드큐는 직관적으로 이해가 되기때문에 간단하게 만들 수 있다.

게다가 링크드큐는 '공간이 가득찼다'는 개념이 없기때문에 확인해줘야 할 것들도 많이 줄어든다.

(그만큼 만들기 편하다)

하지만! 노드의 생성에서 계속 힙영역을 잡아줘야 하고, 데이터를 제거할때는 힙영역또한 제거해줘야하는 등 비용적인 측면에서 순환큐보다 구리다.

큐를 사용하려는 목적에 맞게 순환큐 or 링크드 큐를 적절히 사용해야 할 필요가 있다.

아, 순환큐가 아닌 선형큐(Linear Queue)에서 문제점이 제거연산을 할수록 큐의 공간이 줄어든다였는데,

이 문제를 순환큐로 구성해서 해결하지 않고,

큐의 공간이 **% 이하로 떨어졌을 때 큐 안의 데이터들을 배열요소의 처음부분부터 앞당겨서 다시 쓰도록 할 수도 있다.

                            전단                  후단 

                              ↓                       ↓                                                              

[     ][     ][     ][  D ][  D ][  D ][     ][     ][     ][     ]

예를들어 위 상황에서 아래와 같이 됬을 때,

 

                                            전단                           후단 

                                              ↓                                ↓                                                              

[     ][     ][     ][     ][     ][  D ][  D ][  D ][  D ][     ]

공간이 부족하니 데이터들을 쭉 밀어내는 거다.

   전단                        후단 

    ↓                              ↓                                                              

[  D ][  D ][  D ][  D ][     ][     ][     ][     ][     ][     ] 

 

이런 방법도 있으니 상황에 따라 조금 더 편리하고 효율적인 큐를 사용하면 되겠다.