[알고리즘] 2. 큐 와 덱

Queue 란?

• 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조 

• 먼저 넣은 것이 가장 먼저 나오기 때문에 First In Frist Out (FIFO) 라고도 한다. 

• push : 큐에 자료를 넣는 연산 

• pop : 큐에서 자료를 빼는 연산 

• front : 큐의 가장 앞에 있는 자료를 보는 연산 

• back : 큐의 가장 뒤에 있는 자료를 보는 연산 

• empty : 큐가 비어 있는지 아닌지를 알아보는 연산 

• size : 큐에 저장되어 있는 자료의 개수를 알아보는 연산

 

1. 요세푸스 문제 (1158번)

import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.concurrent.ArrayBlockingQueue;

public class Main {

	public static void main(String[] args) {
		
		// 수 입력
		Scanner sc = new Scanner( System.in );
		
		String data = sc.nextLine();
		
		StringTokenizer izer = new StringTokenizer(data);
		
		int loop = Integer.parseInt( izer.nextToken() );
		
		int chk = Integer.parseInt( izer.nextToken() );
		
		Queue< Integer > queue = new ArrayBlockingQueue<>( loop );

		for( int i=0; i<loop; i++) {
			
			queue.offer(i+1);
		}
			
		StringBuilder sb = new StringBuilder();
		sb.append( "<" );
		
		int a = 0;
		while( !queue.isEmpty() ) {
			
			++a;
			
			int b = queue.poll();
			
			if( a == chk ) {
				
				sb.append( b );
				
				if( !queue.isEmpty() ) sb.append( ", " );
				a = 0;
				
			} else {
				
				queue.offer( b );
			}

		}

		sb.append(">");
		
		System.out.println( sb.toString() );
	}
	
}

 

 

2. Deque 란?

• 양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조 

• Double-endedqueue의 약자이다. 

• push_front : 덱의 앞에 자료를 넣는 연산 

• push_back : 덱의 뒤에 자료를 넣는 연산 

• pop_front : 덱의 앞에서 자료를 빼는 연산 

• pop_back : 덱의 뒤에서 자료를 빼는 연산 

• front : 덱의 가장 앞에 있는 자료를 보는 연산 

• back : 덱의 가장 뒤에 있는 자료를 보는 연산

 

덱을 구현하였다면, 해당 구현클래스로 Stack 과 Queue의 특성을 다 사용 할 수 있는 장점이 있다.