Queue

FIFO - 선입 선출 특징

First-In First-Out

1 넣을 때에는 한 쪽 끝에서 밀어 넣어야 한다.

-> enqueue 연산

2.꺼낼 때에는 반대 쪽에서 뽑아 꺼내야하는 제약

-> dequeue 연산

초기 상태

empty queue

enqueue - 원소 넣기

dequeue - 원소 빼기(반대 방향)

추상적 자료구조 구현

1) array

-> python list built in method

2) LinkedList

-> Doubly LinkedList

method

1. size() - 현재 큐에 들어 있는 데이터 원소의 수 O(1)

2. isEmpty() - 현재 큐가 비어 있는지 판단 O(1)

3. enqueue(x) - 데이터 원소 큐에 추가 O(1)

4. dequeue - 큐에 맨 앞에 저장된 데이터 원소 제기 or 반환 O(n)

5. peek() - 큐의 맨앞에 저장된 데이터 원소 반환(제거 x) O(1)

dequeue 시간 복잡도 - 20, 37, 58, 65, 72, 91

- 맨앞에 요소를 뺌으로 인덱스가 순차적으로 앞으도 당겨와서 시간 복잡도가 O(n) 리스트가 길면 길수록 오래 걸림.

큐 활용

1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이

비동기적으로 일어나는 경우

2. 자료를 생성하는 작업과 그 자료를 이용하는 작업이

양쪽 다 여러 곳에서 이용하는 경우.

consumer <- product <- producer

consumer <- product <- producer1, producer2

consumer1, consumer2 <- product <- producer

3. 자료를 처리하여 새로운 자료를 생성하고,

나중에 그 자료를 또 처리해야 하는 작업의 경우

4. 환형 큐

-정해진 개수의 저장 공간을 빙 돌려가며 이용.

- 큐 길이를 기억하고 있어야 한다. (정해진 개수)

- front, rear

methods

1. size() - 현재 큐에 들어 있는 데이터 원소의 수 O(1)

2. isEmpty() - 현재 큐가 비어 있는지 판단 O(1)

3. enqueue(x) - 데이터 원소 큐에 추가 O(1)

4. dequeue() - 큐에 맨 앞에 저장된 데이터 원소 제기 or 반환 O(n)

5. peek() - 큐의 맨앞에 저장된 데이터 원소 반환(제거 x) O(1)

6. isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단.

5. priority queue

- 큐가 FIFO 방식을 따르지 않고 원소드르이 우선순위에 따라 큐에서 빠져나오는 방식.

활용 예 - 운영체제의 cpu 스케쥴러

방식 1. enqueue 할 때 우선순위 순서를 유지하도록

방식 2. dequeue 할 때 우선순위 높은 것을 선택

-> 어느 것이 유리 할까? - 1번이 유리함. (무작위로 들어 갔을 때 dequeue 할때 원소를 다 찾아야함으로 오래 걸림)

1. 선행 배열 or 연결 리스트중 머가 더 유리할까?

- 시간적인 측면은 연결 리스트가 유리.

- 메모리 측면에서는 선형 배열이 유리함.

> 시간을 우선순위를 두고 채택하는 경우가 많음.