[ Data Structure ] 스택(stack), 큐(queue)

스택(stack)과 큐(Queue)#

스택과 큐는 컴퓨터 과학에서 가장 기본적이면서도 중요한 자료구조이다. 이 둘은 데이터를 저장하고 관리하는 방식에 차이가 있으며, 각각의 특성에 따라 다양한 상황에서 활용된다.

스택(Stack)#

스택은 LIFO(Last In First Out) 형태로 데이터를 저장하는 구조이다. 책을 쌓아올리는 것과 비슷한 방식으로 동작한다고 생각하면 이해하기 쉽다.

스택의 주요 동작#

push: 스택의 가장 위에 새로운 데이터를 추가하는 작업이다.
pop: 스택의 가장 위에 있는 데이터를 제거하고, 그 값을 반환하는 작업이다.
peek: 스택의 가장 위에 있는 데이터를 반환하되, 제거하지는 않는 작업이다.

스택 사용 사례: 스택 메모리와 스택 프레임#

프로그램 실행 시 함수 호출과 관련된 정보(매개변수, 반환 주소 등)를 저장하는 메모리 영역으로 스택이 사용된다. 각 함수 호출마다 스택 프레임(stack frame)이 생성되어 관련 정보가 푸시(push)되고, 함수 종료 시 해당 프레임이 팝(pop)된다.

StackOverflowError#

재귀함수(recursive function)에서 탈출 조건을 제대로 설정하지 않았을 때 주로 발생한다. 스택 메모리가 가득 차서 더 이상 스택 프레임을 저장할 수 없을 때 발생하는 에러이다.

코드#


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

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

NODE* p_head = NULL;

int IsStackEmpty() {
    return (p_head == NULL || p_head->next == NULL);
}

void printStackList(void) {
    NODE* pHead = p_head->next;
    while (pHead != NULL) {
        printf("[%p] %s, next[%p]\n", pHead, pHead->szData, pHead->next);
        pHead = pHead->next;
    }
}

void ReleaseStackList(void) {
    NODE* pTmp = p_head->next;
    while (pTmp != NULL) {
        NODE* pDelete = pTmp;
        pTmp = pTmp->next;
        printf("Delete: [%p] %s\n", pDelete, pDelete->szData);
        free(pDelete);
    }
    free(p_head);
    p_head = NULL;
}

int PushData(char* pszData) {
    NODE* pNode = (NODE*)malloc(sizeof(NODE));
    memset(pNode, 0, sizeof(NODE));
    strncpy(pNode->szData, pszData, sizeof(pNode->szData));

    if (p_head == NULL) {
        p_head = (NODE*)malloc(sizeof(NODE));
        memset(p_head, 0, sizeof(NODE));
        p_head->next = pNode;
    } else {
        pNode->next = p_head->next;
        p_head->next = pNode;
    }
    return 1;
}

int PopData(NODE* pPopNode) {
    if (IsStackEmpty())
        return 0;

    NODE* stack_pointer = p_head->next;
    memcpy(pPopNode, stack_pointer, sizeof(NODE));
    p_head->next = stack_pointer->next;
    free(stack_pointer);
    return 1;
}

int Stack() {
    printf("stack\n");
    PushData("TEST01");
    PushData("TEST02");
    PushData("TEST03");

    NODE node = {0};
    PopData(&node);
    printf("Pop: %s\n", node.szData);

    PopData(&node);
    printf("Pop: %s\n", node.szData);

    PopData(&node);
    printf("Pop: %s\n", node.szData);

    ReleaseStackList();
    return 0;
}

큐(Queue)#

큐는 FIFO(First In First Out) 형태로 데이터를 저장하는 구조이다. 일상생활에서 줄을 서는 것과 비슷한 방식으로 동작한다.

큐의 주요 동작#

enqueue: 큐의 뒤쪽에 새로운 데이터를 추가하는 작업이다.
dequeue: 큐의 앞쪽에 있는 데이터를 제거하고, 그 값을 반환하는 작업이다.
peek: 큐의 앞쪽에 있는 데이터를 반환하되, 제거하지는 않는 작업이다.

큐 사용사례: producer/consumer 아키텍처#

생산자(producer)와 소비자(consumer) 프로세스 간의 데이터 교환을 위해 큐가 사용된다. 생산자는 큐에 데이터를 enqueue하고, 소비자는 큐에서 dequeue하여 데이터를 처리한다. 이 패턴은 멀티스레딩 환경에서 작업을 분배하고 처리하는 데 자주 사용된다.

OutOfMemoryError#

Java의 힙(heap) 메모리를 다 썼을 때 발생하는 에러이다. 큐에 데이터가 계속 쌓이기만 한다면 발생할 수 있다. 메모리 누수(memory leak)나 과도한 메모리 사용으로 인해 발생할 수 있으며, 적절한 메모리 관리가 필요하다.

코드#


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

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

NODE* p_queue_head = NULL;
NODE* g_pTail = 0;

int IsQueueEmpty() {
    return (p_queue_head == NULL || p_queue_head->next == NULL);
}

void PrintQueueList(void) {
    printf("\nPrintQueueList()\n");
    NODE* pHead = p_queue_head->next;
    while (pHead != NULL) {
        printf("[%p] %s, next[%p]\n", pHead, pHead->szData, pHead->next);
        pHead = pHead->next;
    }
}

void ReleaseQueueList(void)
{
    printf("\nReleaseList()\n");
    NODE* pTmp = p_queue_head->next;
    while (pTmp != NULL) {
        NODE* pDelete = pTmp;
        pTmp = pTmp->next;

        printf("Delete: [%p] %s\n", pDelete, pDelete->szData);
        free(pDelete);
    }
    p_queue_head = 0;
    g_pTail = 0;
}


int Enqueue(char* pszData)
{
    NODE* pNode = (NODE*)malloc(sizeof(NODE));
    memset(pNode, 0, sizeof(NODE));
    strncpy(pNode->szData, pszData, sizeof(pNode->szData));

    if (p_queue_head == NULL)
    {
        p_queue_head = (NODE*)malloc(sizeof(NODE));
        memset(p_queue_head, 0, sizeof(NODE));

        // 리스트에 추가된 첫번째 데이터 처리
        p_queue_head->next = pNode;
    } else {
        g_pTail->next = pNode;
    }
    g_pTail = pNode;
    return 1;
}

int Dequeue(NODE* pGetNode) {
    if (IsQueueEmpty())
        return 0;

    NODE* stack_pointer = p_queue_head->next;
    memcpy(pGetNode, stack_pointer, sizeof(NODE));
    p_queue_head->next = stack_pointer->next;
    free(stack_pointer);
    printf("Dequeue: %s\n", pGetNode->szData);
    return 1;
}

int Queue() {
    // Queue 테스트를 위한 코드

    Enqueue("TEST01");
    Enqueue("TEST02");
    Enqueue("TEST03");

    PrintQueueList();

    NODE node = {0};
    printf("\nDequeue()\n");
    Dequeue(&node);
    Dequeue(&node);
    Dequeue(&node);


    PrintQueueList();
    ReleaseQueueList();
    return 0;
}

추가 고려사항#

구현 방식: 스택과 큐는 배열이나 연결 리스트를 사용하여 구현할 수 있다. 각 구현 방식은 장단점이 있으며, 사용 상황에 따라 적절한 방식을 선택해야 한다.
시간 복잡도: 스택과 큐의 기본 연산(push/pop, enqueue/dequeue)은 일반적으로 O(1)의 시간 복잡도를 가진다.
응용 분야
- 스택: 함수 호출 관리, 괄호 매칭, 후위 표기법 계산 등
- 큐: 너비 우선 탐색(BFS), 프린터 스풀링, 프로세스 관리 등
변형: 우선순위 큐, 원형 큐 등 기본 구조를 변형한 자료구조들도 존재한다.

스택과 큐는 간단하면서도 강력한 자료구조로, 컴퓨터 과학의 여러 분야에서 핵심적인 역할을 한다. 이들의 특성을 잘 이해하고 적절히 활용한다면, 효율적이고 견고한 알고리즘과 시스템을 설계할 수 있을 것이다.