[자료구조] 연결 리스트(linked list) 기반 스택 구현

연결(링크드) 리스트 기반 스택

---

• 노드의 경우 Data의 주소를 가리키는 참조형과, 자기 위에 쌓여 있는 노드의 주소를 가리키는 NextNode로 구성
• 스택의 용량이나 최상위 노드의 인덱스가 스택의 멤버로 존재하지 않음
• 링크드 리스트의 헤드와 테일에 대한 포인터는 필요함

 

 

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

typedef struct tagLinkedListStack {
    Node* List; // 자유 저장소에 존재하는 헤드 노드의 주소를 가리킴
    Node* Top; // 자유 저장소에 존재하는 테일 노드의 주소를 가리킴
} LinkedListStack;

* Top 포인터는 스택의 입출력이 이루어지는 최상위 노드에 대한 포인터임

    * Top 포인터가 없다면 최상위 노드를 찾는데 많은 시간이 소모됨

스택 생성/소멸 연산

• 스택 생성

void  LLS_CreateStack( LinkedListStack** Stack )
{
    //  스택을 자유저장소에 생성 
    (*Stack )       = ( LinkedListStack*)malloc(sizeof( LinkedListStack ) );
    (*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 );
}

노드 생성/소멸 연산

• 노드 생성
  • Node 구조체 할당과 Data 필드 할당을 위해 2번 malloc 함수가 호출됨

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; //  다음 노드에 대한 포인터는 NULL로 초기화 한다. 

    return NewNode;//  노드의 주소를 반환한다. 
}

• 노드 제거
  • Data 필드 해제, 노드 해제

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

노드 삽입/제거 연산

• 노드 삽입
  • 스택의 최상위 노드 Top에 새 노드를 얹도록 구현한다

void LLS_Push( LinkedListStack* Stack, Node* NewNode )
{
    if ( Stack->List == NULL ) 
    {        
        Stack->List = NewNode;
    } 
    else
    {
        //  스택의 Top에 신규 노드를 연결한다.
        Stack->Top->NextNode = NewNode;
    }

    //  스택의 Top 필드에 새 노드의 주소를 등록한다. 
    Stack->Top = NewNode;
}

• 노드 제거
  1. 현재 최상위 노드의 주소를 다른 포인터에 복사
  2. 새로운 최상위 노드의 바로 아래 노드를 찾는다
  3. LinkedListStack 구조체의 Top 필드에 새로운 최상위 노드의 주소를 등록
  4. 복사해뒀던 예전 최상위 노드의 주소를 반환

Node* LLS_Pop( LinkedListStack* Stack )
{
    //  LLS_Pop() 함수가 반환할 최상위 노드 저장 
    Node* TopNode = Stack->Top;


    if ( Stack->List == Stack->Top )
    {
        Stack->List = NULL;
        Stack->Top  = NULL;
    }
    else
    {
        // Top 아래에 있던 노드를 새로운 CurrentTop에 저장 
        Node* CurrentTop = Stack->List;
        while ( CurrentTop != NULL && CurrentTop->NextNode != Stack->Top )
        {
            CurrentTop = CurrentTop->NextNode;
        }

        // CurrentTop을 Top에 저장
        Stack->Top = CurrentTop;
        Stack->Top->NextNode = NULL;
    }

    return TopNode;
}

예제 프로그램

#include "LinkedListStack.h"

int main(void) {
    int i= 0;
    int Count = 0;
    Node* Popped;

    LinkedListStack* Stack;

    LLS_CreateStack(&Stack);

    LLS_Push( Stack, LLS_CreateNode("abc") );
    LLS_Push( Stack, LLS_CreateNode("def") );
    LLS_Push( Stack, LLS_CreateNode("efg") );
    LLS_Push( Stack, LLS_CreateNode("hij") );

    Count = LLS_GetSize(Stack);
    printf( "Size: %d, Top: %s\n\n", 
        Count, LLS_Top(Stack)->Data );

    for ( i=0; i<Count; i++ )
    {
        if ( LLS_IsEmpty(Stack) )
            break;

        Popped = LLS_Pop( Stack );

        printf( "Popped: %s, ", Popped->Data );

        LLS_DestroyNode(Popped);

        if ( ! LLS_IsEmpty(Stack) ) 
        {
            printf( "Current Top: %s\n", LLS_Top(Stack)->Data );
        }
        else
        {
            printf( "Stack Is Empty.\n");
        }
    }

    LLS_DestroyStack(Stack);

    return 0;
}

참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)