큐 ( Queue )

HP :) 😃·2022년 1월 7일

알고리즘

[Python] 자료구조

목록 보기

2/4

안녕하세요 hp입니다 :)

오늘은 큐 자료구조에 대해서 공부해도록 하겠습니다.

📚 개념

큐는 기본적으로 데이터의 삽입은 한쪽끝에서 삭제는 다른 쪽 끝에서 일어나는 자료구조입니다.
삽입한 순서대로 원소가 나열되어 가장 먼저 삽입된 원소가 맨 앞에 있다가 가장 먼저 삭제되는 것을 말합니다.
이를 선입선출 ( FIFO ) 라고 합니다.

큐는 삽입과 삭제에 O(1)의 시간복잡도를 가지고 있습니다.
단 , 검색의 경우에는 O(N)의 시간복잡도를 가집니다.

💡 큐 함수

enQueue
큐에 원소를 추가한다.
deQueue
가장 먼저 들어간 원소를 큐에서 삭제하는 경우
empty
큐에 원소가 비어있는지 확인

리스트로 queue를 구현

queue = []

queue.append(1)
queue.append(2)
queue.append(3)

print(queue) # queue = [1,2,3]

queue.pop(0)
queue.pop(0)
queue.pop(0)

print(queue) # queue = []

겉으로 보기에는 stack과 같이 작동하는 것처럼 보이지만 큐와 같이 동작하기 위해 pop()메소드에 0번 인덱스를 입력함으로써 첫번째 원소를 지우고 그 뒤에 있는 원소들이 앞으로 한칸씩 움직이기 때문에 최악의 경우 O(N)의 시간복잡도를 가지게 된다.

그렇기 때문에 큐는 리스트를 이용해서 구현하지 않고 collections 모듈에 deque를 이용해준다.

📚 개념

데크(덱)은 양쪽 끝에서 삽입과 삭제 연산이 모두 가능한 자료구조입니다.

덱 자료구조

deque를 사용하기에 앞서 deque안에 존재하는 메서드들을 알아보도록 하겠습니다.

💡 데크 메서드

deque.append(n) : n을 데크의 오른쪽에 삽입
deque.appendleft(n) : n을 데크의 왼쪽에 삽입
deque.pop() : 데크의 오른쪽 끝 원소를 가져오는 동시에 삭제
deque.popleft() : 데크의 왼쪽 끝 원소를 가져오는 동시에 삭제
deque.extend(arr) : arr을 순환하면서 데크의 오른쪽에 추가
deque.extendleft(arr) : arr은 순환하면서 데크의 왼쪽에 추가
deque.remove(n) : n을 데크에서 찾아 삭제
deque.rotate(num) : 데크를 num만큼 회전한다. ( 양수면 오른쪽 , 음수면 왼쪽 )

from collections import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)

print(queue) # queue = [1,2,3]

queue.popleft() 
queue.popleft() 	
queue.popleft() 	

print(queue) # queue = []