linked list, Queue

Inter Process Communication (IPC)을 제대로 하려면
  > Queue라는 자료구조

Software에서 사용하는 Data > Queue 주로 이용.
 ( Stack : 메모리 주소 ).

Stack 과 달리 <> 먼저 넣은 놈 먼저 나옴
    >  FIFO : 줄세우기

 >  대기행렬 > 일종의 Buffer
- Stack : push, pop <> Queue : put, get

Stack

push (0x1); // 저장하는곳의 주소가 높은곳에서 작은곳임
push (0x2);  // push (0x2) > 0x2 라는 주소를 저장하는 값임
push (0x3); // 주의!

pop (); /* 0x3이 나옵니다. */
pop (); /* 0x2가 나옵니다. */
pop (); /* 0x1이 나옵니다. */

<>

Queue

put (0x1);
put (0x2);
put (0x3);

get () ; /* 0x1이 나옵니다. */
get () ; /* 0x2이 나옵니다. */
get () ; /* 0x3이 나옵니다. */

 > Queue이용 > 순서대로 처리가능
  > 배열,  Linked List 등으로 이용

#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

 Linked List 

  : 서로 다른 데이터 공간에 있어도 서로 Pointer 연결을 통해서 연결되는 자료 구조
    > Pointer 연결 > 논리적인 순서를 줄 수 있음.

 >> 자료처리 > insert, delete가 아주 편리

Double Linked List

A tail > B

B Tail > C

<>

 B head > A

C head > B 

 

> Headnode에서 논리적 순서를 가지고 있음

   .( 순서를 줄 수 있다 ~=  Queue )

 

 

 B tail > E head,

 C head >E tail

insert 를 이용해 간단하게 자료구조(구조체) 추가 가능

<> Delete

 E 제거 후,

B, C의 head, tail을 다시 맞춰주면 원상복구

 

RTOS Kernel에 많이 이용

 > Linked List를 이용한 Queue의 구현 

 

Queue > Linked List를 이용해서 구현

 ex)

A-B-C 

 > 계속 뒤쪽에 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를 만들고/분석 할 때 편리