큐와 JAVA Queue 클래스

Algorithm : 큐와 JAVA Queue 클래스

: 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다.

 

큐의 특징

• FIFO(First In First Out), 가장 먼저 넣은 데이터가 가장 먼저 출력된다.
• 큐에 데이터를 넣는 작업은 enqueue, 큐에서 데이터를 꺼내는 작업은 dequeue이다.
• 데이터가 삽입되는 위치는 rear이고, 데이터를 꺼내는 위치는 front이다.

 

링 버퍼로 큐 구현하기

• 큐로 사용할 배열 : que - enqueue하는 데이터를 저장하기 위한 큐 본체용 배열
• 큐 용량 : max - que에 저장할 수 있는 최대 요소의 개수와 같다.
• 큐 요솟수 : num - que에 저장되어 있는 요소의 개수
• 생성자 : Queue - num과 front, rear를 0으로 설정하고, 매개변수 max를 멤버변수 max에 복사한 후에 que[max]를 생성한다.
• enqueue 메서드 : push - 전달받은 데이터를 배열 que[rear]에 저장하고 rear의 값을 증가시킨다. 만약 rear가 큐의 용량과 같다면 rear를 0으로 지정한다. num의 값을 증가시킨다.
• dequeue 메서드 : pop - 큐가 비어있는 경우에는 -1을 반환한다. 그 외의 경우에는 que[front]에서 데이터를 반환하고, front의 값을 감소시킨다. num의 값을 감소시킨다. 
• size 메서드 : size - num의 값을 반환한다.
• empty 메서드 : empty - num이 0보다 작거나 같으면 1, num이 0보다 크면 0을 출력한다.
• front 메서드 : num이 0보다 크면 que[front]를 반환하고, num이 0보다 작거나 같으면 -1을 반환한다.
• back 메서드 : num이 0보다 크면 que[rear - 1]을 반환하고, num이 0보다 작거나 같으면 -1을 반환한다.

 

큐 알고리즘 코드

출처 : 18258번: 큐 2 (acmicpc.net)

18258번: 큐 2

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Queue {
    
    private int front;
    private int rear;
    private int max;
    private int num;
    private int[] queue;
    
    public Queue(int max) {
        
        front = rear = num = 0;
        this.max = max;
        
        queue = new int[max];
        
    }
    
    public void push(int x) {
        
        if(num < max) {
        
            queue[rear++] = x;
            num++;
            
            if(rear == max) {
                
                rear = 0;
                
            }
        
        }
        
    }
    
    public int pop() {
        
        if(num <= 0) {
            
            return -1;
            
        }
        
        int x = queue[front++];
        num--;
        
        if(front == max) {
            front = 0;
        }
        
        return x;
        
    }
    
    public int size() {
        
        return num;
        
    }
    
    public int empty() {
        
        if(num <= 0) return 1;
        else return 0;
        
    }
    
    public int front() {
        
        if(num > 0) return queue[front];
        else return -1;
        
    }
    
    public int back() {
        
        if(num > 0) return queue[rear - 1];
        else return -1;
        
    }
    
}

public class Main {
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int N = Integer.parseInt(br.readLine());
	    
	    Queue que = new Queue(N);
	    
	    StringBuilder sb = new StringBuilder();
	    
	    for(int i = 0; i < N; i++) {
	        
	        String command = br.readLine();
	        
	        if(command.contains("push")) {
	            que.push(Integer.parseInt(command.split(" ")[1]));
	        } else if(command.contains("pop")) {
	            sb.append(que.pop()).append("\n");
	        } else if(command.contains("front")) {
	            sb.append(que.front()).append("\n");
	        } else if(command.contains("back")) {
	            sb.append(que.back()).append("\n");
	        } else if(command.contains("size")) {
	            sb.append(que.size()).append("\n");
	        } else if(command.contains("empty")) {
	            sb.append(que.empty()).append("\n");
	        }
	        
	    }
	    
	    System.out.println(sb);
	    
	}
}

 

JAVA Queue 클래스

Queue 선언

import java.util.Queue;
import java.util.LinkedList;

Queue<QueueType> queue = new LinkedList<>();
// 큐를 LinkedList로 구현

 

Queue 메서드

Enqueue

Queue<Integer> queue = new LinkedList<>();

queue.offer(1); // 큐에 값 1을 enqueue
queue.offer(3);
queue.offer(2);
queue.add(5); // 큐에 값 5를 enqueue
queue.add(4);
// queue : 1 3 2 5 4, front = 0, rear = 5

: 큐가 꽉 차 있을 경우, offer(value) 메소드는 false를 반환하고 add(value) 메소드는 큐가 꽉차는 상황에서 IllegalStateException을 발생시킨다. 사이즈의 제약이 있는 큐를 사용하는 경우에는 offer(value) 메소드의 사용을 권장한다.

 

Dequeue

queue.poll(); // 큐의 가장 앞에 있는 요소 1을 dequeue
// queue : 3 2 5 4, front = 1, rear = 5
queue.remove(); // 큐의 가장 앞에 있는 요소 3을 dequeue
// queue : 2 5 4, front = 2, rear = 5

: 큐가 비어있을 경우, poll( ) 메소드는 null을 리턴하고 remove( ) 메소드는 NoSuchElementException을 발생시킨다.

 

그 외

queue.peek(); // 큐의 가장 앞에 있는 값 3을 출력
queue.element(); // 큐의 가장 앞에 있는 값 3을 출력
queue.clear(); // 큐의 모든 데이터를 제거
queue.isEmpty(); // 큐가 비어있다면 true를, 비어있지 않다면 false를 반환

: peek() 메소드는 큐가 비어있을 때 null을 리턴하고, element() 메소드는 큐가 비어있을 때 NoSuchElementException을 발생시킨다.

 

JAVA Queue 클래스 사용 알고리즘 코드

출처 : 2164번: 카드2 (acmicpc.net)

2164번: 카드2

 

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

public class Main {
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int N = Integer.parseInt(br.readLine());
	    
	    Queue<Integer> queue = new LinkedList<>();
	    
	    for(int i = 0; i < N; i++) {
	        
	        queue.add(i + 1);
	        
	    }
	    
	    int last = 0;
	    
	    while(!queue.isEmpty()) {
	        
	        last = queue.poll();
	        
	        if(!queue.isEmpty()) {
	            int then = queue.poll();
	            queue.add(then);
	        } else {
	            break;
	        }
	        
	    }
	    
	    System.out.println(last);
	    
	}
}

 

---

 

큐 참고 사이트

• [Java] Queue 클래스 사용법 & 예제 (tistory.com)
• 자바(Java) Queue 클래스 및 예제