본문 바로가기

java

연결큐

순차 자료구조 방식에는 몇가지 문제가 있다.

 - 사용 크기가 제한되어 있어서 큐의 길이를 마음대로 변경할 수 없다.

 - 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리도 낭비 된다.


연결큐의 알고리즘


1. 공백 연결 큐 생성

createLinkedQueue()

   fornt <- null;

   rear <- null;

end createLinkedQueue()   


 - 삽입할 새 노드를 생성하여 데이터 필드에 item을 저장.

 - 삽입할 새 노드는 연결 큐의 마지막 노드가 되어야 하므로 링크 필드에 null을 저장



2. 공백 연결 큐 검사

isEmpty(LQ)

if(front=null) then return true;

else return false;

end isEmpty()

 

- 새 노드를 삽입하기 전 연결 큐가 공백인지 검사

- 연결 큐가 공백인 경우에 삽입할 새 노드가 큐의 첫 번째 노드이자 마지막 노드이므로 참조변수 front와 rear가 모두 새 노드를 가리키도록 설정




3. 연결 큐의 삽입 알고리즘

enQueue(LQ, item)

new <- getNode();

new.data <- item;

new.link <- null;


if (isEmpty(LQ) then {

rear <- new;

front <- new;

} else {

rear.link <- new;

rear <- new;

end enQueue()


 - 큐가 공백이 아닌경우 현재 큐의 마지막 노드의 뒤에 새 노드를 삽입

 - 마지막 노드를 가리키는 rear 가 삽입한 새노드를 가리키게 한다.




4. 연결 큐의 삭제 알고리즘

deQueue(LQ)

   if(isEmpty(LQ)) then Queue_Empty();

   else {

      old <- front;          // ①

      item <- front.data;

      front <- front.link;   // ②

      if (isEmpty(LQ)) then rear <- null;  // ③

      returnNode(old);     // ④

      return item;

}

end deQueue()


delete(LQ)

if(isEmpty(LQ) then Queue_Empty();

else {

old <- front;

front <- front.link;

if (isEmpty(LQ) then rear <- null;

returnNode(old);

}

end delete()


- 삭제할 노드는 front가 가리키고 있는 첫 번째 노드

- front가 가리키는 노드를 참보변수 old가 가리키게 하여 삭제할 노드 지정



 - 삭제 연산 후에는 현재 front 노드의 다음 노드가 front가 되어야 하므로 front를  그 다음 노드(front.link)로 재설정

 

 


 - 현재 큐에 노드가 하나뿐이어서 재설정한 fornt가 null이 되는 경우에는 삭제 연산 후에 공백 큐가 될 것이므로 rear 를 null로 설정


 - old가 가리키고 있는 노드를 삭제하여 메모리 공간을 시스템에 반환 



5. 연결 큐의 검색 알고리즘


peek(LQ)

if(isEmpty(LQ)) then Queue_Empty()

else return (front,data);

end peek()


 - 큐에서 검색 연산은 항상 큐의 첫번째 노드, 즉 front 노드의 데이터 필드 값을 반환



소스 


public interface Queue {
boolean isEmpty();
void enQueue(char item);
char deQueue();
void delete();
char peek();
}


public class LinkedQueue implements Queue {
private QNode front;
private QNode rear;

public LinkedQueue() {
front = null;
rear = null;
}

@Override
public boolean isEmpty() {
return (front == null);
}

@Override
public void enQueue(char item) {
QNode newNode = new QNode();
newNode.data = item;
newNode.link = null;

if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.link = newNode;
rear = newNode;
}

System.out.println("InsertItem Item" + item);
}

@Override
public char deQueue() {
if (isEmpty()) {
System.out.println("Deleteing fail.");
return 0;
}

char item = front.data;
front = front.link;

if (front == null) {
rear = null;
}

return item;
}

@Override
public void delete() {
if (isEmpty()) {
System.out.println("Deleting fail!");
}

front = front.link;

if (front == null) {
rear = null;
}
}

@Override
public char peek() {
if (isEmpty()) {
System.out.println("Peeking Fail!");
return 0;
}

return front.data;
}

public void printQueue() {
if (isEmpty()) {
System.out.println("Linked Queue is Empty.");
}

QNode temp = front;
System.out.printf("Linked Queue>> ");

while(temp != null) {
System.out.printf("%c", temp.data);
temp = temp.link;
}

System.out.println();
System.out.println();
}

public static void main(String[] args) {
char deletedItem;
LinkedQueue lq = new LinkedQueue();

lq.enQueue('A');
lq.printQueue();

lq.enQueue('B');
lq.printQueue();

deletedItem = lq.deQueue();

if (deletedItem != 0){
System.out.println("delete Item : " + deletedItem);
}

lq.printQueue();

lq.enQueue('C');
lq.printQueue();

deletedItem = lq.deQueue();

if (deletedItem != 0){
System.out.println("delete Item : " + deletedItem);
}

lq.printQueue();

deletedItem = lq.deQueue();

if (deletedItem != 0){
System.out.println("delete Item : " + deletedItem);
}

lq.printQueue();

deletedItem = lq.deQueue();

if (deletedItem != 0){
System.out.println("delete Item : " + deletedItem);
}

lq.printQueue();

}
public class QNode {
char data;
QNode link;
}


'java' 카테고리의 다른 글

이진 탐색 트리  (0) 2017.11.15
Deque(Double-ended Queue)  (0) 2017.11.15
원형 큐  (0) 2017.11.15
Queue는 무엇인가?  (0) 2017.11.15
배열과 리스트  (0) 2017.11.15