큐

큐 (Queue)

특징

1. 데이터가 뒤(rear)로 들어가서 앞(front)으로 나오는 자료

2. FIFO (First In First Out)

3. 스케줄링, 탐색 알고리즘 등에서 사용된다.

구현

배열로 구현

선언

• 배열은 사전에 배열의 크기를 지정해줘야한다.
• front와 rear를 선언해준다.

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

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

삽입

• 큐는 한 쪽으로만 데이터가 들어간다.
• 큐의 마지막인 rear에 1을 추가하여 데이터를 삽입해준다.
• 배열의 크기를 초과했을 때는 큐 오버플로우를 선언해준다.

void push(int data) {
   if (rear >= SIZE) {
      printf("큐 오버플로우가 발생했습니다. \n");
      return;
   }
   queue[rear++] = data;
}

삭제

• 큐는 삽입과 같이 한 쪽에서만 데이터가 나온다.
• 큐의 front++를 return함으로써 front를 제거한다.
• 큐가 비어있을 때 시도하면 언더플로우를 선언한다.

void pop() {
   if (front == rear) {
      printf("큐 언더플로우가 발생했습니다. \n");
      return -INF;
   }
   return queue[front++];
}

모든 코드 확인하기

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

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


void push(int data) {
   if (rear >= SIZE) {
      printf("큐 오버플로우가 발생했습니다. \n");
      return;
   }
   queue[rear++] = data;
}

void pop() {
   if (front == rear) {
      printf("큐 언더플로우가 발생했습니다. \n");
      return -INF;
   }
   return queue[front++];
}

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

int main(void) {
   push(7);
   push(5);
   push(1);
   pop();
   show();
   system("pause");
   return 0;
}

연결리스트로 구현

선언

• data와 노드와 다음 데이터를 연결하는 next를 구조에 포함한다.
• 데이터가 나오는 front, 들어가는 node, 데이터 수를 담을 count를 선언한다.

#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;

삽입

• 새로운 node를 동적메모리에 할당해준다.
• node에 데이터를 담고, next는 NULL로 초기화해준다.
• 조건문을 통해 큐에 데이터가 없을 시 front로 선언한다.
• 데이터가 존재할 시 큐의 rear가 node를 가리키게 한다.
• 큐의 rear를 node로 지정하고, count를 추가해준다.

void push(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++;
}

삭제

• 큐에 데이터가 없을 시 실행하면 언더플로우를 선언해준다.
• 큐의 front를 담을 노드를 생성하고, 데이터도 담아준다.
• 큐의 front를 위 노드의 next로 선언한다.
• 기존의 front 다음의 데이터가 front가 되는 것
• 원래의 front를 담고 있던 node를 해제해주고, count를 감소시킨다.

void pop(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;
}

모든 코드 확인하기

#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 push(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++;
}

void pop(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;
   printf("---큐의 앞---\n");
   while (cur != NULL) {
      printf("%d\n", cur->data);
      cur = cur->next;
   }
   printf("---큐의 뒤---");
}

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