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

Queue (동적할당, 연결리스트 구현)

동적할당 방식

[큐] Queue란? 에서 배열(정적할당 방식)로 Queue를 구현하였다.

동적할당 방식은 초기에 메모리 공간을 정해두지 않고, 필요할 때마다 할당하는 방식이다.

- 데이터 삽입, 삭제하는 경우 O(1)에 가능하다.

- (최대 메모리 공간 내에서) 리스트 크기 제한이 없다.

- 인덱스를 통한 임의 접근(random access)이 어렵다

   따라서 특정한 원소를 탐색하는 경우 최대 O(N) 의 시간이 필요할 수 있다

- 일반적으로 자기 참조 구조체를 이용하여 구현한다.

 

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

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

Queue 특징

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

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

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

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

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

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

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

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

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

▶ [[큐] Queue란?

[큐] Queue란?

Queue 초기 상태 (Empty)

Node* head = new Node(0, NULL);
Node* tail = head;

　

Queue 원소 삽입 (Enqueue)

▶ Enqueue"7"

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

// 생성자 X
void push(int nd){     
    Node* tmp= newNode;
    tmp -> data = nd;
    tmp -> next = NULL;
    tail -> next = tmp;
    tail = tail -> next;
}

// 생성자 O
void push(int nd){     
    tail -> next = newNode(nd, NULL);
    tail = tail -> next;
}

 

▶ Enqueue "5"

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

 

Queue 삭제 

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

① head 가 가리키는 노드를 임시 포인터 tmp 가 가리키도록 하고

② head 는 head -> next 를 따라 다음 노드를 가리키도록 한다

③ tmp -> next = NULL 로 연결을 끊는다

④ 이제 tmp 가 가리키는 노드를 삭제한다

 

결과적으로 head가 가리키는 노드는 다시 더미노드가 된다.

즉, head가 가리키는 노드는 더미노드

 

활용

멤버 함수 형태

void pop(){
    head -> erase(head);
}

void erase (Node*&ref){
    ref = next;
    next = NULL;
    delete this;
}

　

클래스와 함수 (C++)

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

　

동적할당 단점

- new, delete (혹은 malloc, calloc)에 따른 할당 시간 비용 (Overhead)

- 메모리 단편화(fragmentation)에 의한 누수(Leakage)

- 할당 실패 시 프로그램이 Holding 상태

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

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

 

Reference

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

- [큐] Queue란?

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