[자료구조] chap5. 큐

5.1 큐 추상 데이터 타입

-먼저 들어온 데이터가 먼저 나가는 구조(선입선출, FIFO) : 뒤에서 새로운 데이터 추가, 앞에서 데이터 하나씩 삭제.
*스택은 삽입삭제가 같은 곳에서 일어나지만 큐는 다른 쪽에서 일어남

 
 
 

삽입연산: enqueue / 삭제연산: dequeue

삽입삭제에 쓰이는 변수: 스택에서는 top이라는 변수 1개 존재, 큐에서는 삽입-rear, 삭제-front 사용 (배열과 연결리스트로 구현)
 

5.2 선형큐

ex. 1차원 배열 쓰는 방법 : (정수저장큐 만든다 가정) 먼저 정수 1차원 배열 정의 - > 삽입, 삭제 위한 변수 front와 rear 만듦

ㄴ front 와 rear의 초기값 : -1 (같음) .
[실행]
데이터 증가> rear 하나 증가>그 위치에 데이터 저장
삭제할 때도 front 하나 증가> front가 가리키는 위치에 있는 데이터 삭제
 
[선형큐의 응용: 작업 스케줄링]
 
운체에서 우선순위 갖지 않는 많은 작업 순서대로 처리 

 

5.3 원형큐

• 문제점: front와 rear값 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달> 배열 앞부분 비어있어도 사용을 못함 > 주기적으로 모든 요소 왼쪽으로 이동시켜야 함 >시간+복잡도 문제 발생 ...

 
 
>> 배열을 원형으로 생각하면 쉽게 해결(처-끝 연결돼있다고 생각. but 개념상으로만 원형으로 만들어주는거임)
 
 
 
 
 
 
 
 
 
 
 

 
 

• 초기값: -1이 아닌 0
• front: 큐의 첫번째 요소 하나 앞, rear은 마지막 요소 가리킴
• front와 rear 값 같으면 원형큐 비어있음을 나타냄
• 포화상태, 공백상태 구별 위해 하나의 자리 꼭 비워둠(포화상태=공백상태가 될 수 있어서)
• 공백상태: front==rear / 포화상태: front가 rear보다 하나 앞에 있을 때 
• *요소들의 개수 저장하고 있는 추가적 변수 count 있으면 한자리 안 비워도 됨

 
 
 

5.4 큐의 응용: 버퍼

 
-큐: 서로 다른 속도로 실행되는 두 프로세스 간의 상호작용을 조화시키는 버퍼역할 담당
ex. 생산자-소비자 프로세스(큐 버퍼로 사용), 교통관리시스템(원형큐), CPU 스케줄링(운체는 실행 가능한 프로세스 저장하거나 이벤트 기다리는 프로세스들을 저장하기 위하여 몇 개의 큐 사용
 

5.5 덱이란?

-double-ended queue 의 줄임말. 큐의 전단과 후단에서 모두 삽입과 삭제 가능한 큐(중간 삽입, 삭제는 허용 x)

 
 
 
 
 
 
 
 
-스택과 큐의 연산들 모두 가지고 있음. (스택이나 큐에 비해 더 융통성 많음-큐, 스택 둘 다 될 수 있음) 
-배열과 연결리스트 사용
-원형큐와 공통점 많음 > 원형큐 확장하면 덱도 쉽게 구현 가능

 
 
*계산하다가 음수가 되면 MAX_QUEUE_SIZE 더해줘야 함.
-덱은 연결리스트로 표현하기 더 복잡(선행노드와 후속노드 가리키는 포인터 변수 가져야 함 > 이중연결리스트)
 
 
 
 
 
 
 
 
 
 
 

5.6 큐의 응용: 시뮬레이션

-큐는 컴퓨터로 큐잉이론에 따라 시스템의 특성을 시뮬레이션하여 분석하는 데 이용. 큐잉모델은 고객에 대한 서비스 수행하는 server와 서비스 받는 client로 이루어짐. 제한된 수의 서버때문에 고객들은 서비스 받기 위해 '대기행렬'에서 기다림.
>service 시작= 전역변수 service_time에 고객 서비스 시간 저장