※ 큐의 구현
- 배열을 사용하는 순차 자료구조 방식과 참조변수를 사용하는 연결 자료구조 방식이 있다.
- 초기 큐를 생성하면 rear와 front는 모두 -1이다.
- rear와 front 가 같으면 큐에는 값이 없는상태이다.
- 생성, 공백 큐 검사, 삽입, 삭제, 검색기능이 있다.
※ 선형 큐 구현 소스(순차 자료구조를 이용해 구현)
Interface
public interface Queue {
boolean isEmpty();
boolean isFull();
void enQueue(char item);
char deQueue();
void delete();
char peek();
}
ArrayQueue
public class ArrayQueue implements Queue {
private int rear;
private int front;
private int queueSize;
private char dataArray[];
public arrayQueue(int queueSize) {
this.queueSize = queueSize;
this.rear = -1;
this.front = -1;
this.dataArray = new char[queueSize];
}
@Override
public boolean isEmpty() {
if(front == rear){
return true;
}else{
return false;
}
}
public boolean isFull(){
if(rear == queueSize-1){
return true;
}else{
return false;
}
}
@Override
public void enQueue(char item) {
if(isFull()){
System.out.println("Queue is Full");
return;
}else{
dataArray[++rear] = item;
}
}
@Override
public char deQueue() {
if(isEmpty()){
System.out.println("Queue is Empty");
return 0;
}else{
return dataArray[++front];
}
}
@Override
public void delete() {
front ++;
}
@Override
public char peek() {
return dataArray[front+1];
}
public void printQueue(){
for(int i= front+1; i<=rear;i++){
System.out.print("value : "+ dataArray[i] + " ");
}
System.out.println();
}
}
Main
public class Main {
public static void main(String[] args) {
int queueSize =3;
char deletedItem;
ArrayQueue aq = new ArrayQueue(queueSize);
aq.enQueue('A');
aq.printQueue();
aq.enQueue('B');
aq.printQueue();
deletedItem = aq.deQueue();
System.out.println(deletedItem);
aq.printQueue();
aq.enQueue('C');
aq.printQueue();
deletedItem = aq.deQueue();
System.out.println(deletedItem);
aq.printQueue();
deletedItem = aq.deQueue();
deletedItem = aq.deQueue();
}
}
※ 원형 큐 구현 소스(순차 자료구조를 이용해 구현)
선형 큐에서는 rear = QueueSize-1 이면 가득 찬 상태가 된다. 그래서 삽입연산이 수행되지 않는다.
또한 아래 그림에서 처럼 배열의 앞이 비었음에도 포화상태로 인식하고 삽입연산을 수행하지 않는다.
만약 삽입연산을 수행하려면 배열 앞부분으로 이동시켜서 위치를 조정해줘야 한다. 하지만 이러한 작업은 연산이 복잡하여
큐의 효율성을 떨어뜨린다.(오버헤드를 수반하여 큐의 효율을 떨어뜨림)
이러한 큐의 문제를 해결하기 위해 원형 큐를 사용한다. 원형 큐는 논리적으로 배열의 처음과 끝이 연결되어 있다고 생각하는 것이다.
- 원형 큐에서 초기 공백 상태일 때 front와 rear의 값이 0이다.
- 포화상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둔다.(ex. front의 값을 항상 비워두도록 하여 rear가 front 전에 위치하면 포화상태)
- 원형큐에서는 삽입할 자리를 정하기 위해 나머지 연산자 mod를 사용한다.
Interface
public interface Queue {
boolean isEmpty();
boolean isFull();
void enQueue(char item);
char deQueue();
void delete();
char peek();
}
CircularQueue
public class CircularQueue implements Queue{
private int queueSzie;
private int front;
private int rear;
private char dataArray[];
public CircularQueue(int queueSize) {
this.queueSzie = queueSize;
this.front = 0;
this.rear =0;
this.dataArray = new char[queueSize];
}
@Override
public boolean isEmpty() {
if(rear == front ){
return true;
}else{
return false;
}
}
@Override
public boolean isFull() {
if((rear+1)%queueSzie == front){
return true;
}else{
return false;
}
}
@Override
public void enQueue(char item) {
if(isFull()){
System.out.println("Queue is full");
return;
}else{
rear = (rear +1)%4;
dataArray[rear] = item;
}
}
@Override
public char deQueue() {
if(isEmpty()){
System.out.println("Queue is empty");
return 0;
}else{
front = (front + 1)%queueSzie;
return dataArray[front];
}
}
@Override
public void delete() {
rear = (rear+1)%queueSzie;
}
@Override
public char peek() {
return dataArray[(front+1)%queueSzie];
}
public void printQueue(){
for(int i = (front+1)%queueSzie ; i !=rear ; i = (i+1)%queueSzie){
System.out.print("value : "+ dataArray[i] + " ");
}
System.out.println("value : " + dataArray[rear]);
}
}
Main
public class Main {
public static void main(String[] args) {
int queueSize = 4;
char deleteItem;
CircularQueue cq = new CircularQueue(queueSize);
cq.enQueue('A');
cq.printQueue();
cq.enQueue('B');
cq.printQueue();
deleteItem = cq.deQueue();
System.out.println(deleteItem);
cq.printQueue();
cq.enQueue('C');
cq.printQueue();
cq.enQueue('D');
cq.printQueue();
cq.enQueue('E');
cq.printQueue();
}
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 04-4 큐의 응용 (0) | 2016.11.25 |
|---|---|
| 04-3 큐의 구현(연결 자료구조 방식을 이용한 큐) (0) | 2016.11.25 |
| 04-1 큐(Queue) (0) | 2016.11.25 |
| 03-4 스택의 응용 (0) | 2016.11.25 |
| 03-3 스택의 구현(연결 자료구조 방식) (0) | 2016.11.25 |
