연결 리스트로 구현한 큐

연결 리스트를 이용하여 스택을 만들 수 있는 것처럼 큐도 연결 리스트를 이용하여 만들 수 있다. 연결 리스트로 만들어진 큐를 연결된 큐(Linked queue) 라고 한다. 연결 리스트로 구현된 큐는 배열로 구현된 큐에 비하여 크기가 제한되지 않는다는 장점을 지니고 있다. 반면 배열로 구현된 큐에 비하여 코드가 복잡하고 링크 필드 때문에 메모리 공간을 더 많이 사용한다. 기본적인 구조는 단순 연결 리스트에다가 2개의 포인터를 추가한 것과 같다. front 포인터는 삭제와 관련되며 rear 포인터는 삽입과 관련된다. 

 

위와 같이 front는 연결 리스트의 맨 앞에 있는 요소를 가리키며 rear 포인터는 맨 뒤에 있는 요소를 가리킨다. 큐에 요소가 없는 경우에는 front 와 rear 는 NULL 값이 된다. 큐의 요소들은 구조체로 정의되며 이 구조체는 데이터를 저장하는 data 필드와 다음 노드를 가리키기 위한 포인터가 들어 있는 link 필드로 이뤄져있다.

//연결된 큐 정의
typedef int element;
typedef struct QueueNode { //큐의 노드의 타입입
  element data;
  struct QueueNode *link;
} QueueNode;

typedef struct { //큐 ADT 구현현
  QueueNode *front, *rear;
} LinkQueueType;

• 삽입 연산

삽입 연산은 먼저 동적 메모리 할당을 통하여 새로운 노드를 생성한 다음, 데이터를 저장하고 연결 리스트의 끝에 새로운 노드를 추가하면 된다.

위의 사진은 삽입 연산의 과정을 보여준다. 그림 (a) 와 같이 만약 큐가 공백상태이면(front 와 rear 가 모두 NULL) front 와 rear 모두 새로운 노드를 가리키도록 해야한다. 만약 (b) 와 같이 공백상태가 아니고 기존의 노드가 있는 경우라면 rear 가 가리키고 있는 노드의 링크 필드와 rear 를 새로운 노드를 가리키도록 변경하면 된다.

void enqueue(LinkQueueType *q, element data)
{
  QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
  temp->data = data; //데이터 저장
  temp->link = NULL; //링크 필드를 NULL
  if (is_empty(q)) {
    q->front = temp;
    q->rear = temp;
  }
  else {
    q->rear->link = temp; //순서 중요
    q->rear = temp;
  }
}

 

 

• 삭제 연산

삭제 연산은 연결 리스트의 처음에서 노드를 꺼내오면 된다.

위의 사진은 삭제 연산의 과정을 보여준다. 삭제 연산은 먼저 큐가 공백상태인가를 검사하여야 한다. 만약 공백상태라면 당연히 오류가 된다. 현재 구현에서는 오류이면 오류 메세지를 출력하고 종료하도록 되어 있다. 만약 공백상태가 아니라면 front 가 가리키는 노드를 temp 가 가리키도록 하고 front는 front 의 링크값으로 대입한다. 그러면 front 는 현재 가리키는 노드의 다음 노드를 가리키게 될 것이다. 그런 다음 temp 가 가리키는 노드로부터 데이터를 꺼내오고 동적 메모리 해제를 통하여 이 노드를 삭제하면 된다.

//삭제 함수
element dequeue(LinkQueueType *q)
{
  QueueNode *temp = q->front;
  element data;
  if (is_empty(q)) {
    fprintf(stderr,"스택이 비어있음\n");
    exit(1);
  }
  else {
    data = temp->data;
    q->front = q->front->link; //front 를 다음노드를 가리키도록
    if (q->front == NULL)
      q->rear = NULL;
    free(temp);
    return data;
  }
}