[자료구조] 큐(Queue)

■ 큐란?

- FIFO (First in First Out) 방식으로 데이터를 입출력

- 현실 세계의 큐 예 )

    티켓 판매기에서 대기하고 있는 사람들,

    일방통행 도로의 차동자들, 인쇄기의 인쇄 순서, CPU의 테스크 스케줄링

- 큐의 한계 :

  1) front부터 삭제되며, 삭제된 공간을 다시는 사용하지 못한다. 

  2) (배열을 사용할 경우) 큐의 크기가 정해지기 때문에 rear가 더 움직이지 못한다.

     (-> 이 부분은 자바에서는 동적관리 객체인 LinkedList로 해결했다)

- 큐의 한계를 보완 : 원형 큐, 우선순위 큐

 

■ 큐의 내부 구조

- 유투브의 영상에 나와있는 튜토리얼에 따라 큐를 구현해보았다. 

https://www.youtube.com/watch?v=W3jNbNGyjMs&list=PLjSkJdbr_gFZL2BNnGLvTgMYXptKGIyum&index=2 

☞ 확인 사항

- 큐는 데이터를 넣을 때 마지막에 넣고, 꺼낼 때는 앞에서부터 꺼낸다

  (1) offer을 할 때는 : REAR가 가리키는 것이 있을 때 ) REAR의 NEXT에 연결

                            FRONT가 가리키는 것이 없을 때(= 저장된 데이터의 사이즈가 0) )

                                FRONT와 REAR가 모두 null임을 명시한다.

  (2) poll을 할 때는 : FRONT가 가리키는 것이 없을 때 ) 꺼낼 수 없으므로 예외 (NoSuchElementException)를 발생

                           FRONT를 꺼낸 뒤 FRONT->NEXT를 FRONT로 변경

                           만약에 새로운 FRONT가 가리키는게 없을때(= 저장된 데이터의 사이즈가 0)

                               FRONT와 REAR가 모두 null임을 명시한다.

※ 자바의 경우 큐는 인터페이스며, LinkedList가 이를 구현하고 있다.

   아래의 실제 자바 Queue메소드는 LinkedList에서 사용 가능하다.

실제 자바 Queue 메소드	구현객체의 메소드	내용
offer(data)	add(data)	데이터 추가
poll()	remove()	가장 앞 데이터 꺼내기
peek()	peek()	가장 앞 데이터 읽기
isEmpty()	isEmpty()	비어있는지 확인

☞ 구현 하기

import java.util.NoSuchElementException;

class Queue<T>{
	
	class Node<T>{
		private T data;
		private Node<T> next;
		
		public Node(T data) {
			this.data = data;
		}
	}
	
	private Node<T> first;
	private Node<T> last;
	
	public void add(T item) {
		Node<T> t = new Node<T>(item);
		
		if (last != null) {
			last.next = t;
		}
		last = t;
		
		if (first == null) {
			first = last;
		}
	} 
	
	public T remove() {
		if (first == null) {
			throw new NoSuchElementException();
		}
		
		T data = first.data;
		first = first.next;
		
		if (first == null) {
			last = null;
		}
		return data;
	}
	
	public T peek() {
		if (first == null) {
			throw new NoSuchElementException();
		}
		return first.data;
	}
	
	public boolean isEmpty() {
		return first == null;
	}

}//end class Queue

 

■ 큐 알고리즘 예제

https://www.acmicpc.net/problem/2164

☞ 계획 수립

[1] LinkedList를 사용하여 데이터를 하나씩 넣어준다.   [2] 반복문을 통해 [1] poll [2] poll & offer을 반복한다.

☞ 계획 수행

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Ex01_2164_카드2 {

	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(reader.readLine());
		
		LinkedList<Integer> list = new LinkedList<Integer>();
		
	    //순서대로 1~N값 입력
		for (int i = 1; i <= N; i++) {
			list.offer(i);
		}
		
		//버리고, 밑으로 내리는 것 반복
		while (list.size() != 1) {			
			list.poll(); //첫번째로 꺼낸 것은 버린다.
			list.offer(list.poll()); //두번째로 꺼낸 것은 가장 마지막에 넣는다.
		}
		System.out.println(list.peek());
		
	}

}

- 여기까지는 문제가 어렵지 않았다.. 그런데 아래의 문제들을 만난 뒤 당황..

 

■ 원형 큐 (Circular Queue)의 원리를 사용한 알고리즘 문제

- 원형 큐의 개념 : 큐를 원형의 구조처럼 한 바퀴를 돌리며 사용하는 방식

☞ 계획 수립

[1] LinkedList를 사용한다.   [2] 이중 루프를 돌려,       - 바깥에서는 큐가 빌 때까지 반복,       - 안쪽에서는 K번째 전까지는 poll & offer을 반복하고, K번째에는 poll을 한다.   [3] 출력은 StringBuffer를 사용한다.

 

☞ 계획 수행

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Ex02_11866_요세푸스문제1_원형큐사용 {

	public static void main(String[] args) throws Exception{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer buffer = new StringBuffer();
		StringTokenizer token = new StringTokenizer(reader.readLine());
		
		int N = Integer.parseInt(token.nextToken());
		int K = Integer.parseInt(token.nextToken());
		
		//1~N까지의 데이터를 담을 연결리스트
		Queue<Integer> queue = new LinkedList<Integer>();
		
		//1~N까지 데이터 채우기
		for (int i = 1; i <= N; i++) {
			queue.offer(i);
		}
		
		buffer.append("<");
		
		int count = 0;
		
		//큐가 더 이상 아무것도 없을 때까지 반복
		while (!queue.isEmpty()) {
			//K보다 작을 때까지 poll&offer을 반복
			for (int i = 1; i < K; i++) {
				queue.offer(queue.poll());
			}
			
			//K번째에 poll해서 buffer에 저장
			if (count == 0) {
				buffer.append(queue.poll());
				count++;
				continue;
			}
			
			buffer.append(", ").append(queue.poll()); 
			
		}//end while
		
		buffer.append(">");

		System.out.println(buffer);
		
	}
	
}

 

>> 결과

7 3
<3, 6, 2, 7, 5, 1, 4>

▼ 처음에 일반큐 + 배열 + 커서변수를 사용해서 예제를 풀었었다. 

    그렇게 하니 코드도 길고 내가 적고도 다른 사람에게 설명할 수 없는 코드가 만들어졌다.

    스터디 때 다른 팀원분이 원형큐에 대해 설명해주셔서 알아보고 다시 작성을 해보았는데

    원형큐를 사용하니 메모리 사용량은 더 많았어도 시간은 더 준 걸 볼 수 있었다.

 

 

[참조]

https://st-lab.tistory.com/184

https://velog.io/@delicate1290/%EB%B0%B1%EC%A4%80-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4-%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4-%EB%AC%B8%EC%A0%9C-1158%EB%B2%88