[큐] Queue (Memory Pool 방식 구현)

Queue (Memory Pool 방식 구현)

Memory Pool 방식이란?

연결리스트를 정적할당한 형태로, 순차 리스트 + (동적) 연결리스트의 장점을 합친 형태

- 필요한 만큼 미리 확보해서 사용 (재활용 하지 않으므로 공간 해제 불필요)

- 동적할당이 실제 메모리 공간에서 할당을 했다면 Memory Pool 방식은 초기에

  일정 공간을 정적할당하고, 해당 공간을 필요할 때마다 포인터로 동적으로 연결해주는 방식

▶ [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교  

[List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교

Queue 특징

- 큐는 먼저 삽입된 데이터가 먼저 삭제되는 FIFO(First In First Out)

  특성으로 한쪽에서는 삽입만 다른 한쪽에서는 삭제만 일어난다

- 두 개의 포인터 head 와 tail 을 사용한다.

  (한쪽에서는 Enqueue, 다른 한쪽에서는 Dequeue)

  삽입과 삭제 연산처리를 쉽게하기 위해 더미(dummy) 노드를 사용할 수 있다.

  (더미 노드 없이 구현하는 것도 가능하다)

    → head 가 가리키는 노드는 더미(데이터는 의미가 없음 완충 역할) 노드이다

    → tail 이 가리키는 노드는 최근에 삽입 한 노드이다

    → head 와 tail 이 같은 곳을 가리킨다면 큐가 비어있는 경우이다.

▶ [큐] Queue란?  

[큐] Queue란?

 

Queue 초기 상태 (Empty)

// C++ version
void push(int nd){     
    head= tail = buf[bCnt++].alloc(0, NULL);
}
// C version
void push(int nd){     
    buf[bCnt].data = nd;
    buf[bCnt].next = head;
    head = tail = buf + bCnt;
    bCnt++;
}

- buf[]에 Node 클래스 객체가 전역으로 준비되어 있다.

- bCnt는 buf[]에서 사용되지 않은 첫 위치를 나타내며 초기값 = 0

- head 포인터와 tail 포인터의 초기값은 NULL인데

  연산의 일반화를 위하여 사전 작업으로 dummy 노드를 할당한 후

  push 또는 pop 등의 본래 프로세스를 진행한다.

 

더미 노드 만들기

- buf[0]을 더미노드로 하기 위해 alloc() 메소드를 호출하여

  필드값에 대입하고 그 주소를 받는다

- 반환된 buf[0]의 주소를 head와 tail 포인터 변수에 저장

- buf 인덱스 bCnt를 증가시켜 다음 노드 할당을 준비한다.

 

Queue 원소 삽입 (Enqueue)

// C++ version
void push(int nd){     
    tail -> next = buf[bCnt++].alloc(nd, NULL);
    tail = tail -> next;
}

// C version
void push(int nd){     
    buf[bCnt].data = nd;
    buf[bCnt].next = head;
    tail->next= buf + bCnt;
    tail = tail -> next;
    bCnt++;
}

- 노드 생성

- 새로 만들어진 노드의 주소를 tail->next에 대입하여 큐에 추가

- tail에 새로운 노드의 주소인 tail->next를 대입하여 tail 포인터를 이동

  (tail이 참조하는 노드는 최근 삽입된 노드가 된다.)

- buf 인덱스 bCnt를 증가시켜 다음 노드 할당 준비

 

▶ Enqueue"7"

- 새로운 노드(data = 7) 추가

 

▶ Enqueue "5"

- 새로운 노드(data = 5) 추가

 

Queue 삭제 (Dequeue)

void pop(){     
    head= head->next
}

- head 포인터를 head가 참조하는 객체의 next 값으로 바꾸면 된다.

- 동적 생성한 것이 아니므로 메모리 해제 과정이 필요 없다.

  (이전 객체는 참조하는 포인터가 없으므로 삭제된 것으로 간주)

- 동적 할당에 비하여 삭제 과정이 간단

* head가 가리키는 노드가 dummy 노드 이므로 data 필드를 다룰 때 주의

　

활용

클래스와 함수 (C++)

struct Node{     
    int data;
    Node* next;
    Node*alloc(int nd, Node*nn){
        data = nd, next = nn;
        returnthis;
    }
} buf[BUFSIZE],*head, *tail;
int bCnt;

void push(int nd){     
    tail -> next = buf[bCnt++].alloc(nd, NULL);
    tail = tail -> next;
}

void pop(){
    head = head -> next;
}

 

구조체와 함수 (C)

typedef struct Node{     
    int data;
    Node* next;  
} Node;
Node buf[BUFSIZE], *head, *tail;
int bCnt;

void push(int nd){     
    buf[bCnt].data = nd
    buf[bCnt].next = NULL
    tail -> next = buf + bCnt
    tail = tail -> bCnt
}

void pop(){
    head = head -> next;
}

　

Reference

- [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교

- [큐] Queue란?

- [큐] Queue (동적할당, 연결리스트 구현)