제가갖고있는 2권의 자료구조책에서는 오로지 리스트로만 구현한 덱 밖에없었습니다.
현재 수강중인 자료구조에서는 교수님께서 원형큐를 응용한 덱구현 프로그램을 올려주셨는데
확실히 리스트로 구현한 것보다 연산이 헷갈리고 어려운 것 같습니다.(이 이유때문에 책에 내용이없는것 아닐까 싶습니다.)
원형큐를 이용한 덱은 기존의 큐에서 아주 살짝만 응용하면 됩니다.
front 와 rear는 똑같이 0부터 시작하고 연산은 다음과 같습니다.
add_front: 꽉찼는지 확인 후 front 자리에 삽입 후 front=(front-1+MAX_SIZE)%MAX_SIZE;
add_rear: 꽉찼는지 확인 후 원형 큐의 enqueue와 동일
delete_front: 원형큐의 dequeue와 동일
delelte_rear: 현재 rear자리의 값 임시 저장 후 rear=(rear-1+MAX_SIZE)%MAX_SIZE 연산 후 임시 저장했던 rear자리 값 반환
즉, 한칸을 비워놓는것은 똑같고 add_front연산 후 front의 위치는 삽입한 자리 한칸 앞을 가리킵니다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #pragma warning(disable:4996) #include<stdio.h> #include<stdlib.h> /* add_front로 1~3까지 삽입 후 각각 출력하고 delete_rear로 모두 삭제하고 출력하기 //front 와 rear 위치 잘 보기 rear 1삽입 */ #define MAX_SIZE 5 typedef struct { int Dqueue[MAX_SIZE]; int front, rear; }DQType; void init(DQType* q) { q->front = q->rear = 0; } int is_full(DQType* q) { return ((q->rear + 1) % MAX_SIZE == q->front); } int is_empty(DQType* q) { return q->front == q->rear; } void add_front(DQType* q, int data) { if (is_full(q)) { fprintf(stderr, "요소가 꽉 찼습니다.\n"); return; } q->Dqueue[q->front] = data; q->front = (q->front - 1+MAX_SIZE) % MAX_SIZE; } void delete_rear(DQType* q) { if (is_empty(q)) { fprintf(stderr, "요소가 없습니다.\n"); return; } int now = q->rear; q->rear = (q->rear - 1+MAX_SIZE) % MAX_SIZE; //반환형 사용시 q->DQeue[now] 반환 } void deque_print(DQType* q) { if (!is_empty(q)) { printf("DEQUE연산: (front=%d rear=%d)= ", q->front, q->rear); int i = q->front; do { i = (i + 1) % MAX_SIZE; //한번은 출력 하고 empty여부판단해야됨 printf("%d | ", q->Dqueue[i]); //비어있으면 탈출해야됨 if (i == q->rear)break; //모든원소를 출력할 때 까지 } while (i != q->front); } printf("\n"); } int main(void) { DQType q; init(&q); for (int i = 0; i < 3; i++) { add_front(&q, i+1); deque_print(&q); } for (int i = 0; i < 3; i++) { delete_rear(&q); deque_print(&q); } return 0; } | cs |
결과
