연결 큐와 데크

728x90

반응형

SMALL

연결 큐	연결 리스트를 이용한 큐의 구현이다. 큐의 원소들을 링크로 연결하여 표현한다.
데크	큐 두 개 중 하나를 좌우로 뒤집어서 붙인 구조, 큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있도록 확장한 자료구조이다.
스케줄링 큐	cpu 사용을 요청한 프로세스들의 순서를 스케줄링 하기 위해서 큐를 사용한다.

---

단순 연결 리스트를 이용한 큐

○ 큐의 원소 : 단순 연결 리스트의 노드

○ 큐의 원소의 순서 : 노드의 링크 포인터로 연결

○ 변수 front : 첫 번째 노드를 가리키는 포인터 변수

○ 변수 rear : 마지막 노드를 가리키는 포인터 변수

 

상태 표현

초기 상태와 공백 상태 : front = rear = null

 

단순 연결 리스트를 이용한 큐 : 연결 큐의 구조

---

공백 연결 큐 생성 알고리즘

---

연결 큐의 공백 상태 검사 알고리즘

삭제 연산을 할때 공백인지 아닌지 검사해야된다.

---

연결 큐의 삽입 알고리즘

배열은 크기를 정해놓기 때문에 full인지 체크해야되지만, 연결 큐는 메모리가 있는 동안은 새 노드를 계속 만들어서 사용할 수 있기 때문에 full인지 체크를 안해도 된다.

 

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

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

 

 

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

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

 

 

③ 큐가 공백이 아닌 경우, 즉 노드가 있는 경우에는

현재 큐의 마지막 노드의 뒤에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정

---

연결 큐의 원소 삭제 알고리즘

 

① 삭제 연산에서 삭제할 노드는 큐의 첫 번째 노드로, 포인터 front가 가리키고 있는 노드

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

 

 

② 삭제 연산 후에는

현재 front 노드 다음 노드(front.link)가 front 노드가 되어야 하므로 포인터 front를 재설정 

 

 

③ 현재 큐에 노드가 하나뿐이어서 재설정한 front가 NULL이 되는 경우에는

삭제 연산 후에 공백 큐가 되므로 포인터 rear를 NULL로 설정

 

④ 포인터 old가 가리키고 있는 노드를 삭제하여

메모리 공간을 시스템에 반환 (returnNode())

---

연결 큐의 원소 검색 알고리즘

연결 큐의 첫 번째 노드, 즉 front 노드의 데이터 필드 값을 반환

---

연결 큐에서의 연산 과정 

---

데크 (Deque : double-ended queue)

큐 두 개 중 하나를 좌우로 뒤집어서 붙인 구조,

큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있도록 확장한 자료구조  

 

---

데크의 연산 과정

---

데크의 구현

양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서 변화가 많으므로 순차 자료구조는 비효율적임

양방향으로 연산이 가능한 이중 연결 리스트를 사용

---

큐의 응용

운영체제의 작업 큐

● 프린터 버퍼 큐 (Printer Buffer Queue)

CPU에서 프린터로 보낸 데이터 순서대로(선입선출) 프린터에서 출력하기 위해서 선입선출 구조의 큐 사용

 

● 스케줄링 큐 (Scheduling Queue)

CPU 사용을 요청한 프로세서들의 순서를 스케줄링 하기 위해서 큐를 사용 

 

\

 

 

●  시뮬레이션에서의 큐잉 시스템

시뮬레이션을 위한 수학적 모델링에서 대기행렬과 대기시간 등을 모델링 하기 위해서 큐의 이론(Queue theory) 사용

---