이번에는 정답률 높은 큐 입니당
책으로 공부 꼼꼼하게 한 다음에 풀어봤던 문제여서 그런지 그때 당시에는 막힘없이 술술 코드를 썼었눈데,,,
지금 다시 해보라카믄 잘 할 수 있을런즤
사실 스택 큐는 당연히 기본적으로 술술 해야하는곤데,,, ^^(쥬륵)
<함수 설명>
* 내가 생각하기에 구조체 짜는것(?)이 중요한 것 같다. 그러면 함수는 술술 만들어지는 것 같당,,,(아님말공)
* 맨날 헷갈림 : pop는 front에서 push는 rear로
1. Queue 구조체 : max부터 차례대로 큐의 크기, 큐에 들어있는 데이터 갯수, rear, front, 큐에 저장될 데이터 배열을 말한다.
2. Initialize : 큐를 초기화 해주는 함수이다. 큐를 빈 상태로, 크기만 할당해 줍니당.
3. Enque : 이름 그대로 큐에 데이터를 삽입하는 함수이다. 큐에 들어있는 데이터 갯수(num)와 큐의 크기(max)가 같으면 큐가 가득 찼다는 의미이므로 enqueue가 불가능하기 때문에 -1을 반환해서 가득 찼음을 알린다. 스택코드에서도 그랬던 것처럼, q->num >= p->max 에서 >=라고 해 준 이유는, =만 써주어도 되지만 오류를 방지하기 위함이다. 큐가 가득차지 않았을 경우에는 큐 배열에 데이터가 추가 되었기 때문에 갯수(q->num)를 ++해 주고 큐는 push될 때 rear로 추가 되기 때문에 q->que[q->rear]에 데이터를 대입하고 rear를 ++해준다.
또한 else문 안의 if는 마지막 데이터(x)를 대입함으로서 큐가 가득찼을 때를 의미한다.
4. Deque : 마찬가지로 큐에서 데이터를 pop하는 함수이다. 큐에 아무것도 들어있지 않을 경우(que->num<=0)에는 pop할 수 없기 때문에 -1을 반환해준다(이 함수에서는 -1을 출력해 줌). 큐가 비어있지 않을 경우에는 데이터를 없애야하기 때문에 q->num을 --해준당. 또한 pop될때에는 front에서 데이터가 빠져나가기 때문에 q->front는 ++해준다! (헷갈리지 말자)
5. back : 맨 마지막 데이터 즉, 가장 나중에 들어온 데이터 출력하는 함수이다. rear-1을 해 주는 이유는 rear는 맨 마지막 데이터 다음을 가리키기 때문이다.
6. front : 맨 앞의 데이터 즉, 가장 먼저 들어온 데이터 출력하는 함수이다.
7. size : 데이터가 저장 된 큐의 크기 구하는 함수이다.
8. IsEmpty : 큐가 비어있는지의 여부를 알 수 있는 함수이다. 비어있으면 1, 아니면 0을 출력한다.
9. Isfull : 큐가 가득 차있는지의 여부를 알 수 있는 함수이다. 가득차 있으면 1, 아니면 0을 출력한다.
10. main : push, pop등 문자열 명령(?)들을 입력받아서 배열 ans1[]에 저장하여 strcmp함수로 비교하여 맞는 명령의 조건문(if)에서 함수를 사용하여 명령을 실행한다. 처음에 입력 받은 숫자만큼 명령을 입력 받고 실행해야하기 때문에 while문을 이용하였다.
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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 10000 typedef struct { int max; int num; int rear; int front; int *que; }Queue; int Initialize(Queue *q, int max) { q->num = q->front = q->rear = 0; if ((q->que = (int*)calloc(max, sizeof(int))) == NULL) { q->max = 0; return -1; } q->max = max; return 0; } int Enque(Queue *q, int x) { if (q->num >= q->max) return -1; else { q->num++; q->que[q->rear++] = x; if (q->rear == q->max) q->rear = 0; return 0; } } void Deque(Queue *q, int *x) { if (q->num <= 0) printf("%d\n", -1); else { q->num--; *x = q->que[q->front++]; if (q->front == q->max) q->front = 0; printf("%d\n", *x); } } void back(Queue *q) { if (q->num <= 0) printf("%d\n", -1); else printf("%d\n", q->que[q->rear-1]); } void front(Queue *q) { if (q->num <= 0) printf("%d\n", -1); else printf("%d\n", q->que[q->front]); } void size(Queue *q) { printf("%d\n", q->num); } void IsEmpty(Queue *q) { if (q->num <= 0) printf("%d\n", 1); else printf("%d\n", 0); } int IsFull(Queue *q) { return q->num >= q->max; } int main() { Queue q; int ans = 0, input = 0; char ans1[] = "empty"; ans1[0] = '\0'; Initialize(&q, MAX); scanf("%d", &ans); while (ans > 0) { scanf("%s", ans1); if (strcmp(ans1, "push") == 0) { scanf("%d", &input); Enque(&q, input); } else if (strcmp(ans1, "pop") == 0) Deque(&q, &input); else if (strcmp(ans1, "size") == 0) size(&q); else if (strcmp(ans1, "empty") == 0) IsEmpty(&q); else if (strcmp(ans1, "front") == 0) front(&q); else if (strcmp(ans1, "back") == 0) back(&q); ans--; } return 0; } | cs |
'백준' 카테고리의 다른 글
백준 알고리즘 2003 수들의 합2 (0) | 2019.02.22 |
---|---|
백준 알고리즘 2750번 수 정렬하기 (0) | 2019.01.30 |
백준 알고리즘 1011번 Fly me to the Alpha Centauri (0) | 2019.01.26 |
백준 알고리즘 9012번 괄호 (0) | 2019.01.15 |
백준 알고리즘 1991번 트리순회 (0) | 2019.01.08 |