Queue(큐)에 대한 간단한 설명

코드 링크는 아래에 있습니다(queue.ipynb)

https://github.com/J-hoplin1/Python-DataStructure/blob/master/Queue.ipynb

 

큐(Queue)란 스택과 달리 항목이 들어온 순서대로 접근이 가능한 FIFO(First In First Out, 선입선출)구조이다. 큐 또한 배열 인덱싱을 통한 접근이 불가능하다. 가장 쉽게 생각하면 우리가 줄서는 것을 생각해보면 된다. 큐 또한 스택과 동일하게 다양한 동작들이 있으며 이 또한 O(1)의 시간복잡도를 가지게 된다.

 

큐의 기본적인 원리

 

- enqueue : 큐 뒤쪽에 항목을 삽입한다.

 

- dequeue : 큐 앞쪽의 항목을 반환 후 제거

 

- peek : 큐의 앞쪽 항목 조회

 

- empty : 큐가 비었는지에 대해 확인

 

- size : 큐의 크기 확인

 

예시 코드 3개를 들어보겠다.

 

1. 기본적인 큐 원리

 

위의 코드는 insert를 이용해서 새로운 값들을 0번째 인덱스에 넣는 방식을 사용하였다. 하지만 이 방법은 기존의 인자들을 모두 옮겨주어야 하므로 O(1)이 아닌 O(n) 시간복잡도를 가지게 된다. 좀더 효율적인 방식으로 큐를 작성하는 방법은 스택(stack)두개를 이용하는 방법이 있다.

 

다른 하나는 스택에서 하였던것과 같이 노드를 이용하여 구현한 Linked Queue 이다.