임베디드 레시피

Egloos | Log-in





Linked List와 Queue

우리 Stack과 Heap등을 살펴 보았듯이, Inter Process Communication을 제대로 하려면, Queue라는 자료구조의 개념을 잘 알아야 해요. 일단 Queue는 Stack과 달리, 먼저 넣은 놈이 꺼내면 먼저 나와요. Stack은 나중에 넣은 넘이 꺼내면 먼저 나오죠. 그래서 Queue라는 건 줄세우기인데요,  보통 FIFO라고 불려요. Software에서 사용하는 Data들은 대부분 이런 Queue라는 걸 이용해서 처리를 한답니다. 먼저 들어온 넘을 먼저 처리하는 게 순리상 정상인 게죠. Stack이 이상한 거에요. ㅋ 보통 Queue라는 건 대기행렬을 의미하는데요, 줄을 세우는 거라고 보시면 되요. 일종의 Buffer라는 의미인데요, 처리 할 녀석들을 줄 세워 놓고서 하나씩 꺼내서 처리하는 거라고 보시면 되지요. 뭐 구현방법에는 Ring buffer니 뭐니 해서 많이 있는데, 그건 자료구조 책들에게 넘기고요. IPC에 이용이 많이 되니까, 꼭 구현을 잘 찾아봐 두세요. 뭐 당연하겠지만, 이런 식인 거에요. - Stack에서는 push와 pop이라는 용어를 썼는데, Queue에서는 put과 get이라는 용어를 써요 -
 
Stack에서는
 
push (0x1);
push (0x2);
push (0x3);
 
pop (); /* 0x3이 나옵니다. */
pop (); /* 0x2가 나옵니다. */
pop (); /* 0x1이 나옵니다. */
 
이런식이었지만,
 
Queue에서는
 
put (0x1);
put (0x2);
put (0x3);
 
get () ; /* 0x1이 나옵니다. */
get () ; /* 0x2이 나옵니다. */
get () ; /* 0x3이 나옵니다. */
 
이런 식으로 먼저 들어간 넘이 먼저 나오죠. Queue를 잘 사용하는 방법에는 여러 가지가 있겠지만요, 요걸 잘 이용하면 제일 먼저 넣은 넘부터 시작해서 제일 마지막에 넣은 넘까지 순서대로 처리가능 하다는 거에욧. Queue를 구현하는 방법은 엄청나게 많아요. 배열을 이용할 수도 있고요, Linked List를 이용할 수도 있고요, 여러 가지 방법이 많은데, 여하튼 위와 같은 식으로 FIFO로 동작만 잘 하면 됩니다. ㅋ . 일단 배열을 이용한 Queue의 구현만 슬쩍 보고 넘어가시죠. 여기에서 front나, rear가 배열의 크기를 넘어 셨을 때의 예외 처리는 구찮아서 표시하지 않았으니까, 이 Code에 Bug가 있다고 항의 하시면 곤란-,.- 해요.
 
#define MAX 50

int Queue[MAX];    /* Queue */
int front = 0;
int rear = 0;      /* Front와 Rear */
void Put(int);        /* Data Put */
int Get();             /* Data Delete */
 
void main ()
{
 
 Put(5);
 Put(10);
 Put(15);
 Put(20);
 Put(30);
 
 /* 여기에서의 Queue안에 남은 결과는 5, 10, 15, 20, 30 */
 Checkqueue();
 
 ret = Get();   /* ret = 5 */
 ret = Get();   /* ret = 10 */
 ret = Get();   /* ret = 15 */
 
/* 여기에서의 Queue안에 남은 결과는 20, 30 */ 
 Checkqueue();

 
 ret = Get();   /* ret = 20 */
 ret = Get();   /* ret = 30 */
 
/* 여기에서의 Queue안에 결과는 아무것도 남지 않음 */
  Checkqueue();

}

void Put (int data)
{
 Queue[rear++] = data;
}

int Get ()
{
 int ret;
 ret = Queue[Front++];
 return ret;
}
 
void CheckQueue ()
{
 int i;
 for(i = Front ; i < Rear ; i++)
  printf("%2d - ", Queue[i]);
}
 
여기에서 볼 수 있듯이, 이런 Queue는 front와 rear를 통해서 Slide Window 형식으로 Valid한 Data를 모아 놓고서 Data를 넣을 때는 rear쪽에 Data를 뺄 때는 front쪽에서 장난을 치는 형식이에요. 이런 건 overflow가 날 수 있으니까, 무한대로 쓰고 싶으면 Ring Buffer를 이용한 Queue도 많이 쓰는데, 그건 자료구조 책들 뒤져 보시면 엄청 나오니까, 일단 생략 하고요.
 
