먼저 들어간 데이터가 먼저 나오는 구조 (선입선출) (FIFO, First-In, First-Out)
마트에서 계산 대기할 때, 영화관 입장 시 등등
데이터 삽입 시 위치를 알기 위한 Rear 변수 필요 데이터 반환 시 위치를 알기 위한 Front 변수 필요
데이터 삽입과 반환이 이루어지는 위치가 다름 (스택은 동일한 위치에서 pop과 push가 이루어지지만, 큐는 Rear, Front를 통해 위치를 알아내야 함)
추상자료형 (ADT)
자료형
반환값
설명
initialize()
void
큐(Queue) 초기화
isEmpty()
boolean
큐가 비어있는지 확인
enqueue(Data)
void
큐에 데이터 삽입
dequeue()
Data
맨 앞에 있는 데이터 반환 및 삭제
peek()
Data
맨 앞에 있는 데이터 반환 후 삭제하지 않음
배열기반 큐 구현
삽입
삭제
삭제 과정의 문제점 - 아래와 같이 Rear가 배열의 끝까지 이동했지만, 삭제된 공간에는 데이터가 저장되지 않음
- dequeue 시 삭제된 빈 공간을 뒤에 데이터들이 채워줘야하는데, 잦은 데이터의 이동이 발생할 경우 성능에 문제가 생길 수 있어 이를 해결하기 위해 front와 rear의 위치만 변경하도록 해야함
해결방법 - rear와 front가 가리키는 인덱스가 배열의 크기보다 클 경우 front또는 rear값을 0으로 설정하여 배열의 첫번째를 가리킬 수 있도록 함 (원형 큐)
구현 Queue 인터페이스 구현
package Queue;
public interface Queue {
// 큐(Queue) 초기화
void initialize();
// 비어있는지 확인
boolean isEmpty();
// 큐에 데이터 삽입
void enqueue(Object data);
// 큐의 맨 앞에있는 데이터 반환 후 삭제
Object dequeue();
// 큐의 맨 앞에있는 데이터 반환 후 삭제하지 않음
Object peek();
}
Queue 구현
package Queue.Array;
import Queue.Queue;
public class ArrayQueue implements Queue {
private final static int QUEUE_SIZE = 5;
int frontIndex = 0;
int rearIndex = 0;
int countOfData = 0;
Object[] queue = null;
@Override
public void initialize() {
queue = new Object[QUEUE_SIZE];
frontIndex = 0;
rearIndex = 0;
countOfData = 0;
}
@Override
public boolean isEmpty() {
if (countOfData == 0){
return true;
}
return false;
}
@Override
public void enqueue(Object data) {
if (countOfData == QUEUE_SIZE){
System.out.println("더이상 데이터를 추가할 수 없습니다.");
return;
}
// 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 rear를 0으로 초기화
if (rearIndex == QUEUE_SIZE){
rearIndex = 0;
}
countOfData++;
queue[rearIndex++] = data;
}
@Override
public Object dequeue() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
// 배열의 끝까지 간 경우 배열의 맨 앞을 가리키도록 front를 0으로 초기화
if (frontIndex == QUEUE_SIZE){
frontIndex = 0;
}
countOfData--;
return queue[frontIndex++];
}
@Override
public Object peek() {
if (countOfData == 0){
System.out.println("데이터가 없습니다.");
return null;
}
return queue[frontIndex];
}
}
테스트 구현
package Queue.Array;
import Queue.Queue;
public class ArrayQueueMain {
public static void main(String[] args) {
Queue queue = new ArrayQueue();
queue.initialize();
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
// 데이터 삽입 후 출력
System.out.println("데이터 삽입 후 출력");
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
System.out.println("데이터 삭제 후 하나 추가 출력 ");
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
queue.dequeue();
queue.enqueue(6);
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
}
}
연결 리스트 기반 큐 구현
배열 기반의 큐와 동일하게 front와 rear 변수 필요
삽입 시 첫 번째 노드와 두 번째 이후의 노드 추가 과정이 다름
삽입
삭제 - front로 큐가 비어있는지 판별할 수 있기 때문에 삭제 시 rear는 신경쓰지 않아도 됨
구현
- 인터페이스는 동일하게 구현
LinkedList 큐 구현
package Queue.LinkedList;
import Queue.Queue;
public class LinkedListQueue implements Queue {
class Node {
Object data;
Node nextNode;
}
Node front = null;
Node rear = null;
int countOfData = 0;
@Override
public void initialize() {
front = null;
rear = null;
countOfData = 0;
}
@Override
public boolean isEmpty() {
if (front == null){
return true;
}
return false;
}
@Override
public void enqueue(Object data) {
Node newNode = new Node();
newNode.data = data;
// 큐가 비어있는 경우 첫 번째 노드 추가
if (isEmpty()){
front = newNode;
rear = newNode;
}
// 두 번째 이후의 노드 추가일 경우 rear의 다음 node 주소를 설정 후 rear값 변경
else {
rear.nextNode = newNode;
rear = newNode;
}
countOfData++;
}
@Override
public Object dequeue() {
if (isEmpty()){
System.out.println("데이터가 없습니다.");
return null;
}
// 제일 앞 쪽 데이터 반환
Object data = front.data;
// front의 다음 노드를 front로 변경
front = front.nextNode;
return data;
}
@Override
public Object peek() {
if (isEmpty()){
System.out.println("데이터가 없습니다.");
return null;
}
return front.data;
}
}
테스트 구현
package Queue.LinkedList;
import Queue.Queue;
public class LinkedListQueueMain {
public static void main(String[] args) {
Queue queue = new LinkedListQueue();
queue.initialize();
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
// 데이터 삽입 후 출력
System.out.println("데이터 삽입 후 출력");
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
System.out.println("데이터 삭제 후 하나 추가 출력 ");
queue.enqueue(1);queue.enqueue(2);
queue.enqueue(3);queue.enqueue(4);
queue.enqueue(5);
queue.dequeue();
queue.enqueue(6);
while(!queue.isEmpty()){
System.out.println(queue.dequeue());
}
}
}
