[자료구조] 단일 연결 리스트(Single Linked List)로 스택(Stack) 구현

bolee·2022년 9월 22일

C 자료구조

자료구조

목록 보기

4/10

널널한 개발자 TV의 자료구조 강의 시리즈를 정리할 것이다.

스택(Stack)이란?

데이터 입/출구가 하나뿐인 선형 자료구조
Last In First Out(LIFO) / First In Last Out(FILO) 구조를 갖는다.
데이터 추가는 Push, 데이터 꺼내기는 Pop이라고 칭한다.

단일 연결 리스트로 스택 구현

아래 단일 연결 리스트(Single Linked List) 코드에서 스택(Stack)에 데이터를 추가하는 PushData()와 데이터를 꺼내는 PopData()를 추가해 준다.

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

typedef struct NODE
{
	char szData[64];
    struct NODE *next;
} NODE;

NODE g_head = { 0 };	// 더미 노드(보통은 동적할당을 함)

/* 연결 리스트가 비어있는 지 확인하는 함수 */
int IsEmpty()
{
	if (g_head.next == NULL)
    	return 1;
    
    return 0;
}

/* 앞부분에 새 노드 추가 함수 */
int InsertAtHead(char *pszData)
{
	NODE *pNode = (NODE *)malloc(sizeof(NODE));
    if (pNode == NULL)
    	return 0;
    memset(pNode, 0, sizeof(NODE));
    strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
    
    if (IsEmpty())
    	g_head.next = pNode;
    else
    {
    	pNode->next = g_head.next;
        g_head.next = pNode;
    }
    
    return 1;
}

/* 마지막 부분에 새 노드 추가 함수*/
int InsertAtTail(char *pszData)
{
	// 마지막 노드 찾기
    NODE *pTmp = &g_head;
    while (pTmp->next != NULL)
    	pTmp = pTmp->next;
    
	NODE *pNode = (NODE *)malloc(sizeof(NODE));
    if (pNode == NULL)
    	return 0;
    memset(pNode, 0, sizeof(NODE));
    strcpy_s(pNode->szData, sizeof(pNode->szData), pszData);
    
    pTmp->next = pNode;
    return 1;
}

/* 연결 리스트 전체 리스트 출력 함수 */
void PrintList(void)
{
	NODE *pTmp = &g_head;
    
	while (pTmp != NULL)
    {
    	printf("[%p] %s, next[%p]\n", pTmp, pTmp->szData, pTmp->next);
        pTmp = pTmp->next;
    }
    printf("\n");
}

/* 연길 리스트 전체 리스트 삭제 */
void ReleaseList(void)
{
	NODE *pTmp = g_head.next;
    
    printf("ReleseList()\n");
    while (pTmp != NULL)
    {
    	NODE *pDelete = pTmp;
        pTmp = pTmp->next;
        
        printf("Delete: [%p] %s\n", pDelete, pDelete->szData);
        free(pDelete);
    }
    g_head.next = NULL;
}

/* 특정 노드를 존재하는 지 확인하는 함수 */
NODE *FindData(char *pszData)
{
	NODE *pCur = g_head.next;
    NODE *pPrev = &g_head;
    while (pCur != NULL)
    {
    	if (strcmp(pCur->szData, pszData) == 0)
        	return (pPrev);
        pCur = pCur->next;
        pPrev = pPrev->next;
    }
    
    return NULL;
}

/* 특정 노드를 찾아 삭제하는 함수*/
int DeleteData(char *pszData)
{
	NODE *pPrev = FindData(pszData);
    
    if (pPrev != NULL)
    {
    	NODE *pDelete = pPrev->next;
        pPrev->next = pDelete->next;
        
    	// 삭제
        printf("DeleteData(): %s\n", pDelete->szData);
        free(pDelete);
        return 1;
    }
    return 0;
}

PushData()

void PushData(char *pszData)
{
	InsertAtHead(pszData);
}

PopData()

int PopData(NODE *pPopNode)
{
	NODE *sp = g_head.next;
    if (IsEmpty())
    	return 0;
    memcpy(pPopNode, sp, sizeof(NODE));
    g_head.next = sp->next;
    free(sp);
    return 1;
}

스택 테스트 코드

int main()
{
	// Stack 테스트를 위한 코드
    PushData("TEST01");
    PushData("TEST02");
    PushData("TEST03");
    
    PrintList();
    
    NODE node = { 0 };
    PopData(&node);
    printf("Pop: %s\n",  node.szData);
    PrintList();
    
    PopData(&node);
    printf("Pop: %s\n",  node.szData);
    PrintList();
    
    PopData(&node);
    printf("Pop: %s\n",  node.szData);
    PrintList();
    putchar('\n');
    
    PushData("TEST01");
    PushData("TEST02");
    PushData("TEST03");
    
    PopData(&node);
    printf("Pop: %s\n",  node.szData);
    PrintList();
    
    PopData(&node);
    printf("Pop: %s\n",  node.szData);
    PrintList();
    
    ReleaseList();
    
    return 0;
}