연결리스트 큐

-배열로 구현된 큐에 비해 크기가 제한되지 않지만

코드가 더 복잡해지고 링크필드때문에 메모리 공간을 더 많이 사용한다.

- 기본적인 구조는 단순 연결 리스트에 2개의 포인터를 추가한 것과 같다.

- front - 연결리스트의 맨앞으로 삭제와 관련된다.

- rear - 연결리스트의 맨 뒤로 삽입과 관련된다.

- 공백의 경우 front와 rear는 NULL값.

- 큐의 각 요소는 (데이터+링크)로 이루어진 구조체로 정의된다.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef int element;
typedef struct QueueNode {
 element item;
 struct QueueNode *link;
} QueueNode;

typedef struct {
 QueueNode *front, *rear;    //큐노드를 가리킬 수 있는 front와 rear 포인터
} QueueType;

//에러처리

void error(char *message)
{
 fprintf(stderr, "%s\n", message);
 exit(1);
}

//초기화

void init(QueueType *q)
{
 q->front = q->rear =0;
}

//공백상태 검출
int is_empty(QueueType *q)
{
 return (q->front == NULL);
}
//포화상태 검출
int is_full(QueueType *q)
{
 return 0;
}

//삽입함수
void enqueue(QueueType *q, element item)
{
 QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
 if(temp == NULL) error("메모리를 할당 할 수 없습니다.");
 else {
  temp->item = item;
  temp->link = NULL;
  if(is_empty(q)) {
   q->front = temp;
   q->rear = temp;
  }
  else {
   q->rear->link = temp;
   q->rear = temp;
  }
 }
}

//삭제

element dequeue(QueueType *q)
{
 QueueNode *temp = q->front;                  //아리송...
 element item;

 if(is_empty(q)) error("큐가 비어있습니다.");
 else {
  item = temp->item;
  q->front = q->front->link;

  if(q->front == NULL) q->rear = NULL;
  free(temp);
  return item;
 }
}

//peek

element peek(QueueType *q)
{
 element item;
 if(is_empty(q)) error("큐가 비어있습니다.");
 else {
  item = q->front->item;
  return item;
 }
}

//main

void main()
{
 QueueType q;

 init(&q);              //초기화

 enqueue(&q, 1);
 enqueue(&q, 2);
 enqueue(&q, 3);

 printf("dequeue() = %d\n", dequeue(&q));
 printf("dequeue() = %d\n", dequeue(&q));
 printf("dequeue() = %d\n", dequeue(&q));
}