원형 Queue(큐)에서의 삽입&삭제 연산

원형 큐(Queue)

• front와 rear의 초기 값은 0으로 설정한다. front와 rear은 시계 방향으로 진행되며, front = rear이 되면 Queue에서는 데이터가 저장되어 있지 않은 빈 상태를 뜻한다.
• 원형 Queue를 유지하기 위해서 mod 연산을 해 주는 %를 사용한다.
• 데이터를 Queue에 삽입하기 위해서는 rear를 하나씩 증가시킬 때 : rear ← (rear+1)%ArraySize
• 데이터를 Queue로부터 삭제할 때 : front ← (front+1)%ArraySize

연결 자료구조를 활용한 연결 Queue에서의 삽입&삭제 알고리즘

연결 자료구조를 활용한 연결 Queue의 삽입 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12

enQueue(LQ, item)
   newnode <- getNode();   
   newnode.data <- item;
   newnode.link <- null;
   if(front=null) then {  
      rear <- newnode;
      front <- newnode;
   } else {   
      rear.link <- newnode;
      rear <- newnode;
   }
end enQueue()

1. newnode ← getNode() : 삽입할 새 노드를 생성하여 데이터 필드에 item을 저장한다.
2. if(front=null) then { ~ } : 새 노드를 삽입하기 전에 연결 Queue가 공백인지 아닌지를 검사한다. 연결 Queue가 공백인 경우에는 삽 입할 새 노드가 Queue의 첫 번째 노드이자 마지막 노드이므로 front와 rear가 모두 새 노드를 가리키도록 설정한다.
3. else { ~ } : Queue가 공백이 아닌 경우, (노드가있는경우) 현재 Queue의 마지막 노드 뒤에새 노드를 삽입한다. 그리고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정한다.

연결 자료구조를 활용한 연결 Queue의 삭제 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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()

Queue에서 삭제 연산은 Queue가 공백이 아닌 경우에만 수행한다.

1. old ← front : front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정한다.
2. front ← front.link : 삭제연산 후에는 현재 front 노드의 다음 노드가 front(첫번째) 노드 가 되어야 하므로 포인트 front를 재설정한다.
3. if(isEmpty(LQ)) then rear ← null : 현재 Queue에 노드가 하나인 경우 삭제연산 이후 공백 Queue가 되는 경우에는 Queue의 마지막 노드가 없어지므로 포인터 rear를 null로 설정한다.
4. returnNode(old) : old가 가리키고 있는 노드를 삭제하여 메모리 공간을 시스템에 반환한다.