기억 장소의 한쪽 끝에서 데이터의 입력이 이루어지고, 다른 한쪽 끝에서 출력이 이루어지는 형태
먼저 삽입한 데이터가 먼저 삭제되는 구조를 가짐
FIFO(First-In First-Out) / 선입선출의 형태
전위 포인터(front)
데이터가 삭제되는 끝을 가리키는 포인터
후위 포인터(rear)
데이터가 삽입되는 끝을 가리키는 포인터
큐에서의 오버플로우(overflow) 해결 방법
후위 포인터 rear의 값이 n과 같을 때 새로운 데이터를 삽입하면 오버플로우 발생
해결 방법
이동 큐 (moving queue)
원형 큐 (circular queue)
이동 큐 (moving queue)
앞부분이 비어있는 경우 큐의 데이터를 앞부분으로 이동
문제: 데이터 이동에 따른 시간적 부담 존재
원형 큐 (circular queue)
선형 큐의 앞(front)과 뒤(rear)를 이어 놓은 형태의 큐
새로운 항목을 삽입하기 위하여 rear를 시계방향으로 증가
큐의 응용
작업 도착 순서에 의한 스케줄링
대표적인 예: 프린터
작업 순서
fornt = 0 작업 A > 작업 B > 작업 C > 작업 D rear = 4
큐의 예제
앞이 비었는데도 오버플로우 발생: 이동 없음
큐 이동해서 오버플로우 해결
java.util.Queue 인터페이스를 LinkedList로 구현
큐 (queue) 예제 1
앞이 비었는데도 오버플로우 발생: 이동 없음
MyQueue.java
package queue;
public class MyQueue {
// 멤버 변수
private int queueSize; // 큐의 용량
private int front; // 전위 포인터. 첫 번째 요소 앞
private int rear; // 후위 포인터. 마지막 요소 값과 동일
private int num; // 현재 데이터 수
private char[] queue; // 큐 본체 (변수 선언만. 아직 할당받지 못함)
// 생성자에서 초기화
public MyQueue(int queueSize){
// 배열 사용하므로 초기값 -1로 설정
front = rear = -1; // 큐가 비어있는 상태임을 의미
num = 0; // 데이터 수
this.queueSize = queueSize;
queue = new char[queueSize];
}
// 큐가 비었는지 상태 확인 isEmpty()
// true / false
public boolean isEmpty() {
// front와 rear 포인터가 같으면 큐가 비어있는 상태
if(front == rear) {
front = rear = -1;
return true;
}
else return false;
}
// 큐가 가득 차있는 상태 확인하는 isFull()
public boolean isFull() {
return rear == queueSize -1;
}
// 큐에 데이터 삽입하는 enqueue()
// (1) Full 인지 확인
// (2) 데이터 삽입
public void enQueue(char item) {
if(isFull()) {
System.out.println("Queue Full.");
}else {
queue[++rear] = item; // rear 다음 위치에 데이터 삽입
num++; // 데이터 수 증가
}
}
// 큐에서 데이터 삭제 deQueue()
// (1) Empty인지 확인
// (2) 데이터 삭제
public char deQueue() {
if(isEmpty()) {
return 'E';
}else{
num--; // 데이터 수 감소
front++; // front 증가 (front 다음 위치 값 삭제)
return queue[front];
}
}
// 큐의 첫 번째 데이터 추출하는 peek()
// 추출해서 반환
public char peek() {
if(isEmpty()){
System.out.println("peek 실패. Empty");
return 'E';
}else {
// front 다음 데이터 추출해서 반환
return queue[front + 1];
}
}
// 큐 초기화하는 clear()
public void clear() {
front = rear = -1;
System.out.println("clear!");
}
// 큐에 들어있는 모든 데이터를 출력하는 showQueue()
public void showQueue() {
if(isEmpty()) {
System.out.println("Queue Empty");
}else {
System.out.print("Queue items : ");
for(int i = front+1; i<=rear; i++){
System.out.print(i + ":" + queue[i] + " ");
}
}
}
// 데이터 개수를 반환하는 numOfData()
public int numOfData() {
return num;
}
}
MyQueueMain.java
package queue;
public class MyQueueMain {
public static void main(String[] args) {
int queueSize = 5;
MyQueue q = new MyQueue(queueSize);
q.showQueue();
System.out.println("데이터 : "+q.numOfData());
System.out.println("\na, b, c enqueue 수행");
q.enQueue('a');
q.enQueue('b');
q.enQueue('c');
q.showQueue();
System.out.println("\n데이터 : "+ q.numOfData());
System.out.println("\npeek 수행 (첫 번째 값) : "+q.peek());
System.out.println("\ndequeue 수행");
System.out.println("삭제된 값: " + q.deQueue());
q.showQueue();
System.out.println("\n데이터: "+q.numOfData());
System.out.println("\npeek 수행 (첫 번째 값) : "+q.peek());
System.out.println("\nd, e enqueue 수행");
q.enQueue('d');
q.enQueue('e');
q.showQueue();
System.out.println("\n데이터 : "+ q.numOfData());
// 현재 큐 상태: 0이 비었고, 1~4까지 4개 데이터가 들어 있음
System.out.println("\nf enqueue 수행");
q.enQueue('f');
q.showQueue();
System.out.println("\n데이터 : "+ q.numOfData());
// 앞 공간이 비었더라도 rear가 stackSize(인덱스 4, 5개)와 동일하면 오버플로우 발생
// 해결1. 이동 큐
// 해결2. 원형 큐
System.out.println("\nclear 수행");
q.clear();
q.showQueue();
System.out.println("\ng enqueue 수행");
q.enQueue('g');
q.showQueue();
}
}
[OUTPUT]
Queue Empty
데이터 : 0
a, b, c enqueue 수행
Queue items : 0:a 1:b 2:c
데이터 : 3
peek 수행 (첫 번째 값) : a
dequeue 수행
삭제된 값: a
Queue items : 1:b 2:c
데이터: 2
peek 수행 (첫 번째 값) : b
d, e enqueue 수행
Queue items : 1:b 2:c 3:d 4:e
데이터 : 4
f enqueue 수행
Queue Full.
Queue items : 1:b 2:c 3:d 4:e
데이터 : 4
clear 수행
clear!
Queue Empty
g enqueue 수행
Queue items : 0:g
큐 예제 2
큐 이동해서 오버플로우 해결
MyQueue 예제에서 다음 변경
QueueMove 클래스
isFull()
rear가 마지막 인덱스와 동일하고, 데이터 수가 stackSize와 동일하면 Full 상태
enQueue()
Full 인지 확인
데이터가 들어있으면 큐 이동: 현재 큐를 복사해서 0 인덱스로 이동
QueueMoveMain( )
출력하는 부분 변경
QueueMove.java - isFull()
public boolean isFull() {
// rear 포인터가 큐의 마지막 인덱스와 동일
// 데이터 수가 queueSize와 동일하면 full 상태
return (rear == queueSize -1 && num == queueSize);
}
QueueMove.java - enQueue()
public void enQueue(char item) {
if(isFull()) {
System.out.println("Queue Full.");
}else if(num != 0 && rear == queueSize -1) {
// rear가 마지막 인덱스와 동일하지만
// 데이터가 1개라도 들어있는 경우
// queue 이동: 현재 queue를 복사해서 시작 인덱스 0으로 덮어 씀
System.arraycopy(queue, front+1, queue, 0, queue.length-1);
System.out.println("큐 이동 발생");
rear--;
front = -1;
queue[++rear] = item; // rear 다음 위치에 데이터 삽입
num++; // 데이터 수 증가
}else {
queue[++rear] = item; // rear 다음 위치에 데이터 삽입
num++; // 데이터 수 증가
}
}
QueueMoveMain.java
package queue;
public class QueueMoveMain {
public static void main(String[] args) {
int queueSize = 5;
QueueMove q = new QueueMove(queueSize);
q.showQueue();
System.out.println("데이터 : "+q.numOfData());
System.out.println("\na, b, c enqueue 수행");
q.enQueue('a');
q.enQueue('b');
q.enQueue('c');
q.showQueue();
System.out.println("\n데이터 : "+ q.numOfData());
System.out.println("\npeek 수행 (첫 번째 값) : "+q.peek());
System.out.println("\ndequeue 수행");
System.out.println("삭제된 값: " + q.deQueue());
q.showQueue();
System.out.println("\n데이터: "+q.numOfData());
System.out.println("\npeek 수행 (첫 번째 값) : "+q.peek());
System.out.println("\nd, e enqueue 수행");
q.enQueue('d');
q.enQueue('e');
q.showQueue();
System.out.println("\n데이터 : "+ q.numOfData());
// 앞 공간이 비었더라도 rear가 stackSize(인덱스 4, 5개)와 동일하면 오버플로우 발생
// 해결1. 이동 큐
// 해결2. 원형 큐
// 이동 큐
System.out.println("\nf enqueue 수행");
q.enQueue('f'); // 큐 이동 발생
q.showQueue(); // Queue items : 0:b 1:c 2:d 3:e 4:f
System.out.println("\n데이터 : "+ q.numOfData()); // 데이터 : 5
System.out.println("\ng enqueue 수행");
q.enQueue('g');
q.showQueue();
System.out.println("\ndequeue 수행");
System.out.println("삭제된 값: " + q.deQueue());
q.showQueue();
System.out.println("\nclear 실행");
q.clear();
q.showQueue();
System.out.println("\nh enqueue 수행");
q.enQueue('h');
q.showQueue();
}
}
[OUTPUT]
Queue Empty
데이터 : 0
a, b, c enqueue 수행
Queue items : 0:a 1:b 2:c
데이터 : 3
peek 수행 (첫 번째 값) : a
dequeue 수행
삭제된 값: a
Queue items : 1:b 2:c
데이터: 2
peek 수행 (첫 번째 값) : b
d, e enqueue 수행
Queue items : 1:b 2:c 3:d 4:e
데이터 : 4
f enqueue 수행
큐 이동 발생
Queue items : 0:b 1:c 2:d 3:e 4:f
데이터 : 5
g enqueue 수행
Queue Full.
Queue items : 0:b 1:c 2:d 3:e 4:f
dequeue 수행
삭제된 값: b
Queue items : 1:c 2:d 3:e 4:f
clear 실행
clear!
Queue Empty
h enqueue 수행
Queue items : 0:h
큐 예제 3
java.util.Queue 사용
Queue 인터페이스를 LinkedList로 구현
ArrayList로 구현할 경우 추가/삭제 시 데이터 이동이 필요하기 때문
QueueLinkedList.java
package queue;
import java.util.LinkedList;
import java.util.Queue;
public class QueueLinkedList {
public static void main(String[] args) {
Queue<String> q = new LinkedList<String >();
// 큐에 추가
System.out.println("큐에 값 4개 삽입");
q.add("김준면");
q.add("김민석");
q.add("정재현");
q.offer("김도영");
System.out.println("큐의 내용 출력");
System.out.println(q); // System.out.println(q.toString());
System.out.println("큐의 크기 : "+ q.size());
System.out.println("peek 수행. 첫 번째 값 출력: "+q.peek());
System.out.println("첫 번째 값 삭제: "+q.remove());
System.out.println("두 번째 값 삭제: "+q.poll());
System.out.println(q);
// remove("검색어")는 검색해서 삭제 가능
System.out.println("검색한 값 없는 경우 : "+ q.remove("김민석"));
System.out.println("검색한 값 없는 경우 : "+ q.remove("김도영"));
System.out.println(q);
}
}
[OUTPUT]
큐에 값 4개 삽입
큐의 내용 출력
[김준면, 김민석, 정재현, 김도영]
큐의 크기 : 4
peek 수행. 첫 번째 값 출력: 김준면
첫 번째 값 삭제: 김준면
두 번째 값 삭제: 김민석
[정재현, 김도영]
검색한 값 없는 경우 : false
검색한 값 없는 경우 : true
데크(deque : double ended queue)
큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있도록 확장한 자료구조
스택과 큐를 하나의 선형 리스트 구조에 복합시킨 형태
end1과 end2 포인터 사용
양쪽 끝에서부터의 오버플로우의 가능성 을 줄이기 위해 데크 내의 중심 근처에서부터 저장 가능
데크의 구현
양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서 변화가 많으므로 순차 자료구조는 비효율적임
양방향으로 연산이 가능한 이중 연결 리스트 사용
데크 예제
java.util.Deque 인터페이스 사용해 구현
DequeArray.java
package queue;
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeArray {
public static void main(String[] args) {
Deque<String> dq = new ArrayDeque<String >();
System.out.println("데이터 3개 삽입");
dq.add("포도");
dq.add("바나나");
dq.add("딸기");
dq.offer("사과");
System.out.println(dq);
System.out.println("앞 쪽에 삽입");
dq.addFirst("수박");
System.out.println(dq);
System.out.println("삽입");
dq.add("복숭아");
System.out.println(dq);
// 동일한 값 삽입 가능
dq.add("복숭아");
System.out.println(dq);
System.out.println("peek 수행: "+dq.peek());
System.out.println("데크 사이즈: "+dq.size());
System.out.println("데크 순회");
for(String item :dq){
System.out.print(item + " ");
}
System.out.println("데이터 꺼내기");
System.out.println("remove : "+dq.remove());
System.out.println(dq);
// 찾아서 삭제
System.out.println("사과 remove : "+dq.remove("사과"));
System.out.println(dq);
System.out.println("앞 쪽에 삽입");
dq.addFirst("복숭아");
System.out.println(dq);
// 앞의 데이터를 먼저 지우는 것 확인 가능
System.out.println("복숭아 remove : "+dq.remove("복숭아"));
System.out.println(dq);
System.out.println("removeAll : "+dq.removeAll(dq));
System.out.println(dq);
}
}
