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

bolee·2022년 9월 22일

C 자료구조

자료구조

목록 보기

5/10

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

큐(Queue)이란?

데이터 입/출구가 하나뿐인 선형 자료구조
Fast In First Out(FIFO) / Lirst In Last Out(LILO) 구조를 갖는다.
데이터 추가는 Equeue(Put, Insertion), 데이터 꺼내기는 Dequeue(Get, Deletion)이라고 칭한다.
Head/Tail을 Front/Rear라도고 한다.

단일 연결 리스트로 큐 구현

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

#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;
}

Equeue()

연결 리스트의 InsertAtTail() 함수를 활용하여 구현한다.

void Equeue(char *pszData)
{
	InsertAtTail(pszData);
}

Dequeue()

스택의 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 Dequeue(NODE *pGetNode)
{
	return PopData(pGetNode);
}

큐 테스트 코드

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