라이크위키

링크드 리스트로 구현하는 스택

IT/알고리즘
반응형

링크드 리스트로 구현하는 스택

링크드 리스트로 구현하는 스택

링크드 리스트로 스택을 구현하면 스택의 용량에 제한을 두지 않아도 된다는 장점이 있습니다. 링크드 리스트의 구조를 잘 떠올리며 링크드 스택에 대해 알아보도록 하겠습니다.

스택과 스택의 노드 표현하기

잘 알려진 것처럼, 배열과는 달리 링크드 리스트는 인덱스로 노드에 접근할 수 없습니다 .따라서 링크드 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 가지고 있어야 합니다. 이러한 요구 사항을 반영한 노드 구조체는 다음과 같습니다.

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

배열 스택에서와는 달리 Data 필드가 char* 형으로 선언되어있습니다. 이는 다음 번에 구현할 계산기를 만들 때에 문자열을 처리하는 스택이 필요한데, 비슷한 코드를 두 번 작성할 필요 없이 이를 그대로 사용하기 위함입니다.

그런데 여기에 한 가지 문제가 있습니다. Data 필드의 자료형이 int나 double 같은 기본 자료형이라면 '값의 복사'만으로 데이터를 담을 수 있지만, char* 형은 포인터이기 때문에 문자열이 저장되어 있는 주소만을 담을 수 있어야 합니다. 또한 이 문자열은 자동 메모리가 아닌 자유 저장소에 저장되어야 합니다. 자동 메모리에 담겨있는 데이터는 우리가 필요로 하는 것과는 상관없이 컴파일러가 정해준 수명이 다하면 사라지기 때문입니다.

이번에는 링크드 리스트 스택의 구조체를 보도록 하겠습니다. 링크드 리스트 스택은 배열 기반의 스택과는 달리 '스택의 용량'이나 '최상위 노드의 인덱스'가 없습니다. 있어도 쓸 곳이 없는 것입니다. 대신 링크드 리스트(List 포인터)의 헤드와 테일(Top 포인터)에 대한 포인터가 필요합니다.

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

List 포인터는 스택이 기반하고 있는 링크드 리스트에 접근할 수 있게 하고, Top 포인터를 이용하면 4바이트를 소비하는 대신, 테일을 찾기 위해 소요되는 시간을 제거할 수 있습니다.

스택의 기본 연산 구현하기

링크드 리스트 스택의 기본 연산을 C 코드로 구현해보겠습니다. 링크드 리스트로 구현하는 방법은 배열로 하는 것보다는 난이도가 높습니다. 링크드 리스트 중에서도 싱글 링크드 리스트를 이용하여 스택을 구현하려고 합니다. 그리고 구현에 사용할 접두사는 LLS(Linked List Stack) 입니다.

스택의 생성과 소멸

먼저 해야 할 것은 스택을 자유 저장소에 생성하는 함수인 LLS_CreateStack()을 구현하는 것입니다. LLS_CreateStack() 함수는 배열 버전의 AS_CreateStack() 함수와는 달리 Stack의 용량의 결정짓는 매개 변수를 필요로 하지 않습니다. 링크드 리스트를 기반으로 하고 있기 때문에 용량의 제한에서 자유로울 수 있는 것입니다.

LLS_CreateStack() 함수가 하는 일은 다음 코드가 보여주는 것처럼 LinkedListStack 구조체를 자유 저장소에 할당하는 것 뿐입니다.

void  LLS_CreateStack( LinkedListStack** Stack )
{
    /*  스택을 자유저장소에 생성 */
    (*Stack )       = ( LinkedListStack*)malloc(sizeof( LinkedListStack ) );
    (*Stack )->List = NULL;
    (*Stack )->Top  = NULL;
}

자유 저장소에 공간을 할당하는 malloc() 함수와 free() 함수는 함께한다는 것을 잘 알 것입니다. LLS_CreateStack() 함수가 malloc() 함수를 이용하여 LinkedListStack 구조체를 자유 저장소에 할당하도록 구현하였으니 이 메모리를 해제하는 free() 함수를 호출하는 LLS_DestroyStack() 함수를 구현하면 다음과 같습니다.

