Queue(큐) (1)
纠错   04 Feb 2020

Queue는 사전적 의미는 “긴 열” 이다. 그림부터 보면

이렇게 데이터가 들어올 때 밑에서부터 위로 차곡차곡 쌓이게 되는 것 (put) 은 Stack이랑 똑같지만, 나갈 때는 아래부터 나가게 되는 (get) 구조로 Stack과 다르다. 그래서, 이를 FIFO (First In First Out)라고 부르고, 이러한 구조로 인해 front (Queue의 맨 앞 index)는 삭제연산 (이를 Enqueue라고 한다.)만, rear (Queue의 맨 뒤 index)부분은 삽입 연산 (이를 Dequeue라고 한다.)만 가능하다. Queue도 Stack과 마찬가지로 배열이나 연결리스트로 둘 다 구현이 가능하지만, 배열로 구현 시 문제점들이 많아 환형 큐 방식으로 구현하거나 연결리스트로 구현을 한다.

  • 배열로 구현 시 문제점

    데이터가 Queue에 가득 차 있다고 가정해보자. 이 상태에서 데이터를 get한다고 할 때 육안으로 봤을 때 Queue에 빈 자리가 있음에도 불구하고 코드 상으로는 Queue가 꽉 차서 Overflow가 발생하는 문제가 발생한다. 말로는 이해가 조금 어려울 수 있으니 아래 그림을 참고하자. 현재 그림은 최대 크기가 3인 Queue이다.

    이렇게 배열로 구현하게 되면 연결리스트처럼 데이터가 빠져나갈 때마다 메모리가 없어지는 것이 아니기 때문에 이렇게 빈 공간이 남게 된다. 그래서, 코드 상에는 rear (Queue의 맨 뒤 index) 부분이 3으로 즉, 최대치로 기록이 되어 있기 때문에 아래쪽에 빈 공간이 있음에도 불구하고 새로운 데이터가 들어갈 수가 없는 것이다. 이 상황을 정확히 이해했다면 해결책은 3가지로 제시할 수 있다.

    (1) 환형 (원형) Queue 방식

    환형 Queue 방식은 rear이 배열의 최대 크기까지 도달하면 처음으로 돌아가는 구조이다 (원의 구조를 생각하면 됨). 이렇게 되면 rear이 3에서 1로 가게 되므로 블록4가 1번 자리로 들어가게 된다.

    이게 환형 Queue 방식이 고안된 이유이다.

    (2) 삭제가 일어날 때마다 (데이터가 get 될 때마다) 모든 배열 원소 이동

    이는 Queue에서 데이터를 삭제하면 빈 공간이 남기 때문에 이를 채우기 위해 모든 요소를 한 칸씩 옮겨주는 방법이다. 이게 배열 요소가 몇 개 안될 때는 상관이 없는데 만약에 1억 개 또는 더 이상이면 그 많은 걸 다 옮겨야 하므로 상당한 리소스 낭비가 유발된다. 따라서, 이 방법은 그다지 권장되지 않는다.

    (3) 연결리스트

    아래에서 바로 설명하겠다.

  • 연결리스트로 구현

    배열로 구현했을 때의 단점을 해결해주는 방법이다. 연결리스트로 구현해주게 되면 데이터가 나갈 때마다 빈 공간이 알아서 없어지므로 배열에서 구현 시 발생한 문제를 고민할 필요가 없다. 그래서, Queue는 연결리스트로 많이 구현하는 편이다. 필자는 배열인 경우와 연결리스트 모두 구현할 것이고 다음 포스팅인 “Queue(큐) (2)”에서 확인할 수 있다 .

Queue의 활용 예


(1) 캐시(Cache)

검색해보니 있어서 적어는 놓았는데 솔직히 무슨 원리인지 모르겠다ㅠㅠ (만약 아신다면, 댓글 부탁드립니다.)

(2) 대기시간 처리 (예약 시스템)

무언가를 대기하는 상황에 먼저 대기(예약)한 순서부터 일처리가 이루어지므로 Queue를 이용할 수 있다. 예를 들어, 콜센터, 티켓 판매, 대기번호표, CPU의 연산 처리 시 프로세스 대기 등이 있다.

(3) 프린터의 출력 처리

사실 (2)와 같은 얘기인데, 인쇄 대기열이라고 생각하면 된다. 프린터기에 A, B, C가 순서대로 입력되면 A, B, C를 순서대로 출력해줘야 하므로 Queue를 이용할 수 있다.

(4) 메시지 처리기

이거 역시 (2), (3)과 같은 얘기이다. 메시지들은 시간 순서대로 쌓여있기 때문에 먼저 온 메시지들부터 처리해야 하므로 Queue를 이용할 수 있다.

(5) BFS (너비 우선 탐색)

- 맨 처음 시작노드(A)를 Queue에 넣는다.

- 시작노드인 A를 방문하면 Queue에서 A를 뺀다.

- A의 인접노드 B, C를 다시 Queue에 넣는다.

- B를 방문 시 Queue에서 B를 빼고 B의 인접노드인 D를 Queue에 넣는다.

- 너비 우선 탐색이므로 다시 돌아와서 C를 방문하고 Queue에서 C를 뺀다.

- 그 다음 남은 D를 방문하고 Queue에서 D를 뺀다.

P.S : https://hongku.tistory.com/156 –> 더 자세한 이해가 필요하신 분은 이 블로그에 BFS에 관해 잘 설명이 되어있으니 참고바랍니다.

  • 그 외의 Queue

    (1) 우선 순위 Queue

    이는 말 그대로 먼저 들어간 데이터가 먼저 나오는 것이 아닌 순서와 상관없이 우선 순위가 높은 데이터가 먼저 나오는 Queue이다. 예를 들어, 대기 순서가 있지만 VIP 회원은 먼저 들어간다던지, 병원에서 응급 환자를 먼저 치료한다던지, 노래방의 우선 예약기능 등이 있다. 이 우선순위 Queue는 추후에 Heap을 포스팅하고 다시 포스팅할 예정이므로 지금은 간단하게 언급정도만 하고 넘어가겠다.

    (2) Deque (Double Ended Queue)

    양쪽 끝에서 삽입과 삭제가 모두 가능한 Queue이다. 쉽게 생각하면, 큐와 스택을 합친 형태로 생각할 수 있다. 이러한 특징으로 인해, 스케쥴링에 많이 이용된다. 왜냐하면, 큐와 스택이 하나의 방향성만 있어 제한조건이 많은 데 반해 Deque는 양방향이므로 우선순위가 있는 스케쥴링이라던지 어떤 특정 조건이 있는 스케쥴링 등 다양한 조건에서 유용하게 쓰일 수 있기 때문이다.

참고 사이트 :


이전글： Stack(스택) (2) 다음글： Queue(큐) (2)

검색

분야

사이트