1. 배열을 이용한 큐 구현
단순히 스택과 같이 큐를 배열을 이요하여 구현하면 아래와 같다.
문제점은 큐의 크기를 한번 다 사용하고 나면 큐는 실제로는 비어있지만 더이상 데이터를 삽입할 수가없다.
그렇기 때문에 배열을 이요할 때에는 원형 큐를 구현하게된다.
init: 큐 초기화
isEmpty: 큐가 비어있으면 1반환, 데이터가 있으면 0 반환
isFull: 큐가 가득 차있으면 1반환, 빈공간이 있으면 0반환
enqueue: 큐에 데이터 삽입
dequeue: 큐에서 데이터 추출
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 | #include <stdio.h> #define MAX_SIZE 10 typedef struct _queue { int data[MAX_SIZE]; int front; int rear; }queue; void init(queue* q) { q->front = 0; q->rear = 0; } int isEmpty(queue* q) { if (q->front == q->rear) return 1; else return 0; } int isFull(queue* q) { if (q->rear == MAX_SIZE) return 1; else return 0; } void enqueue(queue* q, int data) { if (isFull(q)) { printf("queue is full\n"); return; } q->data[q->rear] = data; q->rear++; } int dequeue(queue* q) { if (isEmpty(q)) { printf("queue is empty\n"); return -1; } return q->data[q->front++]; } int seek(queue* q) { if (isEmpty(q)) { printf("queue is empty\n"); return -1; } return q->data[q->front]; } int main(void) { queue q; init(&q); for (int i = 1; i <= 11; i++) { enqueue(&q, i * 10); printf("queue front : %d\n", seek(&q)); } while (!isEmpty(&q)) printf("dequeue data : %d \n", dequeue(&q)); printf("queue front : %d\n", seek(&q)); return 0; } | cs |
2. 배열을 이용한 원형 큐 구현
원형 큐의 경우, 배열을 지속적으로 사용할 수 있는 장점이 있다.
배열이 비어있는상태, 꽉차있는 상태를 구분하기 위해, 배열의 크기 - 1 만큼을 큐에서 사용한다.
front==rear인 경우 큐가 비어있는 상태이며, front-1 = rear인 경우 큐가 가득차 있는 상태이다.
isNext: 다음 인덱스를 가져오는 함수이다.
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 | #include <stdio.h> #define MAX_SIZE 10 typedef struct _queue { int data[MAX_SIZE]; int front; int rear; }queue; void init(queue* q) { q->front = 0; q->rear = 0; } int isEmpty(queue* q) { if (q->front == q->rear) return 1; else return 0; } int isNext(int pos) { if ( pos == MAX_SIZE-1)//마지막 인덱스면 첫번째로 돌아간다. return 0; else return pos + 1; } void enqueue(queue* q, int data) { if (isNext(q->rear)==q->front) { printf("queue is full\n"); return; } q->rear = isNext(q->rear); q->data[q->rear] = data; } int dequeue(queue* q) { if (isEmpty(q)) { printf("queue is empty\n"); return -1; } q->front = isNext(q->front); return q->data[q->front]; } int seek(queue* q) { if (isEmpty(q)) { printf("queue is empty\n"); return -1; } return q->data[isNext(q->front)]; } int main(void) { queue q; init(&q); for (int i = 1; i <= 11; i++) { enqueue(&q, i * 10); printf("queue front : %d\n", seek(&q)); } while (!isEmpty(&q)) printf("dequeue data : %d \n", dequeue(&q)); printf("queue front : %d\n", seek(&q)); return 0; } | cs |
위 코드를 실행하면 아래와 같은 값이 나온다.
큐의 크기는 10이지만, 실제로 사용하는 영역은 9칸 이기 때문에, 11개의 데이터를 삽입하려고 시도하면 2번의 에러가 발생한다.
3. 리스트를 이용한 큐 구현
리스트를 사용할 경우, 데이터 삽입을 위해 리스트의 가장 마지막을 노드를 가르키는 포인터(여기서는 Tail)이 필요하다.
큐에서 데이터 삽입시 Tail 위치에 삽입하며, 삭제시 Head가 가르키는 노드를 삭제한다.
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 83 84 85 86 87 88 89 90 91 92 93 | #include <stdio.h> #include <stdlib.h> typedef struct _node { int data; struct _node* next; }node; typedef struct _queue { node* head; node* tail; }queue; void init(queue* q) { q->head = NULL; q->tail = NULL; } int isEmpty(queue* q) { if (q->head == NULL) return 1; else return 0; } void enqueue(queue* q, int data) { node* newnode = (node*)malloc(sizeof(node)); newnode->data = data; newnode->next = NULL; if (isEmpty(q)) { q->head = newnode; q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } } int dequeue(queue* q) { if (isEmpty(q)) { printf("queue is empty\n"); return -1; } int ret = q->head->data; node* temp = q->head; q->head = temp->next; free(temp); return ret; } int seek(queue* q) { if (isEmpty(q)) { printf("queue is empty\n"); return -1; } return q->head->data; } int main(void) { queue q; init(&q); for (int i = 1; i <= 11; i++) { enqueue(&q, i * 10); printf("queue front : %d\n", seek(&q)); } while(!isEmpty(&q)) printf("dequeue data : %d \n", dequeue(&q)); printf("queue front : %d\n", seek(&q)); return 0; } | cs |
'컴퓨터공학 > 자료구조' 카테고리의 다른 글
| 스택(stack) (0) | 2018.08.09 |
|---|---|
| 1.2 포인터와 동적 메모리 할당 (0) | 2015.07.19 |
| 1.1 시스템 생명 주기(System Life Cycle) (0) | 2015.07.19 |
| C로 쓴 자료구조론 (0) | 2015.07.19 |
