java

자바 큐 알고리즘 구조체방식(Java queue algorithm)

sieunju 2017. 10. 6. 11:29
반응형

안녕하세요.

지금까지 블로그 포스팅 했던걸 봤는데 자바의 내용이 많더군요..;;(주 언어는 C++인데....C++내용은 안올리고 머하는건지 참..)

자바를 사용자들이 많이 사용해서 자바 내용부터 끝내고, C++ 조져야겠다고 생각하다가 이게 이렇게 되었네요

ㄷㄷ;

암튼 이번에도 자바내용이긴 한데, 곧 C++ 버전으로도 포스팅 하겠습니다. 

서론이 길었는데, 자바에서 LinkedList 를 사용해서 큐나 스택 맵을 사용하는데, 이것들을 내식대로 내가 임의로 함수를 만들어서 사용해보는건 어떨까 생각해보다가 우선 "큐"부터 만들어 보았습니다. 

우선 큐같은 경우에는 FIFO 방식입니다.  Fist In First Out 으로 처음 값이 들어가고 처음값이 빠져나가는 방식인데요, 주로 쓰이는 곳은 값을 임시로 저장했다가 바로 쓰는 곳에서 사용하고요, C++ 에서는 IOCP 서버 만들때에도 쓰레드가 큐방식이라고들 합니다. 또는, 서버와 클라에서 받은 데이터를 처리할때 큐를 사용하기도 하고요, 

위 그림 같이 I/O 에서 처음 값이 나올땐 처음값부터 순서대로 나오는 구조입니다. 

그럼 자바에서 쓰이는 큐를 값을 삽입하고 그 중간 과정을 한번 보도록 하겠습니다. 

위 사진 같이 first, last 라는 Node 형식이 있는데,  이것을 보면 처음 값과, 나중값을 저장하는구나를 알수있습니다. 

위 사진은 first에 값을 까본 것입니다. 크게 item, next 가 있는데, 간단히 설명하면 item 은 큐에 삽입한 "값" 을 말하는 것이고, next 는 다음에 들어갈 큐의 정보들을 말하는 것입니다. 

그리고, last 는 맨 마지막 값을 저장하는 부분이 되겠습니다. 

그다음으로는 큐를 clear 했을 경우를 보겠습니다. 

보시다시피 first , last 의 값은 NULL 값이 되었습니다. 

그후 다시 값을 삽입하면 맨처음 사진과 같이 되더군요...

힌트를 구했으니 한번 코딩화 해보도록 하겠습니다. 

위에서부터 차례대로 설명해보도록 하겠습니다. 

이것은 큐가 값을 삽입하고 그다음값을 조정해주는 클래스또는 구조체 입니다. 

제네릭T를 통하여, 어떤 형태든 들어올수 있게끔 설정했습니다. 


변수부터, 생성자, 값의 유뮤를 정해주는 함수를 차례대로 설명하겠습니다. 

front 는 말그대로 처음값부터 차례대로 쌓이는 클래스(구조체) 입니다. 

end 는 맨 마지막 값만 저장이 되는 클래스(구조체) 입니다.

cnt 는 나중에 clearPop이 함수를 사용할때 쓰이는 것입니다. 

front 의 값의 따라서 값이 비었는지 확인해주는 isEmpty 함수입니다. 

큐에서 가장 중요하다고 생각되는 부분인데요, 우선 처음부터 설명해주자면, 

병렬 프로그래밍이라고 다중쓰레드를 사용해서 큐클래스를 사용할때에는 여러군대에서 동시에 Push 나 Pop , Clear 를 사용하면, 어느쪽에는 큐클래스를 Clear 했는데 어느쪽에선 A의 값을 POP해버리면 안전성이 보장 안되기 때문에, synchronized (동기화) 처리를 했습니다. 

그리고 어떤 형태든 그것에 맞게 처리하기 위해 제네릭을 했습니다. 

temp,end,front 를 잘보셔야 하는데요. 이 부분은 한마디로 정의하자면 주소값을 이용한 참조(call by reference)입니다.

일단 결과부터 말씀드리면, front 의 값은 맨처음 값을 선언할때 end 값이 저장이 되는데, 그이후, end 의 값이 new 로인해 생성이 되어서 그값이  front 에 차곡차곡 쌓이게 됩니다. C에서는 포인터 &or * 를사용해서 주소값을 가리킬수가 있는데, 예를 들면, 

삽입할 데이터 값이 mdata 일때

JStruct* temp  = (JStruct*) &mdata; 

간단히 이렇게 하고 JStruct 구조체가 

