Facebook Joinc 그룹
Joinc QA 사이트
Tweet
joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.
Tweet
joinc는 Firefox와 chrome에서 테스트 했습니다. IE에서는 테이블이 깨지거나 이미지가 보이지 않을 수 있습니다. 특히 구글 Docs이미지의 경우 엑박처리될 수 있습니다.
HTML 변환문서
<!DOCTYPE article PUBLIC "-//OASIS//DTD DocBook V4.1//EN">
<article lang="ko">
<!-- -->
<!-- 문서 정보 -->
<!-- -->
<articleinfo>
<title>큐 자료추상</title>
<author>
<surname>윤 상배</surname>
<affiliation>
<address>
<email>dreamyun@yahoo.co.kr</email>
</address>
</affiliation>
</author>
<revhistory>
<revision>
<revnumber>0.8</revnumber>
<date>2003년 3월 21일 20시</date>
<revremark>최초 문서작성</revremark>
</revision>
</revhistory>
</articleinfo>
<!-- -->
<!-- 섹션 시작 -->
<!-- -->
<section>
<title>소개</title>
<para>
지난번의 Stack 자료구조에 이어서 이번에는
Queue(이하 큐) 자료구조에 큐 자료추상 에 대해서
알아보도록 하겠다. 또다른 전혀다른 자료구조라고
볼수 있는 Stack(이하 스택)과 자주 비교될 것이다.
스택에 대한 내용은 <ulink url=http://www.joinc.co.kr/modules.php?name=News&file=article&sid=108>자료구조 2 - stack</ulink>을 참고하기
바란다.
</para>
</section>
<section>
<title>큐 데이타 추상</title>
<section>
<title>큐에 대해서</title>
<para>
큐는 지난번에 배웠던 Stack 과 종종 비교되곤 한다.
Stack 이 후입선출(LILO - Last In Last Out)의 자료 입출력
구조를 가지는것에 비해,
큐는 선입선출(FIFO - First In First Out)의 자료 구조를 가진다.
한마디로 가장 먼저 입력된 데이타가 가장 먼저 출력되는 자료구조다.
<figure>
<title>Queue(큐) 자료구조에서의 입력/출력 </title>
<graphic fileref=http://www.joinc.co.kr/albums/album01/acc.gif>
</figure>
위의 그림을 보면 큐자료구조를 쉽게 이해할수 있을것이다.
</para>
<para>
이러한 큐 자료구조는 보통 우리의 생활에서는 매우 일상적인 자료구조
이다. 큐 자료구조의 형태를 가장 흔히 볼수 있는게 "줄서기" 가
될것이다. 은행 창구에서 줄을 서거나, 버스를 기다리기 위해서
줄을 설경우 가장 먼저 줄을 선 사람이 가장 먼저, 은행업무를
처리하거나, 버스를 타게 된다(새치기 하는 경우는 생각하지 말자).
</para>
<para>
이런 식으로 실제 우리가 사회생활을 하면서 받게 되는 대부분의
서비스들은 큐 자료구조 형태로 이루어지게 된다.
</para>
<para>
그렇다면 스택과 비교해서 컴퓨터 프로그래밍시에 자주 사용되는
자료구조는 무엇이라고 생각되는가 ?
물론 큐도 자주 사용되긴 하지만, 재귀적 호출과의 연광성 때문에
보통은 스택이 더욱 유용하게 사용된다.
바이너리 트리를 순환하고자 할때, 혹은
서브디렉토리를 포함한 디렉토리를 검색하고자 하는 경우
보통 스택을 사용하게 된다.
</para>
<para>
스택의 또다른 사용처라면 인터럽트가 걸렸을경우가
될것이다. 간단히 예를 들어서
우리가 청소를 하고 있는데, 전화벨이 울리면(인터렙트가 발생)
청소를 중단하고 전화를 받게 된다. 전화를 받는 도중에
초인종이 울리면 우리는 상대방에게 잠시 기달려 달라고 하고
누가 방문했는지 확인한다음 다시 전화를 받아서 통화를 끝내고
다시 청소를 하게 된다.
사건의 발생순서로 보자면 청소가 가장먼저고 초인종울린게
가장 나중엔데, 처리 순서는 초인종에 대한 처리가 가장 먼저이고 다음이
전화 다음이 청소가 된다. 매우 전형적인 스택의 예이다.
</para>
<para>
이와 비슷하게 프로그래밍에서의 인터럽트 처리 역시
스택 구조를 가지게 된다. A 라는 작업을 하고 있는데,
만약 시그널을 통한 인터럽트가 발생되면, 시그널 핸들러가
호출되고, 핸들러가 종료된다음 다시 A로 돌아가서 작업을 하는 식이다.
엄밀히 따지자면 프로그래밍 자체가 스택의 구조를 가진다.
최초에 main 함수를 호출하고 도중에 A 라는 함수를 호출하게 되면
A 함수로 작업을 들어가게 된다. 다시 A 에서 B 라는 함수를 호출하면
B 함수로 들어가서 작업을 하게 되고, 리턴하면 다시 A 로, A에서 리턴하면
다시 main 함수로 들어가는 전형적인 스택자료구조의 형태를 지닌다.
</para>
<para>
그렇다면 우리가 관심있어하는 큐의 경우 어떤때 유용하게
사용할수 있을지 생각해보자. 가장 간단하게 생각할수 있는 것은
<emphasis>데이타의 흐름</emphasis>을 처리하는 경우가 될것이다. 데이타는 먼저들어온걸
먼저 처리하는게 일반적인 순서이다. 이런 데이타의 흐름을 처리하기
위해서 큐를 응용하는 가장 대표적인 경우가 바로 버퍼(Buffer)의 사용이
될것이며, 거의 100% 큐는 버퍼를 구현하는데 사용되는 자료구조라고 봐도 된다.
</para>
<para>
프로그래밍 하면서 "큐"를 써야 한다라고 하면, 이말은 곧 "버퍼"를 사용해야
한다는 말로 통할정도로 큐와 버퍼는 뗄래야 뗄수 없는 관계이다.
</para>
</section>
<section>
<title>큐의 구현</title>
<para>
위에서 말했듯이 큐는 버퍼를 만들때 가장 흔하게 사용되는 자료구조이다.
프로그래밍시 버퍼가 사용되는 경우는 보통 완충영역을 두어서,
프로그램의 안정성을 높이기 위한 용도 이다.
</para>
<para>
예를 들어 네트웍에서 어떤 메시지를 받아서 처리하는 프로그램이 있다고
가정해 보자. 이런 프로그램은 보통 네트웍에서 메시지를 받아들이는 부분과
메시지를 처리하는 부분으로 나뉘게 될것이다.
그런데 둘사이에 메시지를 처리할수 있는 양에 있어서 차이가 있을수 있을 것이다.
메시지를 처리하는 루틴이 초당 1000건의 메시지를 처리할수 있다고 가정을 하자.
이 1000건의 메시지를 처리하는 능력은 매우 뛰어나다고 할수 있지만,
때때로 네트웍을 통해서 1000건 이상의 메시지가 전달될때도 있을것이다.
이럴경우 이 메시지 처리 프로그램뿐만 아니라, 이 프로그램이 속해있는
시스템모두에게 영향을 미게 될것이다.
이럴경우 큐를 이용해서 버퍼를 만들게 되면, 1000건 이상의 많은 데이타가
발생할때는 버퍼에 쌓이다가, 메시지가 적게 들어오면 버퍼에 있는 데이타를
모두 처리해 낼수 있을것이다. 이렇게 됨으로써 하나의 프로그램의 성능저하로
인해서 전체 시스템의 성능이 저하되는 문제를 어느정도 해결가능할 것이다.
</para>
<section>
<title>큐 데이타추상을 위해서 기술되어야할 해동</title>
<para>
행동대신 메서드라고 해도 관계는 없다. 데이타 추상은
프로그래머(클래스 사용자)에게 내부구현은 숨기는걸 기본원칙으로
한다. 그럼으로 가능한한 프로그래머가 내부구현에 신경쓸일이 없도록
필요한 메서드를 제공해줄수 있어야 한다.
다음은 큐 데이타추상을 위해서 기본적으로 제공되어야할 메서드와
각 메서드가 숨기고있는(추상화하고 있는) 구현들에 대한 설명이다.
<table>
<title>큐 데이타 추상을 위한 제공 메서드</title>
<tgroup cols=2>
<tbody>
<row>
<entry>Queue</entry>
<entry>생성자로 지정된 크기만큼 큐공간을 할당한다</entry>
</row>
<row>
<entry>~Queue</entry>
<entry>소멸자로 할당된 큐공간을 해제(free)한다.</entry>
</row>
<row>
<entry>push_back</entry>
<entry>데이타를 입력한다. 만약 capacity 를 초과하게 될경우 realloc 한다.</entry>
</row>
<row>
<entry>pop</entry>
<entry>가장 최근데이타를 가져오고, 가져온데이타는 큐에서 삭제한다.</entry>
</row>
<row>
<entry>size</entry>
<entry>현재 큐에 저장된 데이타의 갯수를 얻어낸다.</entry>
</row>
<row>
<entry>capacity</entry>
<entry>현재 큐를 위해 할당된 용량(메모리크기)를 얻어낸다.</entry>
</row>
<row>
<entry>clear</entry>
<entry>큐에 있는 모든 원소를 삭제한다.</entry>
</row>
</tbody>
</tgroup>
</table>
</para>
</section>
<section>
<title>구현 예 - circular queue</title>
<para>
큐를 구현하는 가장 일반적인 방법은 스택과 마찬가지로 배열을 이용하는
방법이다. 그러나 단순배열로 할경우 배열의 크기가 지정되어 있는 상태에서
데이타가 계속 추가되게 되면 어느 시점에서 overflow 가 발생하게 됨으로
데이타가 배열의 크기를 초과하게 되면, 초과된 데이타는 0번째 배열로 들어가게
해야 한다. 이러한 구조가 환형구조와 같다고 해서 보통 환형큐(circular queue)
라고 한다.
</para>
<para>
우리는 circular queue 를 이용해수 큐자료추상(ADT)를 만들고 이것을
테스트 할것이다.
</para>
<para>
예제코드는 template 를 이용해서 작성될것이다.
template 를 이용함으로써, 자료형에 관계없이 유연한 자료구조의
구축이 가능할것이다.
</para>
<para>
<emphasis>예제 : circular_queue.c</emphasis>
<screen>
#include <iostream>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
using namespace std;
template <typename T1>
class Queue
{
private:
int MaxSize;
int DataIndex;
int QueueSize;
T1 *Array;
int PushNum;
public:
// 생성자로써 디폴트 아규먼트로
// 큐의 사이즈를 지정했다.
// 아규먼트로 넘어온 크기만큼 Array 의 크기를
// 할당하고 기타 멤버변수들의 값을 적당히 초기화 한다. Queue(int size=40)
{
MaxSize = size;
Array = (T1 *)malloc(sizeof(T1)*MaxSize);
QueueSize = 0;
DataIndex = 0;
PushNum = 0;
}
// 소멸자 자원을 해제한다.
~Queue()
{
free(Array);
}
// Array에 원소를 입력한다.
// 만약에 Array 의 크기를 초과해서 원소가 들어갈경우
// MaxSize*2 크기만큼 메모리의 크기를 재할당한다.
void push_back(T1 x)
{
if (QueueSize > MaxSize - 1)
{
MaxSize *= 2;
if ((Array = (T1 *)realloc(Array, sizeof(T1)*MaxSize)) == NULL)
{
perror("realloc error:");
exit(0);
}
cout << "Realloc OK" << endl;
}
Array[PushNum%MaxSize] = x;
PushNum++;
QueueSize++;
}
// 데이타를 꺼낸다.
T1 pop()
{
QueueSize--;
DataIndex++;
return Array[(DataIndex-1)%MaxSize];
}
// 큐에 있는 데이타의 갯수를 얻어온다.
int size()
{
return QueueSize;
}
// 큐의 크기를 얻어온다.
int capacity()
{
return MaxSize;
}
// 원소를 삭제한다.
// 실제 데이타를 free 시키지는 않고, Index
// 값들을 조정해서 삭제한것 처럼 보이게 한다.
void clear()
{
QueueSize = 0;
DataIndex = 0;
PushNum = 0;
}
};
int main()
{
Queue<char *> myqueue(4);
cout << "Queue capacity " << myqueue.capacity() << endl;
myqueue.push_back("hello 1");
myqueue.push_back("hello 2");
myqueue.push_back("hello 3");
myqueue.push_back("hello 4");
myqueue.push_back("hello 5");
myqueue.push_back("hello 6");
int size = myqueue.size();
for (int i = 0; i < size; i++)
cout << myqueue.pop() << endl;
myqueue.push_back("hello 1");
myqueue.push_back("hello 2");
myqueue.push_back("hello 3");
myqueue.push_back("hello 4");
for (int i = 0; i < size; i++)
cout << myqueue.pop() << endl;
cout << "Queue capacity " << myqueue.capacity() << endl;
myqueue.clear();
cout << "Queue Size " << myqueue.size() << endl;
}
</screen>
예제는 주석만으로도 충분히 이해가 가능할 것이다.
실제 STL 의 deque 와 매우 비슷하게 구현되었음을 알수 있다.
</para>
</section>
<section>
<title>구현 예 - linked list</title>
<para>
queue 를 구현할수 있는 또다른 방법은 linked list 를 이용하는 방법으로
배열로 구현되는 circular queue 에 비해서 좀더 까다롭다. 또한
pop 을 할때 가져온 데이타의 경우 자원해제(free)를 해줘야하고,
데이타를 push_back 할경우 새로운 공간을 만들어야 하기 때문에 위의 circular
queue 에 비해서 좀더 비효율적이 될경우가 많다.
나중에 linked list 에서 자세하게 다룰 예정임으로
여기에서는 linked list 로 구현하는 예제는 다루지 않을것이다.
개인적으로 구현해보고 싶다면,
<ulink url=http://www.joinc.co.kr/modules.php?name=News&file=article&sid=89>동적 메모리할당</ulink>을 참고해서 구현해보기 바란다.
</para>
</section>
</section>
</section>
<section>
<title>결론</title>
<para>
이상 간단하게 큐자료추상에 대해서 알아보았다.
아마 스택자료추상과 마찬가지로 매우 평이한 수준의 글이였을것으로 생각된다.
다음 강좌는 linked list 와 이의 응용에 대한내용을 다루게 될것이다.
</para>
</section>
</article>