C++로 쉽게 풀어쓴 자료구조/ 큐

큐(Queue)의 추상 자료형

큐란?

입출력이 선입선출(First-In First-Out)인 자료구조.

삽입과 삭제가 같은 위치에서 일어나는 스택과 달리 큐는 삽입과 삭제가 다른 위치에서 일어나는데, 삽입이 일어나는 곳을 후단(rear), 삭제가 일어나는 곳을 전단(front)이라고 한다.

큐의 추상 자료형

  • 객체
    • 선입선출의 접근 방법을 유지하는 요소들의 모음
  • 연산
    • enqueue(e): 주어진 요소 e를 큐의 맨 뒤에 추가한다.
    • dequeue(): 큐가 비어 있지 않으면 맨 앞 요소를 삭제하고 반환한다.
    • peek(): 큐가 비어 있지 않으면 맨 앞 요소를 삭제하지 않고 반환한다.
    • isEmpty(): 큐가 비어 있으면 true, 아니면 false를 반환한다.
    • isFull(): 큐가 가득 차 있으면 true, 아니면 false를 반환한다.
    • size(): 큐의 모든 요소들의 개수를 반환한다.
    • display(): 큐의 모든 요소들을 출력한다.

큐의 활용

컴퓨터 장치들 사이에 데이터를 주고받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 큐가 사용되는데, 이것을 보통 버퍼(buffer)라고 한다. 대부분의 장치에서 발생하는 이벤트는 불규칙하지만, 이를 받아 처리하는 CPU는 일정한 처리 속도를 갖기 때문에 이 둘의 속도 차이를 버퍼를 사용하여 해결한다.

  • 키보드와 컴퓨터 사이에 큐(입력 버퍼)가 존재한다.
  • 컴퓨터와 프린터 사이에도 인쇄 작업 큐가 존재한다.
  • 실시간 비디오 스트리밍에서의 버퍼링에서도 큐가 존재한다.

큐의 구현

선형 큐

배열로 큐를 구현할 때는 크기가 정해진 배열과 삭제를 위한 변수 front, 삽입을 위한 변수 rear가 필요하다. front는 큐의 첫 번째 요소를 가리키고, rear는 큐의 마지막 요소를 가리킨다.

큐가 처음 생성되면 front와 rear의 초기값은 -1로 정해진다. enqueue를 통해 데이터가 삽입되면 먼저 rear를 하나 증가하고 그 위치에 데이터를 저장한다. 삭제 시에는 front를 먼저 하나 증가시키고 front가 가리키는 위치에 있는 요소를 삭제한다.

선형 큐는 front와 rear가 계속 증가만 하기 때문에 배열의 앞부분이 비게 된다는 문제가 있다. 이를 해결하기 위해 후단에 더 삽입할 공간이 없다면 모든 요소들을 왼쪽으로 이동시켜야 하는데, 이는 번거롭고 비효율적인 방법이다.

원형 큐

선형 큐보다 효율적으로 데이터를 관리하는 방법은 원형 큐를 구성하는 것이다. font와 rear의 값이 배열의 끝에 도달하면 다음에 증가되는 값은 0이 되도록하면 배열을 효율적으로 관리할 수 있다.

원형 큐에서는 front와 rear가 선형 큐와는 약간 다른데, front와 rear의 초기값이 -1이 아니라 0이라는 것과 front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다는 것이 그것이다.

원형 큐에서는 포화 상태와 공백 상태를 구분하기 위해서 하나의 자리는 항상 비워두어야 한다. front==rear 면 공백 상태가 되고 front가 rear보다 하나 앞에 있으면 –아래 이미지 기준으로 시계 방향으로 1칸 앞에– 포화 상태가 된다. 큐의 요소들의 갯수를 관리하는 추가적인 변수를 사용한다면 한 자리를 비워두지 않아도 되지만, 이 방법을 프로그램이 복잡해질 수 있다.

덱(Deque)

덱의 소개

덱은 double-ended queue의 줄임말로써 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그러나 여전히 중간에 삽입하거나 삭제하는 것은 허용되지 않는다.

덱은 스택과 큐의 연산들을 모두 갖고 있다. addFront, deleteFront 연산은 스택의 push, pop과 동일하며, addRear, deleteFront는 큐의 enqueue, dequeue 연산과 같다. 덱의 전단과 관련된 연산들만 사용하면 스택이 되고, 삽입은 후단만 허용하고 삭제는 전단만 사용하면 큐가 된다.

덱의 추상 자료형

  • 객체
    • 전단과 후단을 통한 접근을 허용하는 요소들의 모음
  • 연산
    • addFront(e): 주어진 요소 e를 덱의 맨 앞에 추가한다.
    • deleteFront(): 덱이 비어 있지 않으면 맨 앞 요소를 삭제하고 반환한다.
    • addRear(e): 주어진 요소 e를 덱의 맨 뒤에 추가한다.
    • deleteRear(): 덱이 비어 있지 않으면 맨 뒤 요소를 삭제하고 반환한다.
    • getFront(): 덱이 비어 있지 않으면 맨 앞 요소를 삭제하지 않고 반환한다.
    • getRear(): 덱이 비어 있지 않으면 맨 뒤 요소를 삭제하지 않고 반환한다.
    • isEmpty(): 덱이 비어 있으면 true, 아니면 false를 반환한다.
    • isFull(): 덱이 가득 차 있으면 true, 아니면 false를 반환한다.
    • display(): 덱의 모든 요소들을 출력한다.

미로 탐색 문제

미로 탐색 문제는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, Breadth First Search)으로 구분할 수 있다. 이 중 너비 우선 탐색은 일단 주위를 다 둘러 본 후 다음 위치로 이동하는 방식인데, 이 방식은 큐 자료 구조가 적합하다. 반면 깊이 우선 탐색은 일단 갈 수 있는 데까지 간 후에 막히면 다른 길을 찾는 방식으로 스택 자료 구조가 적합하다.

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기