큐 Queue


  • 기본적인 자료구조의 한가지

  • 먼저 넣은 데이터가 먼저 나오는 선입선출 FIFO (First In First Out) 구조로 저장하는 형식

  • 영어 단어 queue는 무언가를 위해 기다리는 한 줄의 사람들을 의미하며 티켓을 사려고 사람들이 줄 서 있는 상황을 연상하면 이해하기 쉽다. 먼저 줄을 선 사람이 먼저 티켓을 사고 가듯이, 자료구조 queueFIFO 구조로 동작한다.

  • 프린터의 출력처리, 윈도우시스템의 프로세스 관리 등 데이터가 입력된 시간 순서대로 일을 처리할 때 많이 사용된다.



큐 Queue 용어


  • queue는 한쪽에서는 데이터가 입력되고 다른 한쪽에서는 출력된다.

  • Enqueuequeue에 데이터를 넣는 기능을 의미한다.

  • Dequeuequeue에 데이터를 꺼내는 기능을 의미한다.

  • frontqueue의 맨 앞의 위치(인덱스). 데이터를 꺼낼 수 있는 위치.

  • rearqueue의 맨 뒤의 위치(인덱스). 데이터를 넣을 수 있는 위치.

  • overflow : queue가 꽉 차서 더 이상 데이터를 넣을 수 없는 경우.

  • underflow : queue가 텅 비어있어서 데이터를 꺼낼 수 없는 경우.

  • 헤드 요소 = the head of this queue = queue의 가장 앞에 있는 요소



Java에서의 Queue


  • import java.util.Queue
    public interface Queue<E> extends Collection<E>


Queue - declaration


  • LinkedList로 생성하는 방법이 많이 사용된다.
import java.util.Queue
import java.util.LinkedList

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


Queue - insert methods


  • add(value)

    • valuequeue에 넣는다.
    • add가 성공하면 true를 반환하고 실패하면 Exception이 발생한다.
  • offer(value)

    • valuequeue에 넣는다.
    • offer가 성공하면 true를 반환하고 실패하면 false를 반환한다.
import java.util.Queue;
import java.util.LinkedList;

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

queue.add(1);
queue.add(2);
queue.offer(3);

System.out.println(queue); // [1,2,3] 출력

boolean a = queue.add(4); // add는 insert 가능하면 true를 반환한다. 
System.out.println(a); // true 출력
System.out.println(queue); // [1,2,3,4] 출력

boolean b = queue.offer(5); // offer는 insert 가능하면 true를 반환한다.
System.out.println(b); // true 출력
System.out.println(queue); // [1,2,3,4,5] 출력


Queue - remove methods


  • remove()

    • 헤드 요소 (가장 앞에 있는 요소)를 삭제하고 반환한다.
    • queue가 비어있는 경우, remove()를 하면 NoSuchElementException이 발생한다.
  • poll()

    • 헤드 요소 (가장 앞에 있는 요소)를 삭제하고 반환한다.
    • queue가 비어있는 경우, poll()를 하면 null을 반환한다.
  • clear()

    • queue의 모든 요소를 삭제한다.
import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();
queue.add(1);   // [1]
queue.add(2);   // [1,2]
queue.offer(3); // [1,2,3]
queue.offer(4); // [1,2,3,4]

queue.remove(); // 헤드요소 1을 삭제하고 queue는 [2,3,4] 된다.
int a = queue.remove(); // 헤드요소 2를 삭제하고 a에 2를 반환한다.
System.out.println(a); // 2 출력
System.out.println(queue); // [3,4] 출력

System.out.println(queue.remove()); // 3 출력
// remove()는 [3,4]에서 헤드요소 3을 삭제하고 반환해서 3이 출력되는 것이다.

queue.remove(); // [4] 에서 4를 삭제하고 반환한다.
System.out.println(queue); // [] 출력
queue.remove(); // remove()는 queue가 비어있을 때, NoSuchElementException 발생한다.
import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();
queue.add(1);   // [1]
queue.add(2);   // [1,2]
queue.offer(3); // [1,2,3]
queue.offer(4); // [1,2,3,4]

queue.poll(); // 헤드요소 1을 삭제하고 queue는 [2,3,4] 된다.
int b = queue.poll(); // 헤드요소 2를 삭제하고 b에 2를 반환한다.
System.out.println(b); // 2 출력
System.out.println(queue); // [3,4] 출력

System.out.println(queue.poll()); // 3 출력
// poll()은 [3,4]에서 헤드요소 3을 삭제하고 반환해서 3이 출력되는 것이다.

queue.poll(); // [4]에서 4를 삭제하고 반환한다.
System.out.println(queue); // [] 출력
System.out.println(queue.poll()); // null 출력
// poll()은 queue가 비어있을 때, null을 반환한다.
import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();
queue.add(1);   // [1]
queue.add(2);   // [1,2]
queue.offer(3); // [1,2,3]
queue.offer(4); // [1,2,3,4]

queue.clear(); // queue의 모든 요소를 삭제한다.
System.out.println(queue); // [] 출력


Queue - examine methods

  • element()

    • 헤드 요소를 반환한다.
    • queue가 비어있을 때, Exception 발생한다.
  • peek()

    • 헤드 요소를 반환한다.
    • queue가 비어있을 때, null 을 반환한다.
import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>();
queue.add(1);   // [1]
queue.add(2);   // [1,2]
queue.offer(3); // [1,2,3]
queue.offer(4); // [1,2,3,4]

queue.peek();  // 헤드요소 1을 반환한다.
System.out.println(queue); // 삭제하지 않고 반환만 한다. [1,2,3,4] 출력

System.out.println(queue.peek()); // 1 출력

int a = queue.peek(); // 헤드요소 1을 a에 반환한다.
System.out.println(a); // 1 출력
import java.util.Queue;
import java.util.LinkedList;

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

System.out.println(queue); // [] 출력

System.out.println(queue.peek()); // null 출력

System.out.println(queue.element()); // NoSuchElementException 발생

Queue 구현


ArrayList를 이용한 간단 구현


import java.util.ArrayList;

public class MyQueue<T> {

    ArrayList<T> arrayList = new ArrayList<T>();

    public void enqueue(T value){
        arrayList.add(value);
    }

    public T dequeue(){
        if (queue.isEmpty()){
            return null;
        }
        return queue.remove(0);
    }

    public boolean isEmpty(){
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        MyQueue<Integer> q = new MyQueue<>();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        q.enqueue(4);

        System.out.println(q.dequeue());
        System.out.println(q.dequeue());
        System.out.println(q.dequeue());
        System.out.println(q.dequeue());
    }
}
profile
real.great.code

0개의 댓글