Data Structure #06 큐

화승이·2024년 6월 30일
1

CS공부

목록 보기
6/14

큐(Queue)

이번에 학습한 큐(Queue)는 앞서 했던 '스택'의 자료구조랑 굉장히 유사하면서 정반대인 자료구조이다. 스택은 접시를 여러개 쌓으면 나중에 쌓은 접시를 제일 먼저 뽑을 수 있는 후입선출의 구조라면, 큐는 먼저 들어간 데이터가 먼저 나오는 선입선출의 구조이다.

큐란?
먼저 들어간 데이터가 먼저 나오는 자료구조
FIFO(First-In, First-Out) 선입선출

대표적인 예시로는 줄을 서있는 우리의 모습을 예를 들면 된다. 우리가 줄을 서는 이유는 그 줄이 빨리 끝나서 우리가 볼 일을 보는 것이 목적인데, 큐도 다음과 같다. 먼저 나가는 데이터는 제일 먼저 줄을 서 있는 사람이라고 보면 쉽게 구조를 이해할 수 있다.


큐의 기본 연산자

큐의 기본 연산자는 크게 두가지로 나타낼 수 있다. 이도 마찬가지로 프로그래머가 구조를 어떻게 사용하냐에 나눠질 수 있겠지만 대표적으로는 데이터를 넣는 연산, 빼는 연산 크게 2가지이다.

  • Enqueue 연산자
    큐에 데이터를 넣는 연산자이다.

  • Dequeue 연산자
    반대로, 큐에서 데이터를 꺼내는 연산자이다. 제일 앞서 넣었던 데이터를 참조해서 빼면 된다.


큐의 ADT

다음은 큐의 ADT를 살펴보도록 하겠다.

  • 큐의 초기화하는데 사용한다. 큐의 자료구조를 사용하기 위해서 제일 먼저 호출되어야하는 함수이다.

    	void QueueInit(Queue * pq);
  • 큐가 비어있는지 여부를 확인한다. 비워있으면 1(TRUE), 데이터가 있으면 0(FALSE)를 반환한다.

    	int QIsEmpty(Queue * pq);
  • 큐에 데이터를 저장하는 연산, 매개변수인 data로 전달된 값을 큐에 저장한다.

    	void Enqueue(Queue * pq, Data data);
  • 저장순서가 가장 앞선 데이터를 삭제 후에 반환한다.

    	Data Dequeue(Queue * pq);
  • 저장순서가 앞선 데이터를 반환한다. Dequeue의 연산에서 삭제 말고 참조된 값을 반환만 한다.

    	Data QPeek(Queue * pq);

큐의 구현

이번 큐의 구현도 마찬가지로 배열과 연결리스트 기반의 구현으로 설명을 할 것이다.

큐의 배열기반 구현

큐의 머리를 F(Front), 큐의 꼬리를 R(Rear)로 가정할 때, 밑 그림으로 큐를 구현할 수 있다. 큐는 데이터를 넣을 때 데이터의 뒷부분에 삽입이 되고, 우리가 큐에서 데이터를 가져올 때는 앞부분에서 가져오기 때문에 F,R 두 개의 참조자가 다 필요하다는 것을 가정할 수 있다.

사실 위 그림에서는 문제가 있다. 만약 Dequeue연산을 2번 더 하고, Enqueue 연산을 더 했을 때 일차원적인 배열으로 볼 때 배열의 끝부분까지 계산을 하면 앞부분 배열은 비워있지만 뒤에 더 데이터를 삽입할 공간이 사라지는 것을 확인할 수 있다. 즉, R이 배열의 끝에 도달하게 되면, 회전을 해서 다시 앞부분부터 채워야하는 복잡한 일이 존재한다. 이거에 대한 해결책은 아래와 같다.

위 사진은 원형큐이다. 원형 큐는 R이 배열의 끝에 도달할 때 회전해야하는 문제를 해결해주는 구조이다. 단, 이 상태에서도 문제가 존재하는데 그 문제는 다음과 같다. 배열의 모든 공간을 다 F와 R이 사용한다면 빈 상태의 원형큐와 다 찼을 때의 원형큐에서 항상 F는 R보다 앞에 있기 때문에 두 개의 위치로만 구분이 힘들다. 그렇기에 한 공간을 비워두고 계산하면 편하다.

  • F와 R이 동일한 위치 => 원형 큐가 빈 상태
  • R이 가리키는 위치의 앞을 F가 가리킴 => 원형 큐가 꽉 찬 상태

큐의 연결리스트기반 구현

큐의 연결리스트 기반 구현은 배열 기반보다는 훨씬 구현하기 쉽다. 그 이유는 스택의 구현에서 데이터를 그냥 앞에서 꺼낸다고 생각하면 되기 때문이다.

  • 큐 초기화
    리스트 2개 (Front, Rear) 를 저장할 공간 만들기

  • Enqueue
    처음 데이터 추가에는 Front 외에 Rear 둘 다 새 노드를 가리키게 한다. 그 이후부터는 Rear의 위치만 변경해가면서 추가하면 된다.

  • Dequeue
    F가 가리키는 대상만 반환하고 변경시키면 된다. 얘도 마찬가지로 한 개만 남을 때는 R을 같이 해줘야하는지 걱정할 수 있지만 데이터를 추가하는 연산을 할 때 큐가 비워있는지의 여부를 확인해주는 연산은 F만 확인하기 때문에 상관이 없다.


덱은 큐와 비슷한 자료구조로 간단하게 설명만 하겠다.

덱(Deque)이란?
앞/뒤 어디든지 자료 넣기가 가능하며, 앞/뒤 어디든지 자료를 빼는 것이 가능한 자료구조, 스택과 큐의 특성을 모두 갖고 있다.

덱은 주로 연결리스트 중에서 양방향 리스트를 활용하면 쉽게 구현하기가 가능하다.

profile
공부한 것들 꾸준하게 올리는 블로그입니다.

0개의 댓글