[알고리즘] 기본 추상자료형(6) - 예제(큐ADT/데크ADT)

[문제1] 배열로 만들어진 원형큐에서 삽입, 삭제하는 프로그램

- front, rear, 배열의 초기값은 0

- front == rear이면 공백상태, front + 1 == rear이면 포화상태

- overflow의 경우 배열에 있는 모든값들을 출력 후 프로그램종료 / underflow의 경우 프로그램종료

- I value : 원형큐에 value를 삽입

- D : 원형큐에 원소삭제, 값0으로 바꿈

- P : 배열에 있는 모든 값을 출력

입력예시               출력예시

6 10 I 10 I 20 P I 30 I 40 D P I 50 I 60 I 70

0 10 20 0 0 0  0 0 20 30 40 0  overflow 60 0 20 30 40 50

#include<stdio.h> #include<stdlib.h> int *queue, queueSize, rear, front; void printQueue(){ for (int i = 0; i < queueSize; i++){ printf(" %d", queue[i]); } printf("\n"); } void enqueue(int value){ if ((rear + 1) % queueSize == front % queueSize){ printf("overflow"); printQueue(queue, queueSize); free(queue); exit(1); } rear = (++(rear)) % queueSize; queue[rear] = value; } int dequeue(){ int value; if (rear % queueSize == front % queueSize){ printf("underflow"); free(queue); exit(1); } else{ front = (++(front)) % queueSize; value = queue[front - 1]; queue[front] = 0; return value; } } void main(){ char select; int calculateSize, value; rear = 0; front = 0; scanf("%d", &queueSize); queue = (int *)malloc(sizeof(int)*queueSize); for (int i = 0; i < queueSize; i++){ queue[i] = 0; } scanf("%d", &calculateSize); for (int i = 0; i < calculateSize; i++){ getchar(); scanf("%c", &select); if (select == 'I'){ scanf("%d", &value); enqueue(value); } else if (select == 'D'){ dequeue(); } else if (select == 'P'){ printQueue(); } } free(queue); }

[문제2] 데크를 헤더와 테일이 없는 이중연결리스트로 구현하는 프로그램

- 데크 : 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 자료구조

- AF value : 데크의 front에 value를 삽입

- AR value : 데크의 rear에 value를 삽입

- DF : 데크의 front에 데이터를 삭제

- DR : 데크의 rear의 리스트를 삭제

입력예시                 출력예시

14 AF 10 AF 20 AF 30 AR 40 AR 50 P DF DF DR P DF DR DR

30 20 10 40 50  10 40  underflow

#include<stdio.h> #include<stdlib.h> #include<string.h> struct node{ int element; struct node *next; struct node *prev; }; int dequeNumber; struct node *deque, *rear, *front; void delete_front(){ struct node *p; if (dequeNumber == 0){ printf("underflow\n"); exit(1); } else{ p = front; if (dequeNumber == 1){ free(p); } else{ front = front->next; front->prev = NULL; free(p); } } } void delete_rear(){ struct node *p; if (dequeNumber == 0) { printf("underflow\n"); exit(1); } else{ p = rear; if (dequeNumber == 1){ free(p); } else{ rear = rear->prev; rear->next = NULL; free(p); } } } void add_front(int value){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->element = value; newnode->prev = NULL; newnode->next = front; newnode->next->prev = newnode; front = newnode; } void add_rear(int value){ struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->element = value; newnode->prev = rear; newnode->next = NULL; newnode->prev->next = newnode; rear = newnode; } void print(){ struct node *p = front; while (p != NULL){ printf(" %d", p->element); p = p->next; } printf("\n"); } void freeDeque() { struct node *temp = front; while (temp != NULL) { front = front->next; free(temp); temp = front; } } void main(){ int calculateSize, value; char calculate[5]; dequeNumber = 0; scanf("%d", &calculateSize); getchar(); for (int i = 0; i < calculateSize; i++){ scanf("%s", &calculate); getchar(); if (strcmp(calculate, "AF") == 0){ scanf("%d", &value); getchar(); if (dequeNumber == 0){ deque = (struct node*)malloc(sizeof(struct node)); deque->element = value; deque->next = NULL; deque->prev = NULL; front = deque; rear = deque; dequeNumber++; } else{ add_front(value); dequeNumber++; } } else if (strcmp(calculate, "AR") == 0){ scanf("%d", &value); getchar(); if (dequeNumber == 0) { deque = (struct node*)malloc(sizeof(struct node)); deque->element = value; deque->next = NULL; deque->prev = NULL; front = deque; rear = deque; dequeNumber++; } else { add_rear(value); dequeNumber++; } } else if (strcmp(calculate, "DF") == 0){ delete_front(); dequeNumber--; } else if (strcmp(calculate, "DR") == 0){ delete_rear(); dequeNumber--; } else if (strcmp(calculate, "P") == 0){ print(&front); } } freeDeque(); }