큐(queue) 정의

  • 큐는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료구조 이다.

  • 스케쥴링, 탐색 알고리즘 등에서 다방면으로 활용된다.

  • push,pop연산이 있다.

image.png

큐(queue) 구현

  • 큐는 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현방법으로 나눠진다.
  • 가장 기본적인 자료구조로 난이도는 낮은편

배열을 이용한 큐(queue)

Queue 선언


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

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

삽입 함수(push)


void push(int data) {

  if ( rear >= SIZE ) {
      printf(" Queue OverFlow " );
    return ;
  }
  queue[rear++] = data;
}

삭제 함수(pop)

int pop() {

    if (front == rear) {
        printf("Queue UnderFlow");
      return -INF;
    }  
      return queue[front++];
}

출력함수(show)

void show() {
    printf("---- queue front---");
      for(int i = front; i < rear; i++ ) {

        printf("%d\n",queue[i]);
    }
  printf("----queue rear ---");
}

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

큐의 선언

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

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

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

큐의 삽입(push)

image.png

image.png

image.png

image.png

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; //front 에 node를 넣어준다.
    }
      else {
        queue->rear->next = node; //rear의 다음 노드로 새 노드가 된다.
    }
    queue->rear = node; // rear가 해당 노드가 된다.
      queue->count++;
}

큐의 추출(pop)

image.png

image.png

image.png

int pop(Queue *queue) {
    if(queue->count == 0) {
        printf("Queue Underflow\n");
        return INF;
    }
      Node *node = queue->front;
      int data = node->data;
      queue->front = node->next;
      free(node);
      queue->count--;
      return data;
}

큐 출력(show)

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

메인 함수

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