Data Structure: Queue

Queue

• FIFO(First In First Out)

• 먼저 push된 데이터가 먼저 pop되는 선입 선출의 구조로 되어있다.

• 리스트로 구현이 가능하지만 효율적이지 않다. 끝에 원소를 덧붙이거나 끝에서 꺼내는 작업은 빠르지만, 리스트의 처음에 원소를 추가하거나 빼는 것은 다른 원소들을 모두 한칸씩 이동시켜야하기 때문에 느리다.

• 양 끝에서 덧붙이기와 꺼내기가 빠르도록 설계된 deque를 사용하거나, 파이썬에서 제공하는 queue 모듈을 이용하거나 원소를 추가, 삭제하는데 효율적인 linked list를 이용할 수 있다.

• 기본적으로 값을 저장하는 연산인 enqueue와 저장된 값을 꺼내는 연산인 dequeue가 제공되어야하며, 부가적으로 큐의 길이를 반환하는 연산이나 큐가 비어있는지 확인한는 연산, 큐의 가장 아래에 있는 값이 무엇인지 확인하는 연산을 추가할 수 있다.

• 프린터의 출력 처리, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야하는 경우 이용된다.

  • Queue(): 가장 일반적인 큐 자료 구조
  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택과 유사 방식)
  • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

👉🏻 queue ADT

• front(head) : 데이터를 dequeue 할 수 있는 위치
• rear(tail) : 데이터를 enqueue 할 수 있는 위치
• 메소드
  • is_empty() : boolean
  • enqueue : insert
  • dequeue : delete
  • peek : 엿보기 (맨 앞의 값 반환만 하고 삭제하지 않는다. 조회)

list

• 리스트를 사용했을 경우 enqueue의 시간 복잡도는 O(1)이며 dequeue는 O(N)이다. 추가의 경우에는 큐의 맨 끝에서만 일어나지만 첫번째 원소를 삭제할 경우 두번째 원소부터 맨 마지막 원소까지 모든 원소들의 위치를 왼쪽으로 한칸씩 옮겨줘야 하기 때문이다.

# 리스트 사용
Class Queue(list):
    # enqueue == > insert 관용적인 이름
    enqueue = list.append
    # dequeue == > delete
    def dequeue(self):
        return self.pop(0)

    def is_empty(self):
        if not self:
            return True
        else:
            return False

    def peek(self):
        return self[0]

if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)

    while not q.is_empty():
        print(q.dequeue(), end= ' ') # 1 2 3 4 5

Deque

• double-ended queue로 앞과 뒤 양방향에서 데이터를 처리할 수 있는 자료구조를 의미한다.

• 파이썬의 리스트와 유사하지만 시간복잡도가 O(1)이다.(내부적으로 double linked list로 구현되어있다.)

from collections import deque

dq= deque([])

#데이터 추가
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
dq.append(5)

print(dq) ->deque([1, 2, 3, 4, 5])

#deque의 첫번째 원소 제거
print(dq.popleft())->1

---

https://visualgo.net/en/list