[Python 자료구조] 큐 (Queue)

💡 Goal
- 큐를 이해한다.
- 큐를 파이썬으로 구현한다.
- 큐 특징 2가지 이상 말하기.

개념

---

FIFO(First In First Out)으로 동작하며 데이터간 순서를 약속하는 추상자료형을 말한다.

가장 먼저 들어온 데이터가 가장 먼저 삭제

대기열과 같은 개념 (ATM기 줄서있는 사람들 모습)

특징

---

• deque를 사용해 큐 자료구조 구현 (doubly-ended-queue의 약자)
  • deque는 내부적으로 doubly linked list로 구현
  • 맨 앞, 뒤에 데이터를 삭제하고 삭제할 수 있게 하는 자료형
  • enqueue: 끝에 삽입
  • peek: 시작 개체값 리턴
  • dequeue: 시작 개체값 제거
• 큐의 활용
  • 스케줄링
    • 동시에 실행되는 여러 프로세스의 자원을 배정을 적절히 조절해 성능 개선
  • 어떤 작업이 병렬적으로 처리될때 큐에 저장하여 관리

시간복잡도 O(1)

• popleft: O(1)

코드 구현

from collections import deque

class Queue:
    def __init__(self, value=[]):
        self.items = deque(value)

    def enqueue(self, data):
        self.items.append(data)

    def dequeue(self):
        if not self.is_empty():
            self.items.popleft()
        else:
            print("underflow")
            exit()

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            print("underflow")
            exit()

    def is_empty(self):
        return len(self.items) == 0

queue = Queue()

queue.enqueue(1)
queue.enqueue(3)
queue.dequeue()
queue.enqueue(5)

print(queue.items[1]) # 5
print(queue.peek()) # 3

References

• https://daimhada.tistory.com/56
• https://www.codeit.kr/courses/data-structures