원형 큐 (Circular Queue) 동적할당 + Memory Pool 방식

원형 큐 (Circular Queue)

원형 큐에 대한 개념이나 배열로 구현한 내용이 궁금하시다면

▶ [큐] 원형 큐 (Circular Queue)

[큐] 원형 큐 (Circular Queue)

 

구조체 형태

- 생성자, 소멸자, 삭제 멤버함수 구현

struct Node{
    int data;
    Node* next;
    Node(){ // default constructor
        data = 0, next = NULL;
    }
    Node(int num , Node* np){
        data = num;
        next = np;
    }
    ~Node(){ /// destructor
        delete next;
    }
    void erase (Node* &ref){
        ref = next;
        next = NULL;    
        delete this;
    }
};

 

초기화 

Node* head = NULL;

- 위와 같이 *head가 아무것도 가르키지 않은 상태

- 일반 큐의 tail->next가 큐의 첫 원소를 참조

   (※ 별도의 더미노드 없이 원형 큐 구현)

 

삽입

- 생성자 사용 version

void pushCirularQueue(int nd)
    if(head == NULL){
        head = new Node(nd, NULL);
        head->next = head;
    }
    else{
        head -> next = new Node(nd, head->next);
        head = head -> next;
    }
}

 

- 생성자 미사용 version

void pushCirularQueue(int nd)
    if(head == NULL){
        head = new Node;
        head->data = nd;
        head->next = head;
    }
    else{
        Node *tmp = new Node;
        tmp->data = nd;
        tmp->next = head->next;
        head = tmp;
    }
}

 

- 기존 원소가 없는 경우 (원소가 처음 삽입되는 경우)

　

 

 

- 기존 원소가 존재하며, 새로운 원소가 추가 되는 경우

 

삭제

- erase() 멤버 함수 사용하지 않는 경우

void popCirularQueue(){
    if(head->next == next){
        delete head;
        head = NULL;
    }
    else{
        Node* tmp = head->next;
        head -> next = tmp ->next;
        tmp -> next = NULL;
        delete tmp;
    }
}

 

- erase() 멤버 함수 사용하는 경우

void popCirularQueue(){
    if(head->next == head){
        head->next = NULL;
        delete head;
        head = NULL;
    }
    else{
        head->next->erase(head->next);
    }
}

 

[예시] head -> next가 참조하는 data = 2인 노드 삭제

① head->next를 삭제될 노드의 next로 바꾼다.

② 삭제될 노드의 next에 NULL을 대입하여 리스트에서 분리

③ 삭제될 노드를 delete 한다.

* 단순 원형 큐이므로 현재 노드를 삭제하면 이전노드와 다음 노드를 연결할 방법이 없다.

   따라서 head->next를 삭제하는 방법을 사용

 

전체 소스

struct Node{
    int data;
    Node* next;
    Node(){ // default constructor
        data = 0, next = NULL;
    }
    Node(int num , Node* np){
        data = num;
        next = np;
    }
    ~Node(){ /// destructor
        delete next;
    }
    void erase (Node* &ref){
        ref = next;
        next = NULL;    
        delete this;
    }
}*head;


void pushCirularQueue(int nd)
    if(head == NULL){
        head = new Node;
        head->data = nd;
        head->next = head;
    }
    else{
        Node *tmp = new Node;
        tmp->data = nd;
        tmp->next = head->next;
        head = tmp;
    }
}


void popCirularQueue(){
    if(head->next == next){
        delete head;
        head = NULL;
    }
    else{
        Node* tmp = head->next;
        head -> next = tmp ->next;
        tmp -> next = NULL;
        delete tmp;
    }
}

 

Memory Pool 방식

struct Node{
    int data;
    Node* next;
    Node *alloc(int nd, Node*np){
        data = nd, next = np;
        return this;
    }
}buf[BUFSIZE], *head;
int bcnt;


void push(int num){
    if(head = NULL){
        head = buf[bcnt++].alloc(num, NULL);
        head->next = head;
    }
    else{
        head->next = buf[bcnt++].alloc(num, head->next);
        head = head->next;
    }
}


void pop(){
    if(head == NULL) return;
    if(head->next == head) head = NULL;
    else head->next = head->next->next;
}

　

Reference

- [큐] Queue란?  

- [큐] 원형 큐 (Circular Queue)

- 우선순위 큐 (Priority Queue)

- [C++] [STL] Queue