[ 자료구조 ] 연결리스트를 이용한 큐의 구현 | 연결큐

연결 큐

1차원 배열을 이용하기 때문에 크기가 정해져 있는 원형 큐의 문제점을 보완해 나온 것이 연결 리스트를 이용한 연결 큐.

원형 큐에 대한 설명은 아래 글로 👇🏻

https://tildacoderecorder.tistory.com/102

[ 자료구조 ] enQueue()와 deQueue() 함수를 이용한 원형큐

 

큐의 원소는 연결 리스트의 노드이고, 각 노드를 포인터로 연결한다.

연결 큐의 구조

 

front = 첫 번째 노드를 가리키는 포인터 변수 (기존 연결 리스트의 head와 같다.)

rear = 마지막 노드를 가리키는 포인터 변수

초기 상태와 공백 상태 : front = rear = null

연결 큐는 노드를 무한으로 생성해 추가할 수 있기 때문에 큐의 포화 상태는 확인하지 않는다. 대신 공백 상태는 확인해야 하는데 첫번째 노드를 가리키는 front의 포인터 변수가 null이라면 공백 상태.

기본 설정

#include<stdio.h>
#include<stdlib.h>
 
typedef struct node {
  int data;
  struct node* next;
} Node;
 
Node *front = NULL;
Node *rear = NULL;

 

정수형 데이터와 포인터 변수 next를 가진 노드 생성 후 front와 rear를 NULL로 초기화.

 

연결 큐의 삽입 알고리즘

 

int enQueue(int item) {
 
  Node* new = (Node*)malloc(sizeof(Node));
 
  new->data = item;
  new->next = NULL;
 
  if ( front == NULL ) {
    rear = new;
    front = new;
    return 1;
  }
 
  rear->next = new;
  rear = new;
  return 1;
}

 

먼저 새 노드 new를 생성해준 뒤, data에 삽입할 원소 item을 넣어준다.

그 후, if문으로 연결큐의 공백 상태를 확인해준다. 만약 공백 상태여서 새 노드 new가 첫번째 노드라면, front와 rear 모두 new를 가리키도록 하고 1을 리턴하며 종료한다.

그렇지 않다면 연결 큐의 노드 중 가장 마지막이 되므로 rear가 가리켜야 한다. 현재 rear는 노드 new가 들어오기 전 마지막 노드를 가리키고 있으므로 먼저 rear->next는 마지막 노드의 포인터 변수이다. 노드와 노드를 연결시켜야 하기 때문에 마지막 노드의 포인터 변수가 새 노드 new를 가리키도록 rear->next = new를 해준다.

마지막으로 rear = new로 rear가 new를 가리키도록 하고 1을 리턴하며 종료.

 

연결 큐의 삭제 알고리즘

 

int deQueue() {
  if( front == NULL ) return 0;
 
  Node* old = (Node*)malloc(sizeof(Node));
 
  old = front;
  int item = front->data;
  front = front->next;
 
  if ( front == NULL ) rear = NULL;
 
  return item;
}

 

큐는 선입선출의 구조로 가장 첫번째 데이터가 삭제되기 때문에 front가 가리키는 노드가 삭제되어야 한다. 먼저 공백 상태를 확인해 삭제할 노드가 없다면 에러 메세지와 함께 종료.

그렇지 않다면 삭제를 도와줄 새 노드 old 생성 후, old = front로 old와 front 모두 첫번째 노드를 가리키도록 한다. item이라는 정수형 변수를 만들어 front가 가리키는 첫번째 노드의 data를 담는다.

이후 front = front->next로 front->next는 첫번째 노드의 포인터 변수가 가리키고 있던 두번째 노드이다. front가 두번째 노드를 가리키도록 함으로써 첫번째 노드는 논리적으로 삭제되는 셈이다.

마지막으로 연결 큐에 노드가 딱 하나 존재해서 front도 rear도 모두 첫번째 노드를 가리키고 있는 상태에서 첫번째 노드를 삭제 해 front가 NULL이 되었다면 rear도 NULL이 되어야 하므로 rear = NULL 하며 삭제한 원소 item을 리턴하며 종료.

 

참고 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미