가변 Queue 구현해보기(JAVA)

JAVA를 공부하면서 자료구조를 제대로 공부해봐야 겠다고 생각했다.

Queue를 구현해보기에 앞서 Queue의 개념에 대해 설명해야 할 것 같다.

 

Queue는 FIFO(First In First Out)

• 즉, 먼저 넣은 것부터 반환하거나 삭제할 수 있다.
• 반대 개념으로는 stack이 있다.(가장 최근에 추가한 것부터 반환하거나 삭제)
• 데이터를 가져오는 위치를 front(head), 데이터를 추가할 수 있는 위치를 rear(tail)라고 한다.
• Queue 가 꽉 차서 더이상 자료를 넣을 수 없는 경우를 overflow , 비어 있어 자료를 꺼낼 수 없는 경우를 underflow 라고 한다.

queue는 선형과 환형으로 나뉘어진다.

 

1. 선형

- 크기가 제한되어 있는 막대모양을 생각해볼 수 있다.

- 단점 : 빈 공간을 사용하려면 모든 자료를 꺼내거나 한칸 씩 옮겨야 한다.

 

2. 환형

- 선형 큐의 문제점을 보완.

- front가 Queue의 끝에 위치하면 Queue의 맨 앞으로 자료를 보내서 원형으로 해결하는 방식이다.

 

메서드로는 

1. add/offer

2. put/peek

3. remove/poll

 

우선 add와 offer은 데이터를 추가하는 메서드다. 

다른 점이 있다면 꽉 차서 더이상 추가할 수 없거나 실패했을 경우 offer은 null을 반환하는 반면에, add는 exception이 발생한다.

 

put 과 peek은 가장 먼저 넣은 데이터를 반환하는 메서드다.

위와 마찬가지로 값이 없다면 put은 exception을, peek은 null을 반환한다.

 

remove 와 poll은 가장 먼저 넣은 데이터를 제거한 후 반환한다.

위와 마찬가지로 데이터가 없거나, 실패하면 remove는 exception을, poll은 null을 반환한다.

 

- 나는 가변적인 선형 Queue 만들고자 했다. 

제네릭을 사용했고, 배열을 이용했다.

 

public class Queue<E> {
	
	E itemAry[];
	int index = 0;
	
	public Queue() {}
	
	//add value
	public boolean offer(E item) {
		
		if(index != 0) {//처음 값을 넣을 때는 제외
			//원래의 배열을 가져온다
			E oldAry[] = itemAry;
			
			//배열의 크기를 하나 늘려서 다시 초기화 한다.
			itemAry = (E[])new Object[index+1];
			
			//새롭게 초기화된 배열에 값을 넣는다.
			for (int i = 0; i < oldAry.length; i++) {
				itemAry[i]=oldAry[i];
			}//for
			
		}else {//처음 값을 넣을 때
			//배열의 크기를 하나 늘려서 다시 초기화 한다.
			itemAry = (E[])new Object[index+1];
		}//if else
		
		//새로운 값을 넣는다
		itemAry[index++] = item;
		
		return true;
	}//offer()
	
	//return value of first index
	public E peek() {
	    return itemAry[0];
	}
	
	//return value and remove of first index
	public E poll() {
		
		if(index == 0) {
			return null;
		}//if queue is empty, return null
			
		//1. take value of first index
		E res = itemAry[0];
		
		//2. change index
		E[] oldAry = itemAry;
		itemAry = (E[])new Object[index-1];
		for (int i = 0; i < index-1; i++) {
			itemAry[i] = oldAry[i+1];
		}//for
		
		index--;
        
	    return res;
		
	}//poll()
	
	//queue의 크기 구하기
	public int size() {
		return itemAry.length;
	}//size()
	
	//queue 삭제
	public void clear() {
		itemAry = null;
		index = 0;
	}//clear()
	
	void print() {
		System.out.println("================");
		System.out.println("배열 출력");
		for(int i = 0 ; i < index ; i++) {
			System.out.println(i+"번째 : "+itemAry[i]);
		}//for
		System.out.println("================");
		System.out.println();
	}//로그용 메서드
}//Queue

 

위는 Queue를 만들어 본 것이다.

 

아래에서는 main method에서 내가 구현한 Queue를 실행 해봤다. 

 

public class QueueTest {

	public static void main(String[] args) {
		
		Queue<String> queue = new Queue<>();
		
		queue.offer("one");
		queue.offer("two");
		queue.offer("three");
		
		System.out.println(queue.peek());//맨 첫번째 값 반환 : "one"

		System.out.println(queue.poll());//맨 첫번째 값을 반환하면서 제거: "one"
        
        System.out.println(queue.poll());//맨 첫번째 값을 반환하면서 제거: "two"

		System.out.println("queue의 크기 : "+queue.size());// 1
        
		queue.print();//현재 queue의 데이터 출력 : "three"
		
		queue.clear();//queue 비우기
		queue.print();//현재 queue의 데이터 출력 : null
		

	}//main()

}

 

솔직히 고정 Queue를 만들 어 본 후에 배열을 가지고 다시 가변 Queue로 만드려고 하니,

그대로 배열을 써야 할지 아니면 다른 방법을 생각해봐야 할지 고민이 많았다.

 

그리고 이건 선형이라서 환형으로도 한번 만들어보려고 한다.

 

데이터 자료 타입에 대한 이해도가 떨어지는 것 같아 하나하나 구현해보고 있는데 생각보다 재미있다.

사실 물어볼 사람이 없어서 잘 맞게 구현하고 있는지는 잘 모르겠다.

회사에서 일을 하게 된다면 좀 더 잘 구현할 수 있으려나..

 

질문1) 가변형을 만들때, List를 사용해도 되는 건가? 실제로 jdk에서는 Queue 를 만들 때 어떤 식으로 자료를 저장하는지 궁금하다.

List와 Map같은 가변형을 사용하면 메모리를 많이 차지해서 함부로 쓰면 안된다는 말을 들은 것 같은데 이 부분도 좀 더 알아봐야 할 것 같다.

 

질문2) 가변형을 만들 때, 배열을 사용하지 않고도 만든다고 하던데 List를 쓰는건가?

 

질문3) 현재 내가 구현한 Queue는 데이터를 추가할 때마다 배열을 다시 초기화한다.(크기를 하나 더 늘려서)

이 방법이 효율적인 방식인지에 대해서는 의문이 든다.

 

질문4) 다들 이런 궁금증이 생길때는 어디서 궁금증을 해결하시나요?