queue란 무엇인가?

개요

알고리즘 문제를 하나씩 풀다보니 자료구조와 관련된 문제가 나오는데, 큐 메서드들이 헷갈리는게 많아서  한번 정리해야겠다 싶었다.

queue란 무엇인가?

Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데, 이처럼 줄을 지어서 순서대로 처리되는 것을 큐(queue)라고 한다.

큐는 자료를 쌓아두는 스택(Stack)과 다르게 FIFO(First In First Out)의 구조로 먼저 들어온 데이터가 먼저 나가게 된다.(스택은 First In Last Out의 구조를 가진다.)

Dequeue : 맨앞 데이터 삭제 / Enqueue : 맨뒤에 데이터 추가

queue의 특징

1. 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out)의 구조이다.

2. 큐는 맨 앞쪽을 front라고 정해서 삭제연산만 수행한다.

3. 큐의 맨 뒤쪽을 rear라고 정해서 삽입연산만 수행한다.

4. 그래프의 너비 우선 탐색(BFS)에서 사용한다.

5. 컴퓨터 버퍼에서 많이 사용된다. 한번에 많은 데이터양의 입력가 입력되었을 때 버퍼(큐)를 만들어서 대기시킨다.

 

너비 우선 탐색(BFS Breadth-First Search) : 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

queue선언

Queue<자료형> 변수명 = new LinkedList<>();

자료형에 맞는 데이터만 삽입, 삭제 가능하다.

 

Queue 변수명 = new LinkedList<>();

자료형을 선언하지 않으면 어떤 자료형이든 삽입,삭제할 수 있다.

int, String을 한 큐안에 넣을 수 있다.

queue메서드

삽입

add(value)  : value를 삽입한다.
반환값(boolean)  : 성공시 ture, 실패시 Exception 발생

offer(value) : value를 삽입한다.
반환값(boolean) : 성공시 ture, 실패시 false 반환

---

삭제

remove( ) : 맨 앞(front)의 데이터를 삭제한다.
반환값(삭제된 값) : 성공시 삭제된 value를 반환, 공백 큐 일 경우  Exception("NoSuchElementException") 반환

remove(value) : 큐에서 value값을 찾아서 삭제한다.
반환값(boolean) : 큐에 해당 value가 존재하면 삭제 후 true, 존재하지 않는다면 false반환

poll() : 맨 앞(front)의 데이터를 삭제한다.
반환값(삭제된 값) : 삭제하면 value를 리턴하고, 공백 큐 일 경우 null을 반환.

---

맨 앞(fornt) 데이터 출력

element( )

반환값 : 맨 앞의 데이터를 반환, 공백 큐 일 경우 Exception("NoSuchElementException") 발생

peek( )
반환값 : 맨 앞의 데이터를 반환, 공백 큐 일 경우 null 반환

---

공백 큐 만들기

clear( ) : 공백 큐를 만든다.

반환값(void): 없음

 

예시

백준 10845번 큐

들어오는 명령어에 따라 큐를 처리하는 문제로 큐 자료구조를 사용하면 어렵지 않게 풀 수 있다.

10845번: 큐

주의할 점으로는 큐의 메서드에는 맨 뒤(back)의 데이터를 가져올 수 없기 때문에 따로 변수를 만들어서 데이터가 추가될 때 마다 해당 변수의 값을 바꿔줬다.

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> q = new LinkedList<>();
        int last = 0;  //큐는 맨뒤의 데이터를 출력하는 메서드가 없기 때문에 따로 저장해야한다.

        for(int i=0; i<n; i++) {
            String str = br.readLine();
            StringTokenizer st = new StringTokenizer(str," ");
            String method = st.nextToken();
            if(method.equals("push")) {
                int num = Integer.parseInt(st.nextToken());
                q.offer(num);
                last = num;
            } 

            else if(method.equals("pop")) {
                if(q.isEmpty()) {
                    System.out.println(-1);
                } else {
                    System.out.println(q.poll());
                }
            } 

            else if(method.equals("size")) {
                System.out.println(q.size());
            } 

            else if(method.equals("empty")) {
                if(q.isEmpty()) {
                    System.out.println(1);
                } else {
                    System.out.println(0);
                }
            } 

            else if(method.equals("front")) {
                if(q.isEmpty()) {
                    System.out.println(-1);
                } else {
                    System.out.println(q.peek());
                }
            }

            else if(method.equals("back")) {
                if(q.isEmpty()) {
                    System.out.println(-1);
                } else {
                    System.out.println(last);
                }
            }
        }
    }
}

---

참고자료

https://coding-factory.tistory.com/602

https://kwin0825.tistory.com/157