기본적인 자료구조의 한가지
먼저 넣은 데이터가 먼저 나오는 선입선출 FIFO (First In First Out)
구조로 저장하는 형식
영어 단어 queue
는 무언가를 위해 기다리는 한 줄의 사람들을 의미하며 티켓을 사려고 사람들이 줄 서 있는 상황을 연상하면 이해하기 쉽다. 먼저 줄을 선 사람이 먼저 티켓을 사고 가듯이, 자료구조 queue
도 FIFO
구조로 동작한다.
프린터의 출력처리, 윈도우시스템의 프로세스 관리 등 데이터가 입력된 시간 순서대로 일을 처리할 때 많이 사용된다.
queue
는 한쪽에서는 데이터가 입력되고 다른 한쪽에서는 출력된다.
Enqueue
는 queue
에 데이터를 넣는 기능을 의미한다.
Dequeue
는 queue
에 데이터를 꺼내는 기능을 의미한다.
front
는 queue
의 맨 앞의 위치(인덱스). 데이터를 꺼낼 수 있는 위치.
rear
는 queue
의 맨 뒤의 위치(인덱스). 데이터를 넣을 수 있는 위치.
overflow
: queue
가 꽉 차서 더 이상 데이터를 넣을 수 없는 경우.
underflow
: queue
가 텅 비어있어서 데이터를 꺼낼 수 없는 경우.
헤드 요소
= the head of this queue
= queue의 가장 앞에 있는 요소
import java.util.Queue
public interface Queue<E> extends Collection<E>
LinkedList
로 생성하는 방법이 많이 사용된다. import java.util.Queue
import java.util.LinkedList
Queue<Integer> queue = new LinkedList<>();
Queue<String> queue = new LinkedList<>();
add(value)
value
를 queue
에 넣는다.add
가 성공하면 true
를 반환하고 실패하면 Exception
이 발생한다.offer(value)
value
를 queue
에 넣는다.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] 출력
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); // [] 출력
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 발생
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());
}
}