알고리즘 강의 6일차 - 큐(Queue)의 기초와 알고리즘

어제에 이어 오늘은 큐(Queue) 에 대한 기초 개념 강의 후 알고리즘 풀이를 했다.

 

큐(Queue)란?

선형 자료구조로써 First In First Out의 개념을 가진 자료구조이다.줄 서기 와 비슷한 방식이라고 보면되며, 앞쪽을 Front, 뒷쪽을 Rear라고 표현하며 EnQueue로 push되고DeQueue로 out된다.

 

아래와 같이 선형 큐를 배열로 표현할 수 있다. 하지만 DeQueue로 빠져버린 인덱스 자리는 빈공간으로 남게되고 추가하면 Rear뒤로 계속 추가되어 배열의 인덱스가 계속 늘어나게된다. 비스크립트 언어의 경우 배열의 길이가 한정되어있고 배열이 꽉차고 끝나게 되지만 자바스크립트의 경우에는 능동적으로 배열의 길이가 조절되기에 배열이 무한대로 늘어날 수 있다.

 

코드로 구현하는건 생각보다 간단한데, Queue라는 class함수안에 enqueue와 dequeue를 만들어 주면된다.

 

또한 선형 큐를 연결리스트로도 표현 가능하다. 연결리스트의 Head가 front가 되고, Rear부분이 Tail이 되게 만들면 된다.

 

코드로 구현하는건 아래와 같다. 선형 리스트를 만드는것과 크게 다르지 않은데 enqueue 부분도 연결리스트의 함수와 비슷한 형태이다.

 

또한 큐를 환형 연결리스트로도 만들 수 있는데, 환형리스트로 만듬으로써 얻을 수 있는 장점이 없기때문에 잘 사용하진 않는다.

 

큐에 관한 알고리즘 문제는 좀 더 생각해보고싶어서 내일 풀이를 적어보도록 하겠다.

 

이미지 출처: https://school.programmers.co.kr/learn/courses/13213/13213-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%91%ED%83%88-%EB%B0%A9%EC%A7%80-a-to-z-javascript