그리고, Linked List 요거도 잘 알아야 되는데, Linked List는 서로 다른 데이터 공간에 있어도 서로 Pointer 연결을 통해서 연결되는 자료 구조인데요, 이걸 이용하면 Pointer 연결을 통해서, 논리적인 순서를 줄 수 있는 장점이 있어요. Double Linked List를 예를 들면요,
 
 
 
A의 tail은 B를 가리키고요, B의 Tail은 C를 가리키고요. 이런 식으로 주르르륵 늘어 놓을 수 있고요, 역시나 반대로 B의 head는 A를 가리키고, C의 head는 B를 가리키는 형식으로 되어 있지요. 이렇게 되면 Headnode에서 주르륵 논리적 순서를 가지고 있겠죠. 순서를 줄 수 있다는 건 Queue랑 비슷한데요, Linked List는 자료를 처리할 때, insert나 delete가 아주 편리하답니다.
 
 
보시다시피 원래 C 가리키던 B tail E head, 그리고 원래 B 가리키던 C head E 연결해 주시고, 나머지 연결은 순서에 맞게 조정해 주시면,

 

 
요렇게 간편하게 3분 요리로 삽입이 되는 거죠. 당연히 빼는 건 이것의 반대로 E를 빼낸 후에, B와 C의 head와 tail을 다시 맞춰주면 원상복구 되지요. 이런 Linked List는, 여러 가지 기능에 이용되는데, 그 예는 차차 보기로 하시지요. 한가지만 더 덧붙이자면, 이런 Linked List를 이용한 Queue의 구현이 RTOS Kernel에 많이 이용된다는 사실이에요. Queue를 Linked List를 이용해서 구현하게 되면, A-B-C 이런 식의 Data가 있을 때, out을 하면 계속 뒤쪽에 A-B-C-D 이런 식으로 덧붙이기가 가능하고요, 한 개의 Linked List를 더 운용하면 더 아름답게 쓸 수 있는데요. Free Queue라는 걸 두어서, A-B-C-D에서 get을 하면 A가 튀어 나올 텐데, 이 녀석을 Free Queue Linked List에 넣어 두는 거죠. Queue에 뭔가 넣고 싶을 때는 무조건 Free Queue에서 하나 get을 한 후에, 실제 Queue에다가 put을 하게 되는 형태인 거죠. 요런걸 잘 알아두면 엄청 Code를 만들거나 분석 할 때 엄청 편하다니까요. 
 

by 히언 | 2009/08/06 21:57 | System비네팅 | 트랙백 | 핑백(1) | 덧글(6)

Linked at 친절한 임베디드 시스템 개발자.. at 2009/09/06 00:22

... ⓙ Linked List와 Queue ... more

Commented by 써니 at 2009/08/06 22:27
Queue의 활용 사례를 네트워크 서버를 예로 들면 참 좋은데, 시간나면 트랙백해 보겠습니다.
사소한 태클인데, 스택이 이상한 건 아니죠... ㅋㅋ 자칫 진지하게 읽으시는 분들 있을까봐.... 나름 스택이 있음으로 해서, function call 이라는게 가능한 것이니까요. 모든 함수형 프로그램 내부에서 사용되는 자료 구조 아닙니까!? 어셈블리 언어 강의할 때 스택 가르치면 다들 어리둥절 하지만 말입니다. 어쨋든 잘 읽었습니다!
Commented by 히언 at 2009/08/06 23:09
ㅎ .. 넹~ 더 좋은 예가 있으면~ 트랙백 부탁합니다. ㄳ - 설마 Stack이 이상하다는 말이 이상하게 들릴지는 상상도 못해봤심다 ㅋ. Stack의 중요성은 이미 앞에서 너무 많이 언급한 터라. ㅋ -
Commented by 써니 at 2009/08/06 23:12
히언님 블로그를 제대로 읽는 사람이라면 절대로 그런 오해 할리 없다고 봅니다. 문제는 이런 블로그 글을 무단으로 복사해다가, 네이버 지식인에 답변이라고 제공하는 사람들을 간혹 보는데요. 본 포스트 하나 달랑 복사해가면, 어린 양 하나 쯤은 오해할 수 있죠.

지식인에서 황당한 소스 해설/예제를 자주 보게 되서 노파심에 해본 소리입니다. 제가 지식인을 선호하는 건 아닌데, 간혹 지식인에서 샘플 코드/ 기술 해설 찾는 개발자들을 접한 경험이 있어 놔서요.
Commented by 히언 at 2009/08/07 21:36
넹~ ㄳㄳ 함당~!
Commented by 임베디드 개발자 at 2009/08/07 14:42
업데이트 되었네요~ 옛날 기억을 더듬으며 잘 보았습니다.^^
Commented by 히언 at 2009/08/07 21:36
완전 감사합니다!!!
※ 이 포스트는 더 이상 덧글을 남길 수 없습니다.

◀ 이전 페이지          다음 페이지 ▶