DataStructure - Queue - 큐

 

안녕하세요 Beepeach입니다 :)

오늘 공부해볼 자료구조는 Queue(큐)입니다.

Queue에서도 여러 가지 종류가 있지만 그중 가장 기본이 되는 queue에 대해서 공부해보겠습니다!

 

 

---

 

Queue

 

Queue는 OS(운영체제)에서 프로세스 스케쥴링에 사용하는 아주 기본적인 자료구조입니다.

Queue라는 단어를 사전에서 찾아보면 줄, 대기열이라고 나옵니다.

이 단어를 사용한 이유가 있겠죠??

단어 그대로 줄 서는것과 비슷하게 동작하기 때문입니다.

 

식당에서 가서 대기줄을 서는 것을 생각해보세요.

먼저 줄을 선 순서대로 식당에 입장을 하죠??

줄을 처음에 선 사람이 가장 먼저 줄을 나가게 됩니다.

이러한 방식을 FIFO(First-In First-out)라고 합니다. (발음하는 방법은 파이포입니다. 피포가 아니에요...)

 

 

---

 

Enqueue, Dequeue

 

Queue에 데이터를 넣는 작업을 Enqueue라고 하고 데이터를 빼는 작업은 Dequeue라고 합니다.

그럼 시각적으로 확인해보도록 하겠습니다.

 

 

head가 왼쪽인것을 감안해주세요.

24를 enqueue하니까 tail에 추가가 되고 dequeue를 실행하니 head인 41부터 사라지는 것을 확인할 수 있습니다.

알고리즘을 시각적으로 확인하는 사이트는 아래에 링크를 첨부하도록 할게요. 해당 사이트에 가시면 queue뿐만 아니라 이것저것 보실 수 있습니다.

 

 

---

 

Swift에서 queue 만들기

 

Swift에서는 queue를 따로 제공하지 않습니다.

그래서 직접 만들어 보겠습니다.

 

 

구조체와 제네릭을 이용하여 손쉽게 queue를 구현할 수 있습니다.

append(_:) 메서드를 이용하여 배열의 끝에 element를 추가시키고

removeFirst() 메서드를 이용하여 맨 앞의 element를 제거하면 끝입니다!

 

 

---

 

알고리즘과 데이터구조를 시각적으로 볼 수 있는 사이트

 

https://visualgo.net/en

 

VisuAlgo - visualising data structures and algorithms through animation

 

---