void LLS_DestroyStack( LinkedListStack* Stack )
{
    while ( !LLS_IsEmpty(Stack ) )
    {
        Node* Popped = LLS_Pop( Stack );
        LLS_DestroyNode(Popped);    
    }

    /*  스택을 자유 저장소에서 해제 */
    free(Stack );
}

LLS_DestroyStack() 함수의 중요한 특징은 LinkedListStack 구조체를 자유저장소에서 해제시키는 것뿐 아니라 그에 앞서 스택 내의 모든 노드들을 제거한다는 것입니다. while 블록의 코드들의 바로 그 일을 합니다. LLS_IsEmpty() 함수는 스택이 비어있는지 여부를 점검하고, LLS_Pop() 함수는 스택의 최상위 노드를 제거합니다. 그리고 LLS_DestroyNode() 함수는 자유 저장소에 할당된 노드를 해제하는 기능을 수행합니다.

스택 노드의 생성과 소멸

링크드 리스트 스택의 노드를 생성하는 LLS_CreateNode()의 구현은 조금 복잡합니다. 앞에서 언급한 바와 같이 노드를 자유 저장소에 생성할 때에 문자열을 저장할 공간 또한 함께 생성해야 하기 때문입니다. 아래의 LLS_CreateNode() 함수 코드를 보면 malloc() 함수가 Node 구조체를 할당하기 위해 한 번, Node 구조체의 Data 필드를 위해 한 번, 모두 두 번 호출됩니다.

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;/*  노드의 주소를 반환한다. */
}

다음은 노드를 메모리에서 깨끗이 제거하는 함수인 LLS_DestroyNode() 입니다. 이 함수 내에서도 free() 함수가 두 번 호출됩니다. 한 번은 노드의 Data 필드를 자유 저장소에서 해제하기 위해서이고 나머지 한 번은 노드를 해제하기 위해서입니다.

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

삽입(Push) 연산

링크드 리스트 버전의 삽입(Push) 연산은 링크드 리스트의 추가(Append) 연산과 비슷합니다. 먼저 최상위 노드(테일)를 찾은 다음, 여기에 새 노드를 얹으면 됩니다. 이렇게 하면 새 노드가 최상위 노드가 되는데 이를 LinkedListStack 구조체의 Top 필드에 등록하는 것으로 LLS_Push() 함수의 임무는 완료됩니다.

void LLS_Push( LinkedListStack* Stack, Node* NewNode )
{
    if ( Stack->List == NULL ) 
    {        
        Stack->List = NewNode;
    } 
    else
    {
        /*  최상위 노드를 찾아 NewNode를 연결한다(쌓는다). */
        Node* OldTop = Stack->List;
        while ( OldTop->NextNode != NULL )
        {
            OldTop = OldTop->NextNode;
        }

        OldTop->NextNode = NewNode;
    }

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

제거(Pop) 연산

링크드 리스트 기반의 스택에서 제거(Pop) 연산은 다음 네 단계로 수행됩니다.

  1. 현재 최상위 노드의 주소를 다른 포인터에 복사해둔다.
  2. 새로운 최상위 노드, 즉 현재 최상위 노드의 바로 이전(아래) 노드를 찾는다.
  3. LinkedListStack 구조체의 Top 필드에 새로운 최상위 노드의 주소를 등록한다.
  4. 1에서 포인터에 저장해둔 옛 최상위 노드의 주소를 반환한다.

다음 코드는 제거 연산을 수행하는 LLS_Pop() 함수의 구현입니다.

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

    if ( Stack->List == Stack->Top )
    {
        Stack->List = NULL;
        Stack->Top  = NULL;
    }
    else
    {
        /*  새로운 최상위 노드를 스택의 Top 필드에 등록한다. */
        Node* CurrentTop = Stack->List;
        while ( CurrentTop != NULL && CurrentTop->NextNode != Stack->Top )
        {
            CurrentTop = CurrentTop->NextNode;
        }

        Stack->Top = CurrentTop;
        CurrentTop->NextNode = NULL;
    }

    return TopNode;
}

