연결 큐(연결리스트 큐)

<연결 큐(연결리스트 큐)>

[연결 큐 알고리즘]

1. 공백 연결 큐 생성

createLinkedQueue()

   front <- null;

   rear <- null;

end createLinkedQueue()

2. 공백 연결 큐 검사

isEmpty(LQ)

   if(front=null) then return true;

   else return false;

end isEmpty()

3. 연결 큐의 삽입

enQueue(LQ, item)

   new <- getNode();   // ⓐ

   new.data <- item;

   new.link <- null;

   if(front=null) then {  // ⓑ

      rear <- new;

      front <- new;

   }

   else {   // ⓒ

      rear.link <- new;

      rear <- new;

   }

end enQueue()

 

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

ⓑ 새 노드를 삽입하기 전에 연결 큐가 공백인지 아닌지를 검사

ⓒ 큐가 공백이 아닌경우, (노드가 있는 경우) 현재 큐의 마지막 노드의 다음에 새 노드를 삽입하고 마지막 노드를 가리키는 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()

​

​①  old <- front;

front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정한다.

② front <- front.link;

 

삭제연산 후에는 현재 front 노드의 다음 노드가 front 노드(첫번째 노드)가 되어야 하므로, 포인터 front를 재설정한다.​ 

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

현재 큐에 노드가 하나뿐이어서 삭제연산 후에 공백 큐가 되는 경우 큐의 마지막 노드가 없어지므로 포인터 rear를 null로 설정한다.​

④ ​returnNode(old);

포인터 old가 가리키고 있는 노드를 삭제하고, 메모리 공간을 시스템에 반환한다​

삭제만 하는 연산

/*

delete(LQ)

   if(isEmpty(LQ) then Queue_Empty();

   else {

      old <- front;

      front <- front.link;

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

      returnNode(old);

   }

end delete()

*/

 

 

5. 연결 큐의 검색

peek(LQ)

   if(isEmpty(LQ)) then Queue_Empty()

   else return (front.data);

end peek()

​

​

 

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)