Queue - C

Q U E U E - C

지난 Stack에 이어 요번엔 Queue를 만들어 보았다.
Queue(큐)는 스택과 달리 먼저 들어간것이 먼저 나오는 FIFO(First In, First Out)를 따르게 된다.
스택과 큐는 자료구조중 가장 기본이 되는 자료구조이므로 잘 알아두고 쓰는게 좋지 않을까 생각한다.

먼저 큐에서 필요한 함수를 작성했다.

void init();     //프로그램 시작시 필요한 동적메모리 할당 하는 함수
void put(int); //큐에 자료를 넣는 함수
int get();       //큐에 있는 자료를 가져오는 함수 ( 맨 앞의 자료)
void clear();  //큐에 있는 자료 비우는 함수
void print();   //출력 함수

물론 여기서 가장 중요한것은 Put, Get이다. 나머지는 프로그램을 테스트 할때 필요한 것이라고 보면된다.


또한 동적메모리를 할당해 링크드리스트로 만들기 위해 구조체 선언을 했다.

typedef struct _node{

 struct _node *prev;
 int key;
 struct _node *next;
}node;

지난 스택과 다른 점이 있다면 큐에서는 앞의 노드의 주소를 저장할수 있는 공간이 추가 되었다는것이다.
이유로는 Put 함수를 부를때에 앞에 저장된 내용이 없다면 처음부터 끝까지 루프를 돌아 찾아가야된다는
작은 문제가 있다. 자료가 많지 않을때는 빠를수도 있지만 자료가 무한대로 많아질수록 속도는 그만큼
느려지기 때문에 이번은 이와같이 선언을 했다.

프로그램에서 계속 쓰이면서 중요한 정보를 저장하는 전역변수

node *front, *rear;

영어 그대로 front는 큐의 앞부분을 rear는 큐의 맨 마지막을 저장하는 전역변수이다.

함수코드

//프로그램 시작될때 동적메모리 할당하는 함수
void init(){

 front = (node*)malloc(sizeof(node));
 rear = (node*)malloc(sizeof(node));

 front->next = rear;
 front->prev = front;
 rear->next = rear;
 rear->prev = front;
 
}

//queue 에 자료를 넣는 함수
void put(int value){

 node *t;

 t = (node*)malloc(sizeof(node));

 t->key = value;
 t->prev = rear->prev;
 rear->prev->next = t;
 t->next = rear;
 rear->prev = t;
 
}

//queue에서 자료를 뺄때 사용하는 함수
int get(){
 
 node *t;
 t = front->next;
 
 if(t->next == rear){
  printf("No Data in Queue\n");
  return 0;
 }

 front->next = front->next->next;
 front->next->prev = front;

 return t->key;
}

//queue 안에 있는 모든 자료 삭제
void clear(){

 node *t;

 while(front->next != rear){
  t = front->next;
  front->next = front->next->next;
  front->next->prev = front;
  free(t);

 }
 
}

//출력 함수
void print(){

 node *t;

 t = front->next;
 while(t->next != rear){
 
  printf("%d -> ",t->key);
  t = t->next;  

 }
}

자료구조에서 스택과 같이 중요한 부분인 '큐' 이다. 잘 이해를 해야될것 같고
물론 배열로 만들수도 있는부분이다. 좀더 유연성이 있는걸로 하자는 생각하에 링크드리스트로 한 것 뿐.

- 역시나 지저분한 코드 (빠지지 않고 쓰는 거 같다 하핫//)
- 오랜만에 하다보니깐 정말 기억이 나질 않아서 걱정이다.
- 계속적으로 공부를 해야겠다는 생각을 하면서 마친다.