C언어 자료구조 큐 개념과 구현(1) queue

1]큐의 기본개념과 성격 

 1)큐(queue) 스택과 같은 리스트이다.

 단 데이터의 삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서만 일어남

 삽입이 일어나는 쪽을 rear, 삭제가 일어나는 쪽을 front라고 부름

 FIFO(First-In, First-Out)라고 불림

 예:프린터 큐, 등 

 

 

2)큐가 지원하는 연산 (다양한 연산의 이름이 있다.)

 

 oInsert, enqueue, offer, push :큐의 rear에 새로운 원소를 삽입하는 연산이다

 oRemove, dequeue, pool, pop  :큐의 front에 있는 원소를 큐로부터 삭제하는 연산.

 oPeek,element,front:큐에 front에 있는 원소를 제거하지 않고 반환하는 연산

 oIs_empty:큐가 비었는지 검 

  

  

 

 

 

 2]큐의 응용 

 

 ocpu 스케쥴링

  multitasking환경에서 프로세스들은 큐에서 cpu가 할당되기를 기다린다

 o데이터 버퍼 

  네트워크를 통해 전송되는 패킷(packet)들은 도착한 순서대로 버퍼에 저장되어

  처리되기를 기다린다. 

 

 o그 외에도 자원을 공유하는 대부분의 경우에 큐가 사용됨 

 ex)mp3 음악리스트, 줄서기,.. 

 

 

 

 

3]큐의 구현

배열 혹은 연결리스트를 이용한

 연결리스트를 먼저 구현하고 다음 배열로 구현하자.

 실제로는 연결리스트가 더 효율적으로 표현과 처리가 가능하다 

 

 

 

 

 rear에서 삭제를 할려면 왼쪽 노드의 주소를 알아야 삭제가 가능하기 때문에

 여기서는 삽입 처리를 한다. 

 front에서는 삽입,삭제가 용이하기 때문에 삭제처리를 한다. 

 

 

 //헤더파일 정의

 #ifndef QUEUEADT_H

 #define QUEUEADT_H

 

 #include <stdbool.h> 

 

 typedef int Item;

 

 typedef struct queue_type *Queue;

 

 Queue create();

 void destroy(Queue q);

 void make_empty(Queue q);

 bool is_empty(Queue q);의 

 void enqueue(Queue q, Item i);

 Item dequeue(Queue q);

 Item peek(Queue q);

 int get_size(Queue q);

 

 



#include <stdio.h>

#include <stdio.h>

#include <stdio.h>



struct node {

 Item data;

 struct node *next;

};

 

 struct queue_type {

  struct node *front;

  struct node *rear;

  int size;

 };

 

 void terminate(const char *message)

 {

  printf("%s\n", message);

  exit(EXIT_FAILURE);

 }

 

 int get_size(Queue q)

 {

  return q->size;

 }

 

 Queue create()

 {

  Queue q = malloc(sizeof(struct queue_type));

  if(q == NULL)

   terminate("Error in create: queue could not be created");

  q->front = NULL;

  q->rear = NULL;

  q->size = 0;

  return q;

 }

 

 void destroy(Queue q)

 {

  make_empty(q);

  free(q);

 }

 

 void make_empty(Queue q)

 {

  while(!is_empty(q))

   dequeue(q);

  q->size = 0;

 }

 

 bool is_empty(Queue q)

 {

  return q->front == NULL;

 }

 

 void enqueue(Queue q,Item i)

 {

  struct node *new_node = malloc(sizeof(struct node));

  if(new_node == NULL)

   terminate("Error in push: queue is full.");

  new_node->data = i;

  new_node->next = NULL;

  if(q->front == NULL){

   q->front = new_node;

   q->rear = new_node;

  }

  else {

   q->rear->next = new_node;

   q->rear = new_node;

  }

  q->size++;

 }

 

 

 Item dequeue(Queue q)

 {

  struct node *old_front;

  Item i;

  if(is_empty(q))

   terminate("Error in dequeue: queue is empty.");

  old_front = q->front;

  i = old_front -> data;

  q->front = old_front->next;

  if(q->front == NULL)

     q->rear == NULL;

  free(old_front);

  q->size--;

  return i;

  

 }

 

 Item peek(Queue q)

 {

  if(is_empty(q))

   terminate("Error in peek: queue is empty");

  return q->front->data;

 }