[C언어] Queue (큐)

FIFO(First-In First-Out), 선입선출의 특성

 

구현해야 하는 필수 요소

• 인큐 연산
  • 데이터 삽입하는 연산
  • ⚠️ 큐의 크기를 초과해 새로운 자료를 추가하지 못하는 현상을 오버플로
• 디큐 연산
  • 데이터 삭제하는 연산
  • ⚠️ 아무 자료가 없는 빈 큐에 연산을 하게 되면 언더플로 현상 발생
• 피크 연산
  • 프론트에 있는 데이터 제거 🚫

기다리는 줄, 공유된 프린터 하나에서 일쇄될 차례를 기다리는 것 등에 사용

 

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h>

# define  TRUE  1
# define  FALSE 0

typedef struct DequeNodeType { 
    int data; 
    struct DequeNodeType *pLLink; 
    struct DequeNodeType *pRLink;
} DequeNode;

typedef struct DequeType {
    int currentCount; 
    DequeNode *pFrontNode;
    DequeNode *pRearNode;
} Deque;

Deque     *createDeque(void);
DequeNode *createNode(int data);
int       deleteDeque(Deque *pList);
int       insertFront(Deque *pList, int data);
int       deleteFront(Deque *pList);
int       insertRear(Deque *pList, int data);
int       deleteRear(Deque *pList);
void      displayDeque(Deque *pList);

#include "Deque.h"

Deque *createDeque(void) { 
  Deque *pReturn = (Deque *)malloc(sizeof(Deque)); 
  if(pReturn != NULL)
    memset(pReturn, 0, sizeof(Deque)); 
  pReturn->pFrontNode = createNode(0);
  pReturn->pRearNode = createNode(0);
  return pReturn; 
}

DequeNode *createNode(int data) {
  DequeNode *ret = (DequeNode *)malloc(sizeof(DequeNode));
  if (ret != NULL)
    memset(ret, 0, sizeof(DequeNode));
  else {
    printf("ERROR give me the memory\n");
    return NULL;
  }
  ret->data = data;
  return ret;
}

int   deleteDeque(Deque *pList) {
  if (!pList)
  {
    printf("Deque does not exist\n");
    return FALSE;
  }

  while (pList->currentCount) {
    deleteFront(pList);
  }
  free(pList);
}

int insertFront(Deque *pList, int data) {
  DequeNode *newNode = createNode(data);

  if (!pList)
  {
    printf("Deque does not exist\n");
    return FALSE;
  }
  if (!newNode)
    return FALSE;

  if (!pList->currentCount) {
    pList->pFrontNode->pLLink = newNode;
    pList->pRearNode->pRLink = newNode;
  }
  else {
    newNode->pRLink = pList->pFrontNode->pLLink;
    pList->pFrontNode->pLLink->pLLink = newNode;
    pList->pFrontNode->pLLink = newNode;
  }
  pList->currentCount++;
}

int deleteFront(Deque *pList) {
  DequeNode *preNode;
  DequeNode *delNode;

  delNode = pList->pFrontNode->pLLink;
  if (!pList->currentCount)
    return FALSE;
  else if (pList->currentCount == 1) {
    pList->pFrontNode->pLLink = NULL;
    pList->pRearNode->pRLink = NULL;
  }
  else {
    preNode = delNode->pRLink;
    pList->pFrontNode->pLLink = preNode;
    delNode->pRLink = NULL;
  }
  free(delNode);
  pList->currentCount--;
  return TRUE;
}

int insertRear(Deque *pList, int data) {
  DequeNode *newNode = createNode(data);

  if (!pList)
  {
    printf("Deque does not exist\n");
    return FALSE;
  }
  if (!newNode) {
    return FALSE;
  }
  if (!pList->currentCount) {
    pList->pFrontNode->pLLink = newNode;
    pList->pRearNode->pRLink = newNode;
  }
  else {
    newNode->pLLink = pList->pRearNode->pRLink;
    pList->pRearNode->pRLink->pRLink = newNode;
    pList->pRearNode->pRLink = newNode;
  }
  pList->currentCount++;
}

int deleteRear(Deque *pList) {
  DequeNode *preNode;
  DequeNode *delNode;

  delNode = pList->pRearNode->pRLink;
  if (!pList->currentCount)
    return FALSE;
  else if (pList->currentCount == 1) {
    pList->pFrontNode->pLLink = NULL;
    pList->pRearNode->pRLink = NULL;
  }
  else {
    preNode = delNode->pLLink;
    pList->pRearNode->pRLink = preNode;
    delNode->pLLink = NULL;
    preNode->pRLink = NULL;
  }
  free(delNode);
  pList->currentCount--;
  return TRUE;
}

void  displayDeque(Deque *pList) {
  DequeNode *current;

  if (!pList)
  {
    printf("Deque does not exist\n");
    return ;
  }
  if (!pList->currentCount)
    return;
  current = pList->pFrontNode->pLLink;
  while(current)
  {
    printf("%d->", current->data);
    current = current->pRLink;
  }
  printf("\n");
}