[1주차 TIL] KnockOn Bootcamp Pre.Rev : 스택 & 큐

스택

스택이란?

후입선출(LIFO, Last In First Out)의 구조로 이루어진 자료구조로서, 항상 스택의 한 쪽 끝에서만 데이터를 넣고 꺼낼 수 있다.
데이터를 넣는 과정을 Push, 꺼내는 과정을 Pop이라 한다.

큐

큐 란?

선입선출(FIFO, First In First Out)의 구조로 이루어진 자료구조로서, 큐의 한쪽 끝에서는 데이터의 삽입만 가능하고, 반대쪽 끝에서는 삭제만 가능하다.
데이터를 넣는 과정을 Enqueue, 꺼내는 과정을 Dequeue라고 한다.

실습

이번 실습 간에는 헤더파일을 이용하여 스택과 큐를 C언어로 구현했다.
내용은 주요한 부분에 대해서만 설명하겠다.

배열로 만든 스택

#include<stdio.h>
#include<stdbool.h>

int stack[100];
int top = -1;

int Empty() {
    if (top < 0) {
        return true;
    }
    else return false;
}

int Max() {
    if (top >= 99) {
        return true;
    }
    else return false;
}

int Push(int value) {
    if (Max() == true) {
        printf("스택이 가득찼습니다.");
        return 0;
    }
    else stack[++top] = value;
    return 0;
}

int Pop() {
    if (Empty() == true) {
        printf("스택이 비어있습니다.");
        return 0;
    }
    else return stack[top--];
}

int main() {
    Push(0);
    Push(1);
    Push(2);
    Push(3);
    Push(4);
    Push(5);
    printf("%d\n", Pop());
    printf("%d\n", Pop());
    printf("%d\n", Pop());
    printf("%d\n", Pop());
    printf("%d\n", Pop());
    printf("%d\n", Pop());
    printf("%d\n", Pop());

    return 0;
}

연결리스트로 만든 스택

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

typedef struct NODE {
    struct NODE* preLink;
    int data;
    struct NODE* nextLink;
} Node;

Node* Push(Node* head, int data) {
    while (head->nextLink != NULL) {
        head = head->nextLink;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->preLink = head;
    newNode->nextLink = NULL;
    newNode->data = data;
    head->nextLink = newNode;
    return newNode;
}

Node* Pop(Node* head, Node* top) {
    if (head->nextLink == NULL) {
        printf("스택이 비어있습니다.");
    }
    Node* temp = top;
    top = top->preLink;
    top->nextLink = NULL;
    free(temp);
    return top;
}


int main() {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->nextLink = NULL;
    Node* top = head;
    for (int i = 0; i < 6; i++) {
        top = Push(head, i);
        printf("Push 값 : %d\n", top->data);

    }
    for (int i = 0; i < 6; i++) {
        printf("pop 결과 : %d\n", top->data);
        top = Pop(head, top);
    }
    return 0;
}

배열로 만든 큐

#include<stdio.h>
#include<stdbool.h>

int queue[100];
int front = 0;
int rear = 0;

int Empty() {
    if (front == rear) {
        return true;
    }
    else return false;
}

int Max() {
    if (rear >= 99) {
        return true;
    }
    else return false;
}

int Enqueue(int value) {
    if (Max() == true) {
        printf("큐가 가득찼습니다.");
        return 0;
    }
    else queue[rear++] = value;
    return 0;
}

int Dequeue() {
    if (Empty() == true) {
        printf("큐가 비어있습니다.");
        return 0;
    }
    else return queue[front++];
}

int main() {
    Enqueue(0);
    Enqueue(1);
    Enqueue(2);
    Enqueue(3);
    Enqueue(4);
    Enqueue(5);
    printf("%d\n", Dequeue());
    printf("%d\n", Dequeue());
    printf("%d\n", Dequeue());
    printf("%d\n", Dequeue());
    printf("%d\n", Dequeue());
    printf("%d\n", Dequeue());
    printf("%d\n", Dequeue());
    return 0;
}

연결리스트로 만든 큐

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

typedef struct NODE {
    int data;
    struct NODE* nextLink;
} Node;

Node* Enqueue(Node* rear, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->nextLink = NULL;

    if (rear != NULL) {
        rear->nextLink = newNode;
    }
    return newNode; 
}

Node* Dequeue(Node* head, Node** front, Node** rear) {
    if (*front == NULL) {
        printf("큐가 비어있습니다.\n");
        return NULL;
    }

    Node* temp = *front;
    int dequeuedData = temp->data;

    *front = (*front)->nextLink;

    if (*front == NULL) {
        *rear = NULL;
    }

    free(temp);
    printf("Dequeue 값: %d\n", dequeuedData);
    return *front;
}

int main() {
    Node* head = NULL;
    Node* front = NULL;
    Node* rear = NULL;

    for (int i = 1; i <= 6; i++) {
        printf("Enqueue: %d\n", i);
        rear = Enqueue(rear, i);

        if (front == NULL) {
            front = rear;
        }
    }

    for (int i = 0; i < 6; i++) {
        front = Dequeue(head, &front, &rear);
    }

    return 0;
}

끝.