큐(Queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣는 데이터가 먼저
나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 Queue는 표를 사러 이렬ㄹ로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저
나갈 수 있는 상황을 연상하면 된다.
나중에 집어 넣는 데이터가 먼저 나오는 스택과는 반대 개념
Ex) 프린터의 출력 처리, 은행 처리 등
- 즉 쉽게 얘기하면 순서 있는 리스트다.
- 큐는 put(Insert) 와 get(delete)을 이용하여 구현된다.
- put은 큐에 자료를 넣는 것을 의미하며, get은 자료를 꺼내는 것을 의미한다.
- front(head)와 rear(tail)는 데이터의 위치를 나타낸다.
- 큐에 Data를 넣는 동작을 EnQueue(인큐) , 제거하는 동작을 DeQueue(디큐)라 한다.
- 빈 큐에서 디큐하려고 하는 것을 언더플로우(Underflow)라고 부르고, 큐가 가득찬
상태에서 인큐하려고 하는 것을 오버플로우(Overflow)라고 한다.(예외처리)
큐의 종류
1. 선형 큐
- 기본적인 큐의 형태
- 막대 모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면
모든 자료를 꺼내거나 자료를 한칸 씩 옮겨야 한다는 단점이 있다.
선형 큐의 데이터 삽입 및 삭제
선형 큐 예제
public class QueueDemo {
private static final int capacity = 3;
int arr[] = new int[capacity];
int size = 0;
int top = -1;
int rear = 0;
public void push(int pushedElement) {
if (top < capacity - 1) {
top++;
arr[top] = pushedElement;
System.out.println("Element " + pushedElement
+ " is pushed to Queue !");
display();
} else {
System.out.println("Overflow !");
}
}
public void pop() {
if (top >= rear) {
rear++;
System.out.println("Pop operation done !");
display();
} else {
System.out.println("Underflow !");
}
}
public void display() {
if (top >= rear) {
System.out.println("Elements in Queue : ");
for (int i = rear; i <= top; i++) {
System.out.println(arr[i]);
}
}
}
public static void main(String[] args) {
QueueDemo queueDemo = new QueueDemo();
queueDemo.pop();
queueDemo.push(23);
queueDemo.push(2);
queueDemo.push(73);
queueDemo.push(21);
queueDemo.pop();
queueDemo.pop();
queueDemo.pop();
queueDemo.pop();
}
}
2. 원형 큐
선형 큐의 문제점을 보완하고자 나왔다.
작업 큐에서 MAX_QUEUE_SIZE 만큼 원소가 삽입되면 큐가 Full 이 된다.
따라서 원형 큐는 front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어
원형으로 연결하는 방식이다.
원형 큐 Ex)
public class CircularQueue {
// 큐 배열은 front와 rear 그리고 maxSize를 가진다.
private int front;
private int rear;
private int maxSize;
private Object[] queueArray;
// 큐 배열 생성
public CircularQueue(int maxSize){
this.front = 0;
this.rear = -1;
// 실제 크기보다 하나 크게 지정한다 (공백과 포화를 막기 위함)
this.maxSize = maxSize+1;
this.queueArray = new Object[this.maxSize];
}
// 큐가 비어있는지 확인
public boolean empty(){
return (front == rear+1) || (front+maxSize-1 == rear);
}
// 큐가 꽉 찼는지 확인
public boolean full(){
return (rear == maxSize-1) || (front+maxSize-2 == rear);
}
// 큐 rear에 데이터 등록
public void insert(Object item){
if(full()) throw new ArrayIndexOutOfBoundsException();
// rear 가 배열의 마지막이면 rear 포인터를 앞으로 돌린다.
if(rear == maxSize-1){
rear = -1;
}
queueArray[++rear] = item;
}
// 큐에서 front 데이터 조회
public Object peek(){
if(empty()) throw new ArrayIndexOutOfBoundsException();
return queueArray[front];
}
// 큐에서 front 데이터 제거
public Object remove(){
Object item = peek();
front++;
// front의 다음 index가 배열크기+1 이면 처음으로 돌아간다
if(front==maxSize){
front = 0;
}
return item;
}
}
3. 우선순위 큐
우선순위 큐는 데이터의 우선순위에 따라 우선순위가 높은 데이터부터 꺼내도록
만들어진 큐.
데이터를 삽입할 때 우선순위에 따라 정렬하여 삽입한 후 한쪽 방향에서만 데이터를
꺼내어 쓰도록 작성하면 된다.
우선순위 큐 예제
public class PriorityQueue {
private int maxSize;
private long[] queueArray;
private int count;
// 큐 배열 생성
public PriorityQueue(int maxSize){
this.maxSize = maxSize;
this.queueArray = new long[maxSize];
this.count=0;
}
// 큐가 비어있는지 확인
public boolean empty(){
return (count==0);
}
// 큐가 꽉 찼는지 확인
public boolean full(){
return (count==maxSize);
}
// 큐에 데이터 등록
// 큐가 데이터가 큰 순서대로 배열의 앞에서부터 정렬되있기에
// 배열의 뒤에서부터 탐색하며 item 보다 큰 값이 있는 index 뒤에 삽입한다.
public void insert(long item){
if(full()) throw new ArrayIndexOutOfBoundsException();
if(empty()){
queueArray[count++] = item;
}else{
// 데이터의 뒤에서부터 앞으로 탐색한다.
int i=0;
for(i=count-1; i>=0; i--){
// 현재 index의 데이터가 입력받은 데이터(item)보다 작으면 배열의 뒤로 밀어낸다.
if(item > queueArray[i]){
queueArray[i+1] = queueArray[i];
}else{
// item이 현재 index의 값보다 작으면 탐색을 멈춘다.
// item 삽입 위치 확인
break;
}
}
// item 등록
queueArray[i+1] = item;
count++;
}
}
// 큐의 마지막 데이터 조회 (가장작은 데이터)
public Object peek(){
if(empty()) throw new ArrayIndexOutOfBoundsException();
return queueArray[count-1];
}
// 큐에서 마지막 데이터 제거 (가장작은 데이터)
public Object remove(){
Object item = peek();
count--;
return item;
}
}
댓글 없음:
댓글 쓰기