스택과 마찬가지로 큐는 선입선출(First In First Out) 방식으로 항목을 저장하는 선형 데이터 구조입니다. FIFO ) 방식. 대기열을 사용하면 가장 최근에 추가된 항목이 먼저 제거됩니다. 대기열의 좋은 예는 먼저 온 소비자가 먼저 제공되는 리소스에 대한 소비자 대기열입니다.

대기열과 관련된 작업은 다음과 같습니다.

• 대기열에 추가: 대기열에 항목을 추가합니다. 대기열이 가득 차면 오버플로 상태라고 합니다. – 시간 복잡도: O(1)
• 따라서: 대기열에서 항목을 제거합니다. 항목은 푸시된 순서와 동일한 순서로 팝됩니다. 큐가 비어 있으면 언더플로우 상태라고 합니다. – 시간 복잡도: O(1)
• 앞쪽: 대기열에서 맨 앞의 항목 가져오기 – 시간 복잡도: O(1)
• 뒤쪽: 대기열에서 마지막 항목 가져오기 – 시간 복잡도: O(1)

Python에서 대기열 구현

큐를 구현하는 방법에는 여러 가지가 있습니다. 파이썬. 이 문서에서는 Python 라이브러리의 데이터 구조와 모듈을 사용하여 대기열을 구현하는 방법을 다룹니다. Python 대기열은 다음과 같은 방법으로 구현할 수 있습니다.

• 목록
• collections.deque
• 꼬리.꼬리

목록을 이용한 구현

리스트는 큐로 사용할 수 있는 Python의 내장 데이터 구조입니다. enqueue() 대신 따라서 () , 추가() 그리고 팝() 기능이 사용됩니다. 그러나 처음에 요소를 삽입하거나 삭제하려면 다른 모든 요소를 ​​하나씩 이동해야 하고 O(n) 시간이 필요하기 때문에 이 목적을 위해서는 목록이 상당히 느립니다.
이 코드는 Python 목록을 사용하여 대기열을 시뮬레이션합니다. 요소를 추가합니다 'ㅏ' , '비' , 그리고 '씨' 대기열에 추가한 다음 대기열에서 빼면 끝에 빈 대기열이 생성됩니다. 출력에는 초기 대기열, 대기열에서 제거된 요소( 'ㅏ' , '비' , '씨' ) 및 대기열의 빈 상태입니다.

파이썬3

산출:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements [] 

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list 

collections.deque를 사용한 구현

Python의 대기열은 컬렉션 모듈의 deque 클래스를 사용하여 구현할 수 있습니다. Deque는 O(n) 시간 복잡성을 제공하는 목록에 비해 추가 및 팝 작업에 O(1) 시간 복잡성을 제공하므로 컨테이너 양쪽 끝에서 더 빠른 추가 및 팝 작업이 필요한 경우 목록보다 Deque가 선호됩니다. . enqueue와 deque 대신에 add()와 popleft() 함수가 사용됩니다.
코드는 deque> ~로부터 collections> 큐를 나타내는 모듈입니다. 그것은 덧붙인다 'ㅏ' , '비' , 그리고 '씨' 대기열에 추가하고 대기열에서 제거합니다. q.popleft()> , 결과적으로 빈 대기열이 생성됩니다. 주석 해제 중 q.popleft()> 대기열이 비어 있으면 IndexError> . 코드는 대기열 작업을 보여주고 빈 대기열 시나리오를 처리합니다.

파이썬3

산출:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([]) 

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque 

queue.Queue를 사용한 구현

큐는 큐를 구현하는 데 사용되는 Python 내장 모듈입니다. queue.Queue(maxsize)는 변수를 최대 크기인 maxsize로 초기화합니다. 최대 크기가 0인 '0'은 무한 대기열을 의미합니다. 이 대기열은 FIFO 규칙을 따릅니다.
이 모듈에서는 다양한 기능을 사용할 수 있습니다:

• 최대 크기 – 대기열에 허용되는 항목 수.
• 비어 있는() – 대기열이 비어 있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
• 가득한() – 대기열에 최대 크기 항목이 있는 경우 True를 반환합니다. 대기열이 maxsize=0(기본값)으로 초기화된 경우 full()은 결코 True를 반환하지 않습니다.
• 얻다() – 대기열에서 항목을 제거하고 반환합니다. 대기열이 비어 있으면 항목을 사용할 수 있을 때까지 기다립니다.
• get_nowait() – 즉시 사용 가능한 항목이 있으면 항목을 반환하고, 그렇지 않으면 QueueEmpty를 발생시킵니다.
• 넣다(항목) – 항목을 대기열에 넣습니다. 대기열이 가득 찬 경우 항목을 추가하기 전에 여유 슬롯을 사용할 수 있을 때까지 기다리십시오.
• put_nowait(항목) – 차단하지 않고 항목을 대기열에 넣습니다. 즉시 사용 가능한 여유 슬롯이 없으면 QueueFull을 발생시킵니다.
• 큐사이즈() – 대기열에 있는 항목 수를 반환합니다.

예: 이 코드는 Queue> 의 수업 queue> 기준 치수. 빈 대기열로 시작하여 '로 채웁니다. ㅏ', '비' , 그리고 '씨' . 큐에서 빼낸 후에는 큐가 비어지고 '1'이 추가됩니다. 이전에는 비어 있었음에도 불구하고 최대 크기가 3으로 설정되어 있으므로 가득 찬 상태로 유지됩니다. 코드는 가득 참 및 비어 있음 확인을 포함한 대기열 작업을 보여줍니다.

파이썬3

산출:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False