[자료구조] C언어로 쉽게 풀어 쓴 자료구조 5장 연습문제

5장 큐 연습문제 풀이

---

Linear Queue

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct {
    int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
} Queue;

void initQueue(Queue* pq) {
    pq->front = pq->rear = -1;
}
void queue_print(Queue* pq) {
    for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
        if (i <= pq->front || pq->rear < i)
            printf("  | ");
        else
            printf("%d| ", pq->data[i]);
    }
    printf("\n");
}
int isFull(Queue* pq) {
    if (pq->rear == MAX_QUEUE_SIZE - 1) 
    	return 1;
    else 
    	return 0;
}
int isEmpty(Queue* pq) {
    if (pq->front == pq->rear) 
    	return 1;
    else 
    	return 0;
}
void enqueue(Queue* pq, int data) {
    if (isFull(pq)) {
		printf("Queue is Full\n");
        return;
    }

    pq->data[++(pq->rear)] = data;
}
int dequeue(Queue* pq) {
    if (isEmpty(pq)) {
    	printf("Queue is Empty\n");
    	return -1;
    }

    return pq->data[++(pq->front)];
}
int main() {
    int item = 0;
    Queue q;

    initQueue(&q);

    enqueue(&q, 10); queue_print(&q);
    enqueue(&q, 20); queue_print(&q);
    enqueue(&q, 30); queue_print(&q);

    item = dequeue(&q); queue_print(&q);
    item = dequeue(&q); queue_print(&q);
    item = dequeue(&q); queue_print(&q);
    return 0;
}

Circular Queue

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define MAX_QUEUE_SIZE 5
typedef int element;

typedef struct _Queue {
    element data[MAX_QUEUE_SIZE];
    int front, rear;
} Queue;
void QueueInit(Queue* pq) {
    pq->front = pq->rear = 0;
}
int isEmpty(Queue* pq) {
    if (pq->front == pq->rear) 
    	return 1;
    else 
    	return 0;
}
int isFull(Queue* pq) {
    if ((pq->rear + 1) % MAX_QUEUE_SIZE == pq->front) 
    	return 1;
    else 
    	return 0;
}
void enqueue(Queue* pq, element data) {
    if (isFull(pq)) {
		printf("Queue is Full\n");
        return;
    }

    pq->rear = (pq->rear + 1) % MAX_QUEUE_SIZE;
    pq->data[pq->rear] = data;
}
element dequeue(Queue* pq) {
    if (isEmpty(pq)) {
    	printf("Queue is Empty\n");
    	return -1;
    }

    pq->front = (pq->front + 1) % MAX_QUEUE_SIZE;
    return pq->data[pq->front];
}
void queue_print(Queue* pq) {

    if (!isEmpty(pq)) {
        int i = (pq->front + 1) % MAX_QUEUE_SIZE;
        while (i != pq->front) {
            printf("%d| ", pq->data[i]);
            if (i == pq->rear)
                break;

            i = (i + 1) % MAX_QUEUE_SIZE;
        }
    }
    printf("\n");
}
int main() {
    Queue q;
    element data;
    QueueInit(&q);
    printf("데이터 추가 단계\n");
    while (!isFull(&q)) {
        printf("정수를 입력하세요 : ");
        scanf("%d", &data);
        enqueue(&q, data);
    }
    printf("큐는 포화 상태입니다.\n\n");

    printf("데이터 삭제 단계\n");
    while (!isEmpty(&q)) {
        data = dequeue(&q);
        printf("꺼내진 정수: %d \n", data);
        queue_print(&q);
    }

    printf("큐는 공백입니다.\n");
    return 0;
}

Circular Deque

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

#define MAX_DEQ_SIZE 5
typedef int element;

typedef struct _deq {
    element data[MAX_DEQ_SIZE];
    int front, rear;
} Deque;

void initDeq(Deque* pd) {
    pd->front = pd->rear = 0;
}
int isEmpty(Deque* pd) {
    if (pd->front == pd->rear) 
    	return 1;
    else 
    	return 0;
}
int isFull(Deque* pd) {
    if ((pd->rear + 1) % MAX_DEQ_SIZE == pd->front) return 1;
    else return 0;
}
void addFront(Deque* pd, element data) {
    if (isFull(pd)) {
    	printf("Deque is Full\n");
        return;
    }

    pd->data[pd->front] = data;
    pd->front = (pd->front - 1 + MAX_DEQ_SIZE) % MAX_DEQ_SIZE;
}
void addRear(Deque* pd, element data) {
    if (isFull(pd)) {
    	printf("Deque is Full\n");
        return;
    }

    pd->rear = (pd->rear + 1) % MAX_DEQ_SIZE;
    pd->data[pd->rear] = data;
}
element deleteFront(Deque* pd) {
    if (isEmpty(pd)) {
    	printf("Deque is Empty\n");
    	return -1;
    }

    pd->front = (pd->front + 1) % MAX_DEQ_SIZE;
    return pd->data[pd->front];
}
element deleteRear(Deque* pd) {
    if (isEmpty(pd)) {
    	printf("Deque is Empty\n");
    	return -1;
    }

    int prev = pd->rear;
    pd->rear = (pd->rear - 1 + MAX_DEQ_SIZE) % MAX_DEQ_SIZE;
    return pd->data[prev];
}
element getFront(Deque* pd) { 
    if (isEmpty(pd)) {
    	printf("Deque is Empty\n");
    	return -1;
    }

    return pd->data[(pd->front + 1) % MAX_DEQ_SIZE];
}
element getRear(Deque* pd) { 
    if (isEmpty(pd)) {
    	printf("Deque is Empty\n");
    	return -1;
    }

    return pd->data[pd->rear];
}
void deque_print(Deque* pd) {
    printf("DEQUE(front=%d rear=%d) = ", pd->front, pd->rear);
    if (!isEmpty(pd)) {
        int i = (pd->front + 1) % MAX_DEQ_SIZE;
        while (i != pd->front) {
            printf("%d| ", pd->data[i]);
            if (i == pd->rear)
                break;
            i = (i + 1) % MAX_DEQ_SIZE;
        }
        printf("\n");
    }
}

int main(void) {
    Deque dq;
    initDeq(&dq);

    for (int i = 0; i < 3; i++) {
        addFront(&dq, i);
        deque_print(&dq);
    }

    for (int i = 0; i < 3; i++) {
        deleteRear(&dq);
        deque_print(&dq);
    }
    printf("\n");
    return 0;
}