그림으로 쉽게 이해하는 자료구조 큐(Queue) (ft. 큐를 배열기반에서 절대 선형으로 구현하지 않는 이유)

그림으로 쉽게 이해하는 자료구조 큐(Queue) (ft. 큐를 배열기반에서 절대 선형으로 구현하지 않는 이유)

 

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

 

오늘은 자료구조 중에서 중요한 큐(Queue)에 대해서 같이 알아보겠습니다.

 

어렵지 않으니 잘 따라와주세요~!

 

 

 

 

- 큐(Queue)란?

 

이전 포스팅에서 배운 스택에서는

 

먼저 들어온 데이터가 나중에 빠지는 후입선출의 LIFO(리포)구조라고 배워습니다.

 

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)

 

그런데 큐(Queue)는 선입선출로 First-in-first-out FIFO(피포) 구조입니다.

 

다시 말해서,

 

먼저 들어온 데이터가 먼저 빠지게 되는 것이죠.

그렇게 순서대로 처리되는 형태를 갖기 때문에

 

데이터의 순서를 보장하는 처리가 필요한 경우에 Queue를 써서 처리를 합니다.

 

 

 

- 큐(Queue)의 활용 예시

쉬운 예를 들어보겠습니다.

 

특정 사이트가 이벤트로 인해서 사람이 확 몰렸다고 가정해봅시다.

 

그때 사람이 몰린 연결 커넥션들을 Queue에다가 하나씩 넣어두고

 

앞에서 부터 먼저 들어온 순서대로 하나씩 하나씩 연결을 처리해주겠죠.

 

 

 

- 큐(Queue)의 주요 동작 3가지

Queue의 주요 동작으로는 push, pop, peek이 있습니다.

 

스택과 비슷하죠. 

언어마다 구현하는 API명이 약간은 달라서 push 대신에 offet나 add를 쓰기도 하고

pop 대신에 poll을 쓰기도 합니다.

언어마다 명칭만 다르지 하고자 하는 동작은 똑같습니다.

push는 데이터를 넣는 작업, pop은 데이터를 빼오는 작업, peek은 데이터를 확인하는 작업 입니다.

Queue에 데이터가 입력되는 동작을 enqueue라고 하고

Queue에서 데이터가 빠지는 출력 동작을 dequeue라고 합니다.

앞에서 말한것처럼 push와 pop이 각각의 연산에 해당하겠죠.

그리고 Queue는 순서를 보장하는 자료구조이기에

 

데이터가 들어갈 때는 제일 뒤인 rear쪽에 데이터가 들어가고

데이터가 빠져나갈 때는 가장 앞쪽인 Front부터 데이터가 빠지게 됩니다.

 

 

큐 그림 예시

 

일단 아무것도 없는 상황에서 데이터가 들어오게 되면 위 그림에서 처럼 front에 데이터가 쌓이게 되고,

그 다음에 데이터가 들어오게 되면 그 뒤에, 그리고 데이터가 또 들어오면 그 뒤에 쌓이면서 

 

순차적으로 데이터가 쌓입니다.

그리고 데이터가 빠질때는 가장 먼저 들어온 초록색 노드부터 빠지게 되겠죠.

그리고 또 빠지게 되면 연노란색이 빠지게 됩니다.

그리고 여기서 데이터가 또 들어 오게 되면 빨간색 노드 뒤에 데이터가 쌓이게 되겠죠.

 

 

 

- 큐(Queue)를 배열로 구현한다면 무슨 일이 생길까요?

큐의 동작을 한 번 같이 예상을 해볼까요?

먼저 고정된 사이즈의 배열이 주어지겠죠.

여기서 데이터를 넣게 되면 0번째에 데이터가 먼저 들어가게 될거고,

 

그 다음에 첫번째, 두번째 이렇게 순차적으로 데이터가 쌓이게 될 겁니다.

 

그 다음에 데이터를 빼는 연산인 Dequeue연산을 합니다.

 

그러면 가장 먼저 들어 온 노드가 먼저 빠지게 되겠죠.

 

그러면 맨 앞이 비게 되는 현상이 또 발생할 거에요.

 

그러면 이것을 또 한 칸씩 다 앞으로 당겨줘야 합니다.

 

이렇게 배열로 Queue를 구현할 경우에

 

앞에 있는 데이터가 빠질 때마다 데이터를 한칸씩 앞으로 당겨주는 연산을 해야 합니다.

 

만약 하지 않게 되면,

 

앞에는 데이터가 빠지게 되면서 점점점점 비게 되는데 뒤에는 데이터가 계속 쌓이게 되요.

그래서 나중에는 

데이터가 앞에 공간이 많이 비어있는데도 더이상 데이터를 넣지 못하는 상황이 발생할 수도 있습니다.

 

그렇기 때문에 배열로 Queue를 구현하게 되면은

 

데이터를 한칸씩 앞으로 당겨오는 과정이 반드시 들어가야 하기 때문에

이렇게 할 경우 시간 복잡도가 O(N)까지 상승을 하게 되겠죠.

 

N개의 데이터만큼 앞으로 당겨와야 하니까요.

그래서 Queue는 선형 구조이지만 배열 기반으로 구현해서 쓰는 것은 비효율적이라 잘 쓰지는 않습니다.

 

다음 포스팅에서에서는 원형큐에 대해서 다뤄보도록 하겠습니다.

 

로스윗의 코딩 캠프는

 

미래의 개발자 여러분을 응원합니다!!

 

모두 화이팅입니다!!

 

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)

자료구조 스택(stack)이란? (ft. 그림으로 쉽게 설명)

 

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)