[Python][파이썬] 자료구조 큐(Queue)

안녕하세요. Jake 입니다.

이번 시간에는 자료구조중 자주 쓰게 되는 큐를 같이 구현 해보려 합니다.

 

스택이란?

 - FIFO(First In First Out)의 구조를 가지는 자료 구조입니다.

 - 파이썬에선 리스트나 , deque를 import 해서 주로 사용합니다.

 - 트리나 그래프에서 BFS 탐색시 주로 사용되는 자료구조 입니다.

 ex)우리가 파이썬에 q = [] 로 선언하고, 차례로

      q.append(1), q.append(2), q.append(3)  실행시 큐에 다음과 같은 모양으로 데이터가 들어갑니다. 수행시간 (O(1))

 

1

2

3

후에 q.pop(0)을 수행시 맨 왼쪽에 있는 데이터  1 부터 반환 되고 나머지 데이터 두개가 큐에 남아있게 되죠. 

유의 사항: list 로 구현시 q.pop(0) 수행시간은 O(n) 이고, 효율이 좋지 않다.

                 이 시간을 단축 시키고자 q = deque() 로 선언 하고 q.popleft() 로 데이터를 제거 하면,  수행시간이 O(1) 로 좋아진다.

 

2

3

List 를 통한 MyQueue 클래스 구현

- MyQueue 클래스에는 데이터를 저장하는 리스트와, enqueue, dequeue, peek, isEmpty 메소드를 구현해 보도록 하겠습니다.

메소드별 수행시간 : enque : o(1), dequeue: o(n), peek : o(1), isEmpty:o(1)

LinkedList 를 통한 LinkedListQueue 클래스 구현

- LinkedListQueue 클래스에는 Node 클래스를 따로 구현 하고 , enqueue, dequeue, peek, isEmpty 메소드를 구현 하겠습니다.

 

메소드별 수행시간 : enque : o(1), dequeue: o(1), peek : o(1), isEmpty:o(1)

 * 링크드리스트로 구현시, peek 요소를 계속해서 head로 가지고 있으니 좀더 효율적으로 수행됩니다.

 

다음 시간에는 우선순위큐를 구현해 보도록 하겠습니다.