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

큐(Queue)

• 은행에서 대기번호를 받을 때 먼저 대기표를 받고 자신의 차례를 기다린다. 이후 순서가 돌아오면 번호표대로 업무를 보기 시작하는데 이와 같은 구조는 선입선출(FIFO) 구조를 지닌 큐(Queue)와 동일하다.
• 프린트는 사용자가 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청한 것을 먼저 인쇄한다. 이와 같은 구조는 선입선출(FIFO) 구조를 가진 큐(Queue)와 동일하다.

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

큐(Queue)에서의 삽입 연산 알고리즘

1
2
3
4
5
6
7
8

enQueue(Queue, data)
	if(rear > n) then 
		return overflow;
	else {
			rear ← rear + 1;
			Queue[rear] ← data;
	}
end enQueue()

1. if(rear > n) : rear 값이 배열 인덱스 범위를 초과 할 경우 데이터를 삽입할 공간이 없으므로 overflow를 반환하고 삽입 연산을 수행하 지 않는다.
2. rear ← rear + 1 : 마지막 원소의 인덱스를 저장한 rear의 값을 하나 증가시켜 다음 삽입 연산에 필요한 공간을 준비한다.
3. Queue[rear] ← data : 인덱스에 해당되는 배열원소 Queue[rear]에 data를 저장한다.

큐(Queue)에서의 삭제 연산 알고리즘

1
2
3
4
5
6
7
8
9

deQueue(Queue)
	if(front = rear) then
		return underflow;
	else {
			front ← front + 1;
			delete_data ← Queue[front];
			return Queue[front];
	}
end deQueue()

1. if(front = rear) : 맨 앞 위치(front)와 맨 뒤 위치(rear)가 같을 경우 큐(Queue)는 공백이므로 Underflow를 반환하고 연산을 종료한다.
2. front ← front + 1 : front의 위치를 하나 뒤로 이동하여 다음 삭제 연산을 준비한다.
3. delete_data ← Queue[front] : front 인덱스의 있는 데이터를 삭제한다.
4. return Queue[front] : front 인덱스의 공간을 반환한다.