큐 (Queue) 란?
- 입력 순서대로 데이터 처리가 필요할 때 사용하는 선입선출 구조 (FIFO)
- BFS (그래프 넓이 우선 탐색), 프린터 출력 대기열과 같은 상황에서 사용
큐의 연산
● enqueue() : 큐 맨 뒤에 데이터 추가
● dequeue() : 큐 맨 앞쪽의 데이터 삭제
위 연산 뿐만 아니라, poll(), peek(), contains(), size(), isEmpty()도 사용가능하다.
큐의 특징
● 한 쪽 끝은 front로 정하여 삭제 연산만 수행한다.
● 다른 한 쪽 끝은 rear로 설정하여 삽입 연산만 수행한다.
● ArrayList와 배열로 구현 가능하다.
1) 큐의 구현
아래 구현한 것과 같이, LinkedList로 생성하여 Queue의 다양한 메서드를 사용해보고 결과를 확인할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import java.util.LinkedList;
import java.util.Queue;
public class Queue01 {
public static void main(String[] args) {
Queue queue = new LinkedList();
queue.add(1);
queue.add(2);
System.out.println(queue.contains(2));
System.out.println(queue.poll());
System.out.println(queue.peek());
System.out.println(queue);
System.out.println(queue.size());
System.out.println(queue.isEmpty());
queue.clear();
}
}
|
cs |
2) 큐의 구현 - ArrayList
MyQueue 클래스를 ArrayList를 통해 구현해보겠다.
import java.util.ArrayList;
class MyQueue {
ArrayList list;
MyQueue1() {
this.list = new ArrayList();
}
}
ArrayList를 통한 isEmpty의 경우, list의 사이즈가 0일 경우 true를 반환하고 아닐 경우 false를 반환한다.
public boolean isEmpty() {
if (this.list.size() == 0) {
return true;
} else {
return false;
}
}
public void push(int data) {
this.list.add(data);
}
pop()과 peek()를 구현할 때는 큐가 빈 경우를 꼭 확인해주어야한다. 먼저 구현한 isEmpty를 통해 확인한다.
public Integer pop() {
if (this.isEmpty()) {
System.out.println("Queue is empty!");
return null;
}
int data = (int)this.list.get(0);
this.list.remove(0);
return data;
}
public Integer peek() {
if (this.isEmpty()) {
System.out.println("Queue is empty!");
return null;
}
return (int)this.list.get(0);
}
3) 큐의 구현 - 배열 (원형 큐)
- 원형 큐 관리를 위해 front 값을 처음에 비워두기 때문에 하나 더 크게 만들어야한다.
class MyQueue2 {
int[] arr;
int front = 0;
int rear = 0;
MyQueue2(int size) {
arr = new int[size + 1];
}
}
- 배열이 비어 있을 때, rear와 front가 같은 곳을 가리킨다.
- 또한, rear가 끝인데 길이로 나누었을 때 front 위치일 경우 full. 즉, 큐가 꽉찬 상태이다.
public boolean isEmpty() {
return this.rear == this.front;
}
public boolean isFull() {
return (this.rear + 1) % this.arr.length == this.front;
}
- enqueue 구현 시, 원형 큐 관리를 위해 front는 비워두고, rear을 왼쪽으로 하나씩 옮기면서 값을 넣는다.
- dequeue 구현 시, front 값에 1을 더해 길이로 나눈 값을 front로 하여 해당 위치에 존재하는 값을 반환한다.
public void enqueue(int data) {
if (this.isFull()) {
System.out.println("Queue is full!");
return;
}
this.rear = (this.rear + 1) % this.arr.length;
this.arr[this.rear] = data;
}
public Integer dequeue() {
if (this.isEmpty()) {
System.out.println("Queue is empty!");
return null;
}
front = (front + 1) % this.arr.length;
return this.arr[front];
}
'자료구조' 카테고리의 다른 글
[자료구조] 해시테이블 (0) | 2022.08.17 |
---|---|
[자료구조] 데크 (0) | 2022.08.16 |
[자료구조] 스택 (0) | 2022.08.13 |
[자료구조] 연결리스트 (0) | 2022.08.09 |
[자료구조] 조합 (0) | 2022.08.08 |