큐_Queue

큐(Queue)

큐(Queue)는 데이터를 임시저장 하는 자료구조이다.

• 선입선출(FIFO:First In First Out)방식이다.
  • 가장 먼저 들어온 데이터가 가장 먼저 나간다.
• 큐에 데이터를 추가하는 작업을 인큐(enqueue)라고 하고 ,꺼내는 작업을 디큐(dequeue)라고 한다. 데이터를 넣는 쪽을 리어(rear) 꺼내는 쪽을 프런트(front)라고 한다.
• 가득 찬 큐에 요소를 추가하려고 할 때 overflow 가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 underflow가 발생한다.
• enqueue 및 dequeue 작업이 있는 경우 어느 시점에서 큐가 비어있어도 자료를 삽입하지 못하는 경우가 발생한다.

함수

enque() - 데이터 넣기

deque() - 데이터 꺼내기

peek() - 데이터 들어다 보기(맨 앞 데이터 front)

find() - 데이터 검색

count() - 데이터 개수 세기

__contains() - 데이터 포함 여부

clear() - 큐 전체 원소 삭제

dump() - 전체 데이터 출력

우선순위 큐(priority queue)

• 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할때 우선순위가 가장 높은 데이터를 꺼내는 방식
• python heapq 모듈에서 제공

 

링버퍼 (ring buffer)

• 디큐할 때 배열 안의 원소를 옮기지 않는 큐
• 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
• 링버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear의 값을 업데이트 하는 것만으로 인큐, 디큐를 수행한다.
• 두개의 포인터를 가지고 있다 head, tail 포인터

덱(double-ended queue)

• 맨 앞과 맨 끝 양쪽에서 데이터를 삽입 · 삭제할 수 있는 자료구조
• 2개의 포인터 사용