입사문제 자료구조 큐만들기

큐 작성하고 정렬하기

큐만들기는 자주 나오는 문제입니다. 다음 링크를 확인해봅시다. 

http://www.geeksforgeeks.org/queue-set-2-linked-list-implementation/

영어라서 힘들지만... 굉장히 간단한 코드입니다 .푸하하 ^~^

하지만 입사문제에서는 단지 큐를 만드는것보다 조금 더 어렵게 나오기도합니다. 큐를 소팅해보세요~ 라는식입니다.
당황하지 않고 풀려면 개념을 보다 잘 이해해야 겠죠...
알고리즘 문제를 풀 때 큐를 링크드 리스트로는 거의 사용하지 않습니다만...
자료구조 배웠냐고 물어보면... 그땐 해내야하니까 ... 이렇게 포스팅합니다..



1. 큐 구조체의 이해

큐는 노드로 구성됩니다. 큐의 front, rear 는 단지 node를 가르킬 뿐입니다. 사실 위의 노드만 있어도 충분히 큐를 구현가능합니다. 어떻게 가능할까요 ?

^^ 이렇게로도 가능합니다. 이때는 자료가 더커집니다. 이 방법은 제가 한 정점에서 뻗어나가는 그래프를 표현할 때 사용합니다. 이 경우에는 1 vertex 에서 뻗어나가는 간선들을 큐든 스택의 형태로 저장할 수 있습니다. node front를 참조할때는 배열 자체를 사용하면됩니다. head[1], head[2] .. 등등

사설이 너무 길었습니다. 아! 하지만 이 방법말고도 큐를 표현하는 여러가지 방법이 있습니다. 제 블로그에서 추후에도 더 많이 다뤘으면 좋겠습니다.


2. 구현의 예

우선 큐를 구현한다음 정렬한뒤 팝하면서 출력합니다. 큐가 비어있을때는 0XFFFFFFF 를 출력합니다. 
10 9 8 7 6 5 4 3 2 1 은 큐에 푸쉬하면서 출력되는 것이구요,
정렬하면 큐안에서 노드의 데이터가 다음과 같이 정렬됩니다. 1 2 3 4 5 6 7 8 9 10 (이건 출력X)

각 프론트 가 출력되면서 팝됩니다. 1 2 3 4 5 6 7 8 9 10 

 

3 queue init 

메모리 할당해주면됩니다. 그리고 맨처음 큐의 상태는 front 도 rear 도 0(NULL)입니다.

4 push  --  

기본적으로 push는 node를 만들어서 그뒤에 연결해줍니다. q->front 가 없을 경우 큐가 빈 경우니까 q->front=q->rear=n 을 해주고 함수를 종료합니다.
그 외의 경우는 q->rear->next = n; 을 해주면 현재 rear->next에 새로 생성된 노드가 할당됩니다.
마지막으로 q->rear=n; 을 통해 큐의 rear를 새로 생성된 노드 n 으로 설정해줘야합니다    

5 sort

버블소트입니다. 저는 처음에 queue를 정렬하라길래 노드간 스왑을 구현하려고 했는데 data만 비교해서 data만 바꾸면됩니다. 아래는 제가 참고한 주소입니다.

http://www.geeksforgeeks.org/c-program-bubble-sort-linked-list/

6 pop 

기본적으로 q->front 가 없으면 큐가 비어있다는 것입니다. 
아닌 경우 q->front 의 데이터 값을 ret 값으로 받은뒤, q->front 는 q->front->next를 가르키게 합니다.
이 떄 q->front->next 가 존재하지 않는 경우, q->rear 또한 존재하지 않게 됩니다. 즉 이전 작업에서 queue size가 1인경우 즉, 좌항의 front가 rear 인 경우였습니다.  즉 q->rear도 존재하지 않는다고 해줘야겠죠. 그런데 이부분은 우리가 구현하는 스펙만으로는 꼭 선언해줄 필요는 없습니다만.... ..
다른 경우에서는 해줘야하겠죠.  

수고하셨습니다.

전체 코드보기

https://github.com/ingyeoking13/algorithm/blob/master/swtest/sk/queue3.c