원형큐 ( Circular Queue )
- 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조 입니다. 선형큐의 문제점은 rear가 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할수가 없었습니다.
public class Circular_Queue {
int rear = 0; //최초 0에서부터 시작
int front = 0; //최초 0에서부터 시작
int maxsize = 0; //배열의 크기
int[] circular_Queue; //배열
public Circular_Queue(int maxsize)
{
this.maxsize = maxsize;
circular_Queue = new int[this.maxsize];
}
public boolean Isempty() //배열이 공백 상태인지 체크하는 메서드입니다.
{
if(rear == front)
{
return true;
}
return false;
}
public boolean Isfull() //배열이 포화 상태인지 체크하는 메서드입니다.
{
if((rear+1)%maxsize == front)
{
return true;
}
return false;
}
public void EnQueue(int num)
{
if(Isfull()) //배열이 포화상태일경우
{
System.out.println("큐가 가득 찼습니다");
}
else //배열이 포화상태가 아닐경우
{
rear = (rear+1) % maxsize;
circular_Queue[rear]=num;
}
}
public int DeQueue()
{
if(Isempty()) //배열이 공백상태이면 -1반환
{
return -1;
}
else //배열이 공백상태가 아니라면
{
front = (front+1)%maxsize;
return circular_Queue[front];
}
}
}
링크드리스트를 이용하여 큐 구현
원형큐를 이용하여 선형큐의 단점을 극복하였지만, 원형큐의 경우도 원소가 없을 때도 배열의 크기를
유지하고 있어야하므로 메모리 낭비가 있을수 있다는 단점이 있다.
public class LinkedQueue{
Node front;
Node rear;
public class Node {
int data;
Node next;
}
public LinkedQueue() {
front = null;
rear = null;
}
@Override
public boolean isEmpty() {
return (front==null);
}
@Override
public void enQueue(int item) {
QueueNode node = new QueueNode(item);
if(isEmpty()){ // 처음 만든 경우는 font rear 같은 노드로 설정
front = node;
rear = node;
}else{
rear.next = node;
rear = node;
}
}
@Override
public char deQueue() {
if(isEmpty()){
System.out.println("큐의 내용이 존재하지 않습니다.");
return 0;
}else{
int item = front.item;
front = front.next;
if(front==null){ // 삭제전 front 랑 rear 같은 위치에 있었던 경우 해당 노드가 삭제됬으니 rear null
rear=null;
}
return item;
}
}
원형큐 ( Circular Queue )
링크드리스트를 이용하여 큐 구현
원형큐를 이용하여 선형큐의 단점을 극복하였지만, 원형큐의 경우도 원소가 없을 때도 배열의 크기를
유지하고 있어야하므로 메모리 낭비가 있을수 있다는 단점이 있다.