[자료구조] 링크드 리스트(Linked List)를 기반으로 스택(Stack) 구현하기

링크드 리스트를 기반으로 스택 구현하기

스택 구현에서 링크드 리스트가 배열보다 좋은 점은 두 자료구조의 근본적인 차이인 용량에 제한을 두지 않아도 된다는 점입니다. 스택의 크기를 필요할 때 줄일수도, 늘릴수도 있는것이죠.

하지만 인덱스를 활용하여 노드에 접근할 수 없습니다. 따라서 노드는 자신의 위에 위치하는 노드에 대한 포인터를 갖고 있어야 합니다.

 

 

-각 층을 구성할 노드와 스택의 구조체

typedef struct tagNode{
    char* Data;
    struct tagNode* NextNode;
} Node;

 

문자열이 저장된 자료형의 포인터와 위의 노드를 가리키는 포인터를 갖습니다.

이는 Heap에 저장되어야 합니다.

---

typedef struct tagLinkedListStack{
    Node* List;
    Node* Top;
} LinkedListStack;

 

List 포인터는 데이터를 담는 링크드 리스트를 가리키고 Top포인터는 이 링크드 리스트의 Tail을 가리킵니다.

 

 

-스택의 생성과 소멸

void LLS_CreateStack(LinkedListStack** Stack){  //스택 생성
    (*Stack) = (LinkedListStack*)malloc(sizeof(LinkedListStack)); //스택을 Heap에 생성

    (*Stack)->List = NULL;
    (*Stack)->Top = NULL;
}

 

배열 기반의 스택구현과 다르게 용량을 결정짓는 매개 변수를 필요로 하지 않습니다. 즉 링크드 기반이므로 앞서 말한바와 같이 용량 제한에서 자유로워진 것이죠.

---

void LLS_DestroyStack(LinkedListStack* Stack){  //스택 소멸
    while(!LLS_IsEmpty(Stack)){
        Node* Popped = LLS_Pop(Stack);
        LLS_DestroyNode(Popped);
    }

    free(Stack);
}

 

스택의 각 노드를 먼저 제거하고 마지막으로 Heap에서 구조체를 free()함수로 해제 시켜줍니다.

 

 

-노드의 생성과 소멸

데이터값을 바로 매개변수로 받고 스택에 값을 저장했던 배열기반과 다르게 다소 신경 쓸 부분이 있습니다. 또한 이번 링크드 리스트 기반 스택은 데이터를 문자열로 받을것이기 때문에 Heap에 문자열을 저장할 공간도 같이 할당해 줄 것입니다.

Node* LLS_CreateNode(char* NewData){    //노드 생성
    Node* NewNode = (Node*)malloc(sizeof(Node));
    NewNode->Data = (char*)malloc(strlen(NewData) + 1);
    
    strcpy(NewNode->Data, NewData);
    
    NewNode->NextNode = NULL;
    
    return NewNode;

---

void LLS_DestroyNode(Node* _Node){
    free(_Node->Data);
    free(_Node);
}

 

노드를 소멸할 때도 잊지말고 문자열 공간 또한 해제해줍니다.

 

 

-노드 삽입 연산

void LLS_Push(LinkedListStack* Stack, Node* NewNode){
    if(Stack->List == NULL){
        Stack->List = NewNode;
    }
    else{
        Stack->Top->NextNode = NewNode;
    }
    
    Stack->Top = NewNode;
}

 

기존 링크드 리스트와 다른점은 Top노드를 따로 신경써주기만 하면 되겠네요.

 

 

-노드 제거 연산

Node* LLS_Pop(LinkedListStack* Stack){
    Node* TopNode = Stack->Top;
    
    if(Stack->List == Stack->Top){
        Stack->List = NULL;
        Stack->Top = NULL;
    }
    else{
        Node* CurrentTop = Stack->List;
        while(CurrentTop != NULL && CurrentTop->NextNode != Stack->Top){
            CurrentTop = CurrentTop->NextNode;
        }
        
        Stack->Top = CurrentTop;
        Stack->Top->NextNode = NULL;
    }
    
    return TopNode;
}

 

마찬가지로 데이터값과 다음 노드를 가리키는 포인터를 관리해줍니다.

 

 

-그 외 연산

• 최상위 노드(Top) 반환

Node* LLS_Top(LinkedListStack* Stack){
    return Stack->Top;
}

 

• 스택 크기(Size) 반환

ElementType LLS_GetSize(LinkedListStack* Stack){
    int count = 0;
    Node* Current = Stack->List;
    
    while(Current != NULL){
        Current = Current->NextNode;
        count++;
    }
    
    return count;
}

 

• 스택이 비어있는지 bool값 반환

bool LLS_IsEmpty(LinkedListStack* Stack){
    if(Stack->List == NULL) return true;
    else return false;
}