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

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

[스택] Stack 이란? 에서 배열(정적할당 방식)로 Stack을 구현하였다.

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

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

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

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

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

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

 

▶ 자세한 내용 [List] 순차 리스트(정적 배열) & 연결 리스트(동적할당) 비교 참고

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

 

초기 스택 상태 (Empty)

- head가 참조하는 노드 = 최근에 삽입한 노드 의미 

  (스택에서 "top"의 역할이라고 보면된다.)

- Data가 추가된다면 "head" 위치에 할당받아 연결된다.

Node *head = NULL;

　

스택 원소 삽입 (Push)

▶ push "7"

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

void push(int val){     
    Node* newNode = newNode();
    newNode -> data = val; // 7
    newNode -> next = head;
    head = newNode;
}

 

▶ push "5" 

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

- LIFO(Last In First Out) 구조인 것을 확인할 수 있다.

 

 

스택 원소 삭제(Pop)

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

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

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

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

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

 

활용

▶ 멤버 함수 형태로 적용

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

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

　

▶ 생성자, 소멸자, 삭제 멤버함수 사용

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

　

동적할당 단점

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

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

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

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

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

Reference

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

- [스택] Stack 이란?  

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