큐 구현 / 백준 10845 / Queue

Queue 란 First In First Out 을 만족하는 자료구조로 놀이공원을 생각하면 이해하기 쉽다.

먼저와서 줄을 선 사람이 가장 먼저 놀이기구를 탈수 있는 것과 같은 원리이다. 

일종의 터널인데 들어가는 입구 하나이고 나가는 입구도 하나이다. 그런데 한번에 한사람밖에 못지나갈정도로 좁다면

사람들이 줄줄이 들어가면 나올때 가장 먼저 들어갔던 사람이 나올것이다. 

먼저 줄을 선사람이 차례대로 은행일을 볼수 있다. Queue에 아주 좋은 예 이다.

대부분의 자료구조가 그렇듯 안에서 어떻게 구현을 하느냐는 프로그래머의 마음이다. 링크드 리스트로 구현할수도 있고, 배열로 구현할수도 있다.

환형으로 구현해서 메모리의 절감을 가져올 것인지 그냥 깡 Linear로 해서 그냥 편한것을 추구할것인지 까지도 모두 프로그래머 마음대로이다. 요컨대

원하는 함수가 원하는 결과만 가져오면 되지 그 과정은 중요치 않다는 것이다.

물론 그 과정까지 빠르고 적은 메모리로 해결할 수 있게 구현하는 사람이 고급 프로그래머 일것이다.

어쨋든....Stack 에 이어 이번 Queue 구현도 배열로 하였는데, 문제는 도대체왜 내 비주얼에서 String이 사용이안되는건지.....

Stack 과 비슷하게 아스키 코드를 사용하려 했으나 이번 큐에 사용되는 함수들 

push

pop

size

empty

front

back

모든 함수의 두번째 알파벳이 다른것이 보이는가 ? 보인다면 당신도 나처럼 변태같은 방법으로 코딩하는것이 분명하다

두번째 알파벳들을 이용해 스위치로 분기를 주고 인덱스를 가리키는 두가지 변수를 통해 큐를 제어하였다.

왜 두가지 변수가 필요하냐면 들어가는 입구를 관리해줄 하나와 출구를 관리해줄 하나가 필요하기 때문이다.

스택의 경우는 입구가 곧 출구였으므로 관리할 변수가 하나면 됬지만, 큐는 입구 따로 출구 따로이기 때문이다.

다시한번 놀이공원을 생각해보자, 놀이기구 타는데 들어가는 입구만 관리하고, 다 타고 나가는 사람들을 관리 안한다면 문제의 여지가 많을 것이다.

왜 String이 사용안되는거지....

#include <stdio.h>

unsigned int queue[10000]; char mem[6]; int output = 0, input = 0; int main() { int N,a,temp; scanf("%d", &N); for (a = 0; a < N; a++) { scanf("%s", mem); switch (mem[1]) { case 'u' : // push scanf("%d", &temp); queue[input++] = temp; break; case 'o' : // pop if (input - output == 0) printf("-1\n"); else printf("%d\n", queue[output++]); break; case 'i' : // size  printf("%d\n",input - output); break; case 'm' : // empty if (input - output == 0) printf("1\n"); else printf("0\n"); break; case 'r' : //front if (input - output == 0) printf("-1\n"); else  printf("%d\n", queue[output]); break; case 'a' : // back if (input - output == 0) printf("-1\n"); else printf("%d\n",queue[input - 1]); break; } } return 0; }