[스택] Stack (Memory Pool 방식 구현)

Stack (Memory Pool 방식 구현)

Memory Pool 방식이란?

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

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

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

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

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

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

 

Stack 특징

스택(Stack)은 삽입(push)과 삭제(pop)이 한쪽 끝에서만 일어나는 구조

    → LIFO(Last In First Out)

▶ [스택] Stack 이란?

[스택] Stack 이란?

 

Stack 초기 상태 (Empty)

- buf[]에 Node 클래스 객체가 전역으로 준비

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

  buf[] 중에서 실제 사용된 개수를 의미한다.

- head 포인터의 초기 값 = NULL

Stack 원소 삽입 (Push)

▶ push "7" 

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

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

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

 

▶ push "5"

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

 

 

Stack 원소 삭제 (pop)

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

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

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

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

// C, C++ version
void pop(){
    head = head->next;
}

 

 

Memory pool 방식 필요성

- delete와 new 연산자가 같은 생성 소멸에 대한 비용 (시간 등)

- 구현 용이성

- PS할 때, 매번 생성하고 초기화하는 경우 효과적

    - Test Case에 따른 초기화 부담 ↓

    - 전체 초기화는 사용된 배열의 위치(bcnt)만 0으로 초기화

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

void push(int nd){     
    buf[bCnt].data = nd;
    buf[bCnt].next = head;
    head= buf + bCnt;
    bCnt++;
}

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

 

동적할당과 Memory Pool 코드 비교

- alloc()이 생성자 역할을 대신하게끔 한 것

 

Reference

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

- [스택] Stack 이란?  

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