링크드 리스트로 구현하는 스택 예제 프로그램

이번에는 위의 내용들을 모아 프로그램으로 만들려고 합니다. 이 예제에서는 앞에서 설명한 각 연산들과 더불어 설명하지 않은 몇 가지 간단한 연산들도 포함하고 있습니다. 예를 들어 스택의 최상위 노드를 제거하지는 않은 채로 반환만 하는 LLS_Top() 함수, 스택이 비어있는 지 여부를 점검하는 LLS_IsEmpty() 함수, 스택의 크기를 재는 LLS_GetSize() 함수가 바로 그것들입니다. 이 함수들의 내용은 코드를 작성하면서 익힐 수 있습니다.

예제 프로그램은 세 개의 파일로 구성되어 있습니다. LinkedListStack.h와 LinkedListStack.c는 스택 연산 함수를 선언하고 정으하고 있으며, Test_LinkedListStack.c 에서는 두 개의 파일에서 정의한 함수를 테스트합니다.

/*********************/
/* LinkedListStack.h */
/*********************/

#ifndef LINKEDLIST_STACK_H
#define LINKEDLIST_STACK_H

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

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

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

void  LLS_CreateStack( LinkedListStack** Stack );
void  LLS_DestroyStack( LinkedListStack* Stack );

Node* LLS_CreateNode( char* Data );
void  LLS_DestroyNode( Node* _Node );

void  LLS_Push( LinkedListStack* Stack, Node* NewNode );
Node* LLS_Pop( LinkedListStack* Stack );

Node* LLS_Top( LinkedListStack* Stack );
int   LLS_GetSize( LinkedListStack* Stack );
int   LLS_IsEmpty( LinkedListStack* Stack );

#endif LINKEDLIST_STACK_H

/*********************/
/* LinkedListStack.c */
/*********************/

#include "LinkedListStack.h"

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* 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;/*  노드의 주소를 반환한다. */
}

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
    {
        /*  최상위 노드를 찾아 NewNode를 연결한다(쌓는다). */
        Node* OldTop = Stack->List;
        while ( OldTop->NextNode != NULL )
        {
            OldTop = OldTop->NextNode;
        }

        OldTop->NextNode = NewNode;
    }

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

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

    if ( Stack->List == Stack->Top )
    {
        Stack->List = NULL;
        Stack->Top  = NULL;
    }
    else
    {
        /*  새로운 최상위 노드를 스택의 Top 필드에 등록한다. */
        Node* CurrentTop = Stack->List;
        while ( CurrentTop != NULL && CurrentTop->NextNode != Stack->Top )
        {
            CurrentTop = CurrentTop->NextNode;
        }

        Stack->Top = CurrentTop;
        CurrentTop->NextNode = NULL;
    }

    return TopNode;
}

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

int LLS_GetSize( LinkedListStack* Stack )
{
    int    Count = 0;
    Node*  Current = Stack->List;

    while ( Current != NULL )
    {
        Current = Current->NextNode;
        Count++;
    }

    return Count;
}

int LLS_IsEmpty( LinkedListStack* Stack )
{
    return (Stack->List == NULL);
}
/**************************/
/* Test_LinkedListStack.c */
/**************************/

#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;
}
반응형

'IT > 알고리즘' 카테고리의 다른 글

큐 (Queue) - 큐의 주요 기능, 순환 큐  (0) 2020.07.15
스택 응용하기 - 사칙연산 계산기 만들기  (0) 2020.07.15
스택(Stack)의 개념 및 배열로 구현하는 스택  (0) 2020.06.26
환형 링크드 리스트 (원형 링크드 리스트, Circular Linked List)  (0) 2020.06.25
더블 링크드 리스트(Doubly Linked List)  (0) 2020.06.23

공유하기

facebook twitter kakaoTalk kakaostory naver band

'IT/알고리즘' 의 관련글

loading

티스토리툴바