[1주차 TIL] KnockOn Bootcamp 스택&큐

💡 스택(Stack)이란?

스택(Stack)은 자료구조의 한 종류로, 아래 그림과 같이 한쪽 방향에서만 데이터를 넣거나(Push) 꺼낼 수 있는(Pop) 구조이다.

이러한 특성 때문에, 가장 나중에 추가된 데이터가 가장 먼저 제거되는 후입선출(LIFO, Last In First Out) 방식으로 동작한다.

스택의 기본 개념

• 삽입(Push) : 데이터를 스택의 맨 위(Top)에 넣는 작업
• 삭제(Pop) : 스택의 맨 위(Top)에 있는 데이터를 꺼내는 작업(스택에서 데이터는 삭제됨)
• 확인(Peek) : 스택에서 데이터를 삭제하지 않고 맨 위의 데이터를 확인만 하는 작업

 

🎯 스택 구현하기(배열)

배열의 크기를 동적으로 구현

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

void push(int** stack, int* size, int data)
{
    *size = *size + 1;    // 스택 크기 증가

    if(stack == NULL)
    {
        *stack = (int*) malloc(sizeof(int) * (*size));    // 스택이 아직 생성되지 않은 경우 스택 생성
    }
    else
    {
        // 스택의 메모리 사이즈를 새로 할당
        int* temp = realloc(*stack, sizeof(int) * (*size));

        if(temp == NULL)
        {
            printf("realloc falied\n");

            return;
        }

        *stack = temp;
    }

    (*stack)[*size - 1] = data;    // 스택에 데이터 삽입
}

void pop(int** stack, int* size)
{
    if(*size == 0 || *stack == NULL)    // 스택이 비어있는지 체크
    {
        printf("stack is empty\n");

        return;
    }

    printf("pop: %d\n", (*stack)[*size - 1]);    // pop 되는 데이터를 콘솔에 출력

    *size = *size - 1;    // 스택의 크기 감소

    if(*size == 0)    // 스택이 비어있는 상태가 되는지 체크
    {
        *stack = NULL;

        return;
    }

    // 스택의 메모리 사이즈를 새로 할당
    int* temp = realloc(*stack, sizeof(int) * (*size));

    if(temp == NULL)
    {
        printf("realloc failed\n");

        return;
    }

    *stack = temp;
}

// 스택의 내부 값 콘솔 출력
void printStack(int* stack, int size)
{
    printf("stack: ");

    for(int i = 0; i < size; i++)
    {
        printf("%d ", stack[i]);
    }

    printf("\n");
}

int main()
{
    int* stack = NULL;
    int size = 0;

    push(&stack, &size, 1);
    push(&stack, &size, 2);
    push(&stack, &size, 3);
    push(&stack, &size, 4);
    push(&stack, &size, 5);

    printStack(stack, size);

    pop(&stack, &size);
    pop(&stack, &size);
    pop(&stack, &size);
    pop(&stack, &size);
    pop(&stack, &size);
    pop(&stack, &size);

    free(stack);

    return 0;
}

출력 결과

stack: 1 2 3 4 5
pop: 5
pop: 4
pop: 3
pop: 2
pop: 1
stack is empty

🎯 스택 구현하기(연결 리스트)

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

// 연결 리스트를 위한 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 스택의 top을 가리키는 포인터
void push(Node** top, int data)
{
    // 새 노드 생성
    Node* newNode = (Node*) malloc(sizeof(Node));

    if(newNode == NULL)
    {
        printf("malloc failed\n");
        return;
    }

    newNode->data = data;
    newNode->next = *top;

    *top = newNode;    // top 갱신
}

void pop(Node** top)
{
    if(*top == NULL)
    {
        printf("stack is empty\n");
        return;
    }

    Node* temp = *top;

    printf("pop: %d\n", temp->data);

    *top = temp->next;

    free(temp);
}

