9-2 연결 큐와 데크

1. 연결 큐의 이해와 구현

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

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

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

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

 

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

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

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

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

  -  현재 큐에 노드가 하나뿐이어서 재설정한 front가 niull이되는 경우에는 삭제 연산 후에 공백 큐가 되므로 포인터 rear를 Null로 설정

③ 연결 큐에서의 연산 과정

2. 데크의 개념과 구현

① 데크

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

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

②데크의 연산 과정

③ 데크의 구현

  - 양쪽 끝에서 삽입, 삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서변화가 많으므로

    순차 자료구조는 비효율적임!

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

3. 큐의 응용

① 운영체제의 작업 큐

  - 프린터 버퍼 큐

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

  - 스케줄링 큐

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

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

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