<template typedef T>

strct JStruct{

T data;

JStruct* next;

}

이런식이면, temp의 data는 형틀에 맞게 mdata 주소값은 temp->data 의 주소값을 가리키게 됩니다. 

따로 malloc , new 를 사용안하고 주소값을 가리키는 것만으로도 저렇게 접근할수 있습니다.

이것이 포인터의 매력이라고 할수있죠!


다시 자바로 넘어와서 

temp 라는 구조체를 선언과 동시에 end의 구조체를 삽입했습니다. 

그후에 end 를 new를 이용하여 생성하고, 데이터의값과 next 의 값을 null 했습니다. 이렇게 되면, 

temp 는 처음 값을 삽입할때 null 인상태로 되고, 그후에  front 의 값은 값이 들어간 상태인 end로 가리키게 됩니다.  이걸 캡처해서 보여드리면, 

id값이 같다는 것을 볼수있는데 이게 첫번째 값을 삽입했을때 경우입니다. 

그 후에 temp 주소값의 변동과 front 주소값의 변동입니다. 

처음에는front == end 를 통해서 end에서 값을 front 에 참조를 했습니다. 

그후에는 temp.next = end 를 통해서 end의 값은 temp.next 를 통해서 temp 는 이전값,현재값을 가지게 됩니다. 

그리고 참조를 통하여 front 는 삽입할때마다 그 값이 계속해서 end값이 쌓이게 됩니다. 

말이좀 어려운데, 

중간 과정을 보여드리면, 이런식으로 구성되어 있습니다.  

여기서 의문점이 드는게 front 의 값은 처음에 값을 삽입할때만 넣었는데 왜 값을 삽입할때마다 점점 값들이 쌓이나요? 라는 의문점이 들수있는데 이게 바로 (call by reference)  참조의 매력입니다. 

자바는 클래스로 접근해야 참조를 할수 있어서 좀 번거롭긴한데, C같은 경우는 포인터만 걸어도 알아서 참조가 되는 점이 있긴하지만, end의 값이 변동이 될때 그리고 그 end의 값이 처음 값삽입 이후 어떻게 해주냐에 따라서 

front 의 값이 알맞게 변동이 됩니다. 

이 부분은 포인터에 대해서 미리 공부를 하셔야지 이해를 할수 있습니다. 그냥 맬럭이나 뉴를 사용해서 메모리를 할당한다 이런 기본적인거 말고 주소값을 이용해서 컨트롤 하는 부분에 대해서 이해를 하셔야 가능 할것으로 보입니다. 

다음으로는 pop 함수입니다. 형태의 맞게 리턴을 제네릭으로 했으며, 데이터가 없을시 cnt 의 값은 0, 그리고 null값으로 리턴합니다. 

그게 아닐시에는 처음 값이 value에 박히고, 그이후 그다음 값의 정보는 다시 front 로 덮어씌우게 됩니다. 

다음으로는 clear 함수인데 타입이 2가지가 있습니다. 반복문을 통하여 일일히 pop을 통해서 front 의 값을 null로 바꾸거나, 그냥 한번에 front , end 를 null 로 바꾸는 타입이 있습니다. 

한번에 null하는것이 가장 좋아 보이긴 한데, 저는pop을 통해서 하는방법도 나쁘지 않다고 생각합니다. 

이건 둘다, 또는 기존에 LinkedList 큐를 이 3가지를 테스트해본결과 메모리에서는 비슷비슷했습니다. 

성능에서는 테스트를 안해봤지만, clarPop 이 함수를 어떻게 잘 해보면, 그냥 null보다 좀더 좋게 메모리성능을 잘해 낼수 있을거 같다는 저의 극히 주관적인 생각입니다. 

(나중에 실력 더 좋아지면, 가능할지도..?)

아 마지막으로 사용법에 대해서 말씀 안해드렸네요. 

사용법은 기존에 LinkedList와 동일합니다. 

-기존 방식

Queue<void> que = new LinkedList<void>();

-선언

JQue<void> que = new JQue<void>();


기존 큐 삽입은 que.add 였다면, 제가 만든것은 que.push 입니다. 

값을 빼오는 것은 que.remove였다면, 제가 만든것은 que.pop 입니다.

다음 번에는 c++ 버전으로 포스팅 해보겠습니다. 감사합니다. 


이상 포스팅을 마치도록 하겠습니다. 

ps. 아 보니까 값을 리턴만 하는 peek 함수를 만들었어야 했는데 이건뭐....제맘인걸로 ㅎ



반응형