// 스택의 내부 값 출력
void printStack(Node* top)
{
    printf("stack: ");

    Node* current = top;

    while(current != NULL)
    {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

int main()
{
    Node* stack = NULL;

    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    push(&stack, 4);
    push(&stack, 5);

    printStack(stack);

    pop(&stack);
    pop(&stack);
    pop(&stack);
    pop(&stack);
    pop(&stack);
    pop(&stack);
    
    return 0;
}

출력 결과

stack: 1 2 3 4 5
pop: 5
pop: 4
pop: 3
pop: 2
pop: 1
stack is empty

---

💡 큐(Queue)란?

큐(Queue)는 자료구조의 한 종류로, 아래 그림과 같이 한쪽 방향에서 데이터를 넣고(Enqueue) 반대쪽에서 꺼낼 수 있는(Dequeue) 구조이다.

이러한 특성 때문에, 가장 먼저 추가된 데이터가 가장 먼저 제거되는 선입선출(FIFO, First In First Out) 방식으로 동작한다.

큐의 기본 개념

• 삽입(Enqueue) : 데이터를 큐의 맨 뒤에 넣는 작업
• 삭제(Dequeue) : 큐의 맨 앞에 있는 데이터를 꺼내는 작업(큐에서 데이터는 삭제됨)

 

🎯 큐 구현하기(배열)

배열의 크기를 동적으로 구현

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

void enqueue(int** queue, int* size, int data)
{
    *size = *size + 1;    // 큐 크기 증가

    if(*queue == NULL)
    {
        *queue = (int*) malloc(sizeof(int) * (*size));    // 큐가 아직 생성되지 않은 경우 큐 생성
    }
    else
    {
        int* temp = realloc(*queue, sizeof(int) * (*size));

        if(temp == NULL)
        {
            printf("realloc failed\n");
            return;
        }

        *queue = temp;
    }

    (*queue)[*size - 1] = data;    // 큐의 끝에 데이터 삽입
}

void dequeue(int** queue, int* size)
{
    if(*size == 0 || *queue == NULL)
    {
        printf("queue is empty\n");
        return;
    }

    printf("dequeue: %d\n", (*queue)[0]);    // 맨 앞 데이터 출력

    // realloc 시 배열의 끝부분이 제거되므로 한 칸씩 앞으로 밀기
    for(int i = 1; i < *size; i++)
    {
        (*queue)[i - 1] = (*queue)[i];
    }

    *size = *size - 1;    // 크기 감소

    if(*size == 0)
    {
        free(*queue);
        *queue = NULL;
        return;
    }

    int* temp = realloc(*queue, sizeof(int) * (*size));

    if(temp == NULL)
    {
        printf("realloc failed\n");
        return;
    }

    *queue = temp;
}

// 큐 내용을 콘솔에 출력
void printQueue(int* queue, int size)
{
    printf("queue: ");

    for(int i = 0; i < size; i++)
    {
        printf("%d ", queue[i]);
    }

    printf("\n");
}

int main()
{
    int* queue = NULL;
    int size = 0;

    enqueue(&queue, &size, 10);
    enqueue(&queue, &size, 20);
    enqueue(&queue, &size, 30);
    enqueue(&queue, &size, 40);
    enqueue(&queue, &size, 50);

    printQueue(queue, size);

    dequeue(&queue, &size);
    dequeue(&queue, &size);
    dequeue(&queue, &size);
    dequeue(&queue, &size);
    dequeue(&queue, &size);
    dequeue(&queue, &size);

    free(queue);

    return 0;
}

출력 결과

queue: 10 20 30 40 50
dequeue: 10
dequeue: 20
dequeue: 30
dequeue: 40
dequeue: 50
queue is empty

---

🎯 큐 구현하기(연결 리스트)

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

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 큐 구조체 정의 (front와 rear를 모두 가짐)
typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

// 큐 초기화
void initQueue(Queue* q)
{
    q->front = NULL;
    q->rear = NULL;
}

void enqueue(Queue* q, int data)
{
    Node* newNode = (Node*) malloc(sizeof(Node));

    if(newNode == NULL)
    {
        printf("malloc failed\n");
        return;
    }

    newNode->data = data;
    newNode->next = NULL;

    if(q->rear == NULL)    // 큐가 비어있는 경우
    {
        q->front = newNode;
        q->rear = newNode;
    }
    else
    {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

void dequeue(Queue* q)
{
    if(q->front == NULL)
    {
        printf("queue is empty\n");
        return;
    }

    Node* temp = q->front;

    printf("dequeue: %d\n", temp->data);

    q->front = q->front->next;

    if(q->front == NULL)    // 큐가 비게 된 경우 rear도 NULL로 설정
    {
        q->rear = NULL;
    }

    free(temp);
}

// 큐의 내용을 콘솔에 출력
void printQueue(Queue* q)
{
    printf("queue: ");

    Node* current = q->front;

    while(current != NULL)
    {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

// 큐가 비어있는지 확인
int isEmpty(Queue* q)
{
    return q->front == NULL;
}

// 메모리 해제
void freeQueue(Queue* q)
{
    while(!isEmpty(q))
    {
        dequeue(q);
    }
}

int main()
{
    Queue q;

    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    enqueue(&q, 40);
    enqueue(&q, 50);

    printQueue(&q);

    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);

    freeQueue(&q);

    return 0;
}

출력 결과

queue: 10 20 30 40 50
dequeue: 10
dequeue: 20
dequeue: 30
dequeue: 40
dequeue: 50
queue is empty