[자료구조] 5. Circle queue (원형 큐)

• 큐
• 덱

 

 

큐(queue)

 

선입선출의 자료구조.. FIFO… First In First Out

즉 대기열임 .. 기다리는 순서대로 나가니까..

front.. 전단 ~~~~~ rear… 후단

삭제하는 곳 들어오는 곳

큐의 연산 5가지

• enqueue(e) : e를 후단에 삽입
• dequeue() : 전단에서 데이터 삭제
• isEmpty() : Empty면 True, 아니면 False 반환
• isFull() : Full이면 True, 아니면 False 반환
• peek() : 큐의 맨 앞 요소를 삭제하지 않고 !! 반환

 

동적배열을 이용함.. 단방향 linked 리스트

→ del queue[0] 하면 전방에 있는 원소 삭제.. 스택은 top 원소 삭제

→ peek… queue[0] 하면 전방의 원소 반환…

class queue

• 단점

원소를 삭제할 때… 최상단의 데이터를 모두 삭제해야 앞으로 밀 수 있음..

최악의 경우.. O(n)의 시간복잡도

⇒ 원형 큐

원형으로 데이터를 제어하는 구조

일반적으로 크기를 고정해두고 사용한다

front : 맨 앞 원소를 참조…. dequeue()

rear : 마지막 원소를 참조….. enqueue()

Q. 크기가 n인 원형 큐에서 enqueue가 갖는 시간 복잡도는?

A. O(1).. … 일반 큐도 마찬가지

• rear가 참조하던 곳에 데이터 삽입
• rear + 1

Q. 크기가 n인 원형 큐에서 dequeue가 갖는 시간 복잡도는?

A. O(1)

• 최전방의 데이터 None으로 대치
• front + 1

 

 

덱 (Deque)

 

스택이나 큐보다 입출력이 자유로운 자료구조

전단과 후단에서 모두 삽입 및 삭제가 가능

스택 + 큐 의 특성을 합친 자료구조

//양방향 linked 리스트로 구현

• 파이썬에서의 덱 라이브러리 제공 
• from collections import dequeue deq = dequeue() deq.append(5) deq.appendleft(3) deq.popleft() print(deq) # 출력결과 5 (3-5)에서 3pop
• from collections import dequeue