큐

큐

• 입구와 출구가 각각 하나씩 있는 자료구조
• FIFO(First In First Out)

큐 연산

• enQueue : 큐의 가장 마지막 아이템 뒤에 새로운 아이템을 추가한다.
• deQueue : 큐의 맨앞에 있는 아이템을 빼면서 반환한다.
• isEmpty : 큐가 비어있는지 확인한다.
• isFull : 큐가 꽉 찾는지 확인한다.

큐 구현(배열 사용)

public class Queue{
	int queue[] = new int[10];
    int front = 0;
    int rear = 0;
    
    public void enQueue(int item){
    	if(isFull()){
        	System.out.println("큐가 꽉 차있습니다.");
        	return;
        }
        queue[rear] = item;
        rear = (rear + 1)%10;
    }
    
    public int deQueue(){
    	if(isEmpty()){
        	System.out.println("큐가 비었습니다.");
            return -1;
        }
        int temp = queue[front];
        front = (front + 1)%10;
        return temp;
    }
    
    public boolean isEmpty(){
    	return (front==rear);
    }
    
    public boolean isFull() {
    	return (front==(rear+1)%10);
    }
}

예시

• 백준 18258번 큐2
  https://www.acmicpc.net/problem/18258

1) 문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

2) 코드

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

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());
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		int queue[] = new int[N];
		int front =0;
		int rear = 0;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String input = st.nextToken();
			if(input.equals("empty")) {
				if(front==rear) {
					sb.append(1).append("\n");
				}
				else {
					sb.append(0).append("\n");
				}
			}
			else if(input.equals("size")) {
				sb.append(rear-front).append("\n");
			}
			else if(input.equals("front")) {
				if(front==rear) {
					sb.append(-1).append("\n");
				}
				else {
					sb.append(queue[front]).append("\n");
				}
			}
			else if(input.equals("back")){
				if(front==rear) {
					sb.append(-1).append("\n");
				}
				else {
					sb.append(queue[rear-1]).append("\n");
				}
			}
			else if(input.equals("pop")) {
				if(front==rear) {
					sb.append(-1).append("\n");
				}
				else {
					sb.append(queue[front]).append("\n");
					front = front +1;
				}
			}
			else if(input.equals("push")) {
				int item = Integer.parseInt(st.nextToken());
				queue[rear] = item;
				rear = rear+1;
			}
		}
		System.out.print(sb);
	}
}

이미지 출처 : https://velog.io/@godkor200/%ED%81%90Queue