큐(Queue)

  큐(Queue)는 뒤로 들어가서 앞으로 나오는 자료구조로 선입선출(First In First Out, FIFO)형태이며

  이러한 특성때문에 스케쥴링, 탐색 알고리즘 등에서 다방면으로 활용된다.

  스택(Stack)에서와 마찬가지로 push는 데이터를 넣어주고 pop은 데이터를 뺀다.

  보통 큐를 사용할때는 enQueue, deQueue를 많이 사용한다고 한다.

  enQueue가 push와 같고 deQueue가 pop과 같다. 스택과 혼동할 수 있기 때문에 enQueue, deQueue로 사용한다.

 

 

  큐는 배열을 이용한 구현방법과 연결리스트를 이용한 구현방법으로 나누어지는데

  가장 기본적인 형태의 자료구조로 구현 난이도는 낮은편이다.

 

  배열을 이용한 구현방법

#include <stdio.h>
#define SIZE 10000
#define INF 99999999

int queue[SIZE];
int front = 0;
int rear = 0;

void enQueue(int data){
  if(rear >= SIZE){
    printf("큐 오버플로우 발생\n");
    return;
  }
  queue[rear++] = data;
}

int deQueue(){
  if(front == rear){
    printf("큐 언더플로우 발생.\n");
    return -INF;
  }
  return queue[front++];
}

void show(){
  for(int i = front; i < rear; i++){
    printf("%d\n", queue[i]);
  }
}

int main(void){
  enQueue(7);
  enQueue(5);
  enQueue(4);
  deQueue();
  enQueue(6);
  show();
  system("pause");
  return 0;
}

  결과값은 5 4 6이다.

  넘겨준 값이 queue의 rear번째에 들어가는데 rear의 초기값은 0이기 때문에 queue[0]에 첫 값이 들어가고

  rear는 후치증가로 값이 1 증가하게 된다.

  그래서 다음 값이 queue[1]에 들어가는 방식으로 처리된다.

  deQueue에서는 맨 앞에 있는 값이 삭제되는 방식이기에 따로 넘겨주는 값은 없고 front에 있는 값을 날려준다.

  출력에서 front가 1증가한 상태이기 때문에 i = 1이 되고 queue에서 0번인덱스부터가 아닌 1번 인덱스부터

  출력해줌으로써 5 4 6 만 출력이 되게 된다.

  

  연결리스트를 이용한 큐 구현

#include <stdio.h>
#include <stdlib.h>
#define INF 99999999

typedef struct{
  int data;
  struct Node *next;
} Node;

typedef struct{
  Node *front;
  Node *rear;
  int count;
} Queue;

void enQueue(Queue *queue, int data){
  Node *node = (Node*)malloc(sizeof(Node));
  node->data = data;
  node->next = NULL;
  if(queue->count == 0){
    queue->front = node;
  }else{
    queue->rear->next = node;
  }
  queue->rear = node;
  queue->count++;
}

int deQueue(Queue *queue){
  if(queue->count == 0){
    printf("큐 언더플로우 발생.\n");
    return -INF;
  }
  Node *node = queue->front;
  int data = node->data;
  queue->front = node->next;
  free(node);
  queue->count;
  return data;
}

void show(Queue *queue){
  Node *cur = queue->front;
  
  while(cur != NULL){
    printf("%d\n", cur->data);
    cur = cur->next;
  }
}

int main(void){
  Queue queue;
  queue.front = queue.rear = NULL;
  queue.count = 0;
  enQueue(&queue, 7);
  enQueue(&queue, 5);
  enQueue(&queue, 4);
  deQueue(&queue);
  enQueue(&queue, 6);
  show(&queue);
  system("pause");
  return 0;
}

 

  큐 삽입과정

  기본형태에서부터 front와 rear가 존재한다.

  그리고 enQueue를 하게 되면  rear뒤에 노드가 하나 들어오게 되는데 그럼 rear의 next가 새로운 노드를 가리키도록

  하고 새로운 노드를 rear로 만들어준다.

  rear의 next를 새로운 노드로 연결해주는 이유는 들어가있는 값이 있다면 그 마지막 노드인 rear의 next를 연결해줘야

  그 뒤로 새로운 노드를 연결하게 되는것이고 그 다음 rear를 새로 넣어준 노드로 다시 지정해주는 것이기 때문이다. 

  삭제의 경우는 앞에서부터 삭제하기 때문에 front를 두번째 노드로 옮기고 첫번째 노드를 메모리해제하면 된다.

 

 

레퍼런스

패스트캠퍼스 올인원 패키지 - 소프트웨어 베이직