C언어 덱 구현

1 개요

C언어 덱 구현

2 예시 1

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

#define MAX 100
int arr[MAX];
int front;
int rear;
int size;

void init(int n) {
    front = -1;
    rear = 0;
    size = n;
}

bool isFull() {
    return ((front == 0 && rear == size - 1) || front == rear + 1);
}

bool isEmpty() {
    return (front == -1);
}

void insertFront(int value) {
    if (isFull()) {
        printf("Overflow\n");
        return;
    }

    if (front == -1) {
        front = rear = 0;
    }
    else if (front == 0) {
        front = size - 1;
    }
    else {
        front = front - 1;
    }

    arr[front] = value;
}

void insertRear(int value) {
    if (isFull()) {
        printf("Overflow\n");
        return;
    }

    if (front == -1) {
        front = rear = 0;
    }
    else if (rear == size - 1) {
        rear = 0;
    }
    else {
        rear = rear + 1;
    }

    arr[rear] = value;
}

int getFront() {
    if (isEmpty()) {
        printf("Underflow\n");
        return -1;
    }
    return arr[front];
}

int getRear() {
    if (isEmpty() || rear < 0) {
        printf("Underflow\n");
        return -1;
    }
    return arr[rear];
}

void deleteFront() {
    if (isEmpty()) {
        printf("Underflow\n");
        return;
    }

    if (front == rear) {
        front = -1;
        rear = -1;
    }
    else if (front == size - 1) {
        front = 0;
    }
    else {
        front = front + 1;
    }
}

void deleteRear() {
    if (isEmpty()) {
        printf("Underflow\n");
        return;
    }

    if (front == rear) {
        front = -1;
        rear = -1;
    }
    else if (rear == 0) {
        rear = size - 1;
    }
    else {
        rear = rear - 1;
    }
}

void printDeque() {
    if (isEmpty()) {
        printf("Deque is empty\n");
        return;
    }
    int i = front;
    while (true) {
        printf("%d ", arr[i]);
        if (i == rear)
            break;
        i = (i + 1) % size;
    }
    printf("\n");
}

int main() {
    init(5);
    insertRear(10);
    insertRear(20);
    printDeque(); // 10 20 
    insertFront(5);
    insertFront(2);
    printDeque(); // 2 5 10 20 
    deleteFront();
    deleteRear();
    printDeque(); // 5 10 
}

3 예시 2

#include <stdio.h>
#include <malloc.h>

typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

typedef struct Deque {
    Node* front;
    Node* rear;
    int size;
} Deque;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode->prev = NULL;
    return newNode;
}

Deque* createDeque() {
    Deque* dq = (Deque*)malloc(sizeof(Deque));
    dq->front = dq->rear = NULL;
    dq->size = 0;
    return dq;
}

int isEmpty(struct Deque* dq) {
    return (dq->front == NULL);
}

void insertFront(struct Deque* dq, int data) {
    struct Node* newNode = createNode(data);
    if (isEmpty(dq)) {
        dq->front = dq->rear = newNode;
    } else {
        newNode->next = dq->front;
        dq->front->prev = newNode;
        dq->front = newNode;
    }
    dq->size++;
}

void insertRear(struct Deque* dq, int data) {
    struct Node* newNode = createNode(data);
    if (isEmpty(dq)) {
        dq->front = dq->rear = newNode;
    } else {
        newNode->prev = dq->rear;
        dq->rear->next = newNode;
        dq->rear = newNode;
    }
    dq->size++;
}

void deleteFront(struct Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    struct Node* temp = dq->front;
    dq->front = dq->front->next;
    if (dq->front == NULL) {
        dq->rear = NULL;
    } else {
        dq->front->prev = NULL;
    }
    free(temp);
    dq->size--;
}

void deleteRear(struct Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    struct Node* temp = dq->rear;
    dq->rear = dq->rear->prev;
    if (dq->rear == NULL) {
        dq->front = NULL;
    } else {
        dq->rear->next = NULL;
    }
    free(temp);
    dq->size--;
}

int getFront(struct Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    return dq->front->data;
}

int getRear(struct Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return -1;
    }
    return dq->rear->data;
}

int size(struct Deque* dq) {
    return dq->size;
}

void printDeque(Deque* dq) {
    if (isEmpty(dq)) {
        printf("Deque is empty\n");
        return;
    }
    Node* current = dq->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    Deque* dq = createDeque();
    insertRear(dq, 10);
    insertRear(dq, 20);
    printDeque(dq); // 10 20 
    insertFront(dq, 5);
    insertFront(dq, 2);
    printDeque(dq); // 2 5 10 20 
    deleteFront(dq);
    deleteRear(dq);
    printDeque(dq); // 5 10 
}

4 같이 보기