Home

Published

- 7 min read

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

Data Structure Computer Science
img of [ Data Structure ] 스택(stack), 큐(queue)

스택(stack)과 큐(Queue)

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

스택(Stack)

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

스택의 주요 동작

  1. push: 스택의 가장 위에 새로운 데이터를 추가하는 작업이다.
  2. pop: 스택의 가장 위에 있는 데이터를 제거하고, 그 값을 반환하는 작업이다.
  3. 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) 형태로 데이터를 저장하는 구조이다. 일상생활에서 줄을 서는 것과 비슷한 방식으로 동작한다.

큐의 주요 동작

  1. enqueue: 큐의 뒤쪽에 새로운 데이터를 추가하는 작업이다.
  2. dequeue: 큐의 앞쪽에 있는 데이터를 제거하고, 그 값을 반환하는 작업이다.
  3. 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;
}

추가 고려사항

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

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