[C 자/알] 스택과 큐

스택과 큐는 이를 활용하는 코딩 테스트 문제가 주로 등장한다

 

스택(Stack)
기본적인 구조는 배열과 동일하다

하지만 먼저 들어온 데이터가 나중에 나가는 구조를 가진다

 

스택 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

enum
{
    FALSE = 0,
    TRUE = 1,
    MAXCOUNT = 1024
};

typedef struct Stack
{
    int Data[MAXCOUNT];
    size_t Top;
} Stack_t;

void Push(Stack_t* InStack, int InData);
int IsEmpty(Stack_t* InStack);
int Pop(Stack_t* InStack);

int main(void)
{

    return 0;
}

void Push(Stack_t* InStack, int InData)
{
    assert(InStack->Top < MAXCOUNT);

    InStack->Data[InStack->Tap++] = InData;
}

int IsEmpty(Stack_t* InStack)
{
    if (0 == InStack->Top)
    {
        return TRUE;
    }
    
    return FALSE;
}

int Pop(Stack_t* InStack)
{
    assert(FALSE == IsEmpty(InStack));

    return InStack->Data[--InStack->Top];
}

 

큐(Queue)

먼저 들어온 데이터가 먼저 나가는 구조를 가진다

 

큐 구현 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

enum
{
    FALSE = 0,
    TRUE = 1,
    MAXCOUNT = 1024
};

typedef struct Queue
{
    int Data[MAXCOUNT];
    size_t Count;
    size_t Front;
    size_t Rear;
} Queue_t;

void Enqueue(Queue_t* InQueue, int InData);
int IsEmpty(Queue_t* InQueue);
int Dequeue(Queue_t* InQueue);
void Print(Queue_t* InQueue);

int main(void)
{
    size_t i;
    Queue_t Queue = { 0, };

    for (i = 0; i < 5; ++i)
    {
        Enqueue(&Queue, (int)i * 2);
    }
    Print(&Queue);

    printf("Dequeue: ");
    for (i = 0; i <= 2; ++i)
    {
        printf("%d ", Dequeue(&Queue));
    }
    printf("\n");
    Print(&Queue);

    for (i = 0; i <= 2; ++i)
    {
        Enqueue(&Queue, (int)i * 3);
    }
    Print(&Queue);

    return 0;
}

void Enqueue(Queue_t* InQueue, int InData)
{
    assert(InQueue->Count < MAXCOUNT);

    InQueue->Data[InQueue->Rear] = InData;
    InQueue->Rear = (InQueue->Rear + 1)171;
    ++InQueue->Count;
}

int IsEmpty(Queue_t* InQueue)
{
    if (0 == InQueue->Count)
    {
        return TRUE;
    }

    return FALSE;
}

int Dequeue(Queue_t* InQueue)
{
    int ReturnedData;

    assert(FALSE == IsEmpty(InQueue));

    ReturnedData = InQueue->Data[InQueue->Front];
    InQueue->Front = (InQueue->Front + 1) % MAXCOUNT;
    --InQueue->Count;

    return ReturnedData;
}

void Print(Queue_t* InQueue)
{
    size_t i;

    assert(FALSE == IsEmpty(InQueue));

    i = InQueue->Front;
    while (InQueue->Rear != i)
    {
        printf("[%zu]: %d\n", i, InQueue->Data[i]);
        i = (i + 1) % MAXCOUNT;
    }
    printf("\n");
}