Queue란?

<aside> 💡 Queue의 정의와 이용

</aside>

• 일반적 의미에서는 대기열을 뜻함.
• 자료구조에서는 선입선출 방식(First in First out)이며 스택과는 반대이다.
• semaphore 등 많은 부분에서 queue가 이용된다.

Deque란?

<aside> 💡 Deque의 정의와 이용

</aside>

• queue나 stack과는 달리 rear와 front 모두에서 추가와 반환이 가능한 자료구조.
• front와 rear를 가리켜야 하기 때문에 double linked list를 이용한다.

• 따라서 스택과 큐에서 하지 못하는 동작들을 모두 구현할 수 있다.

헤더 분석

#ifndef _LINKED_DEQUE_
#define _LINKED_DEQUE_

typedef struct DequeNodeType
{
	char data;
	struct DequeNodeType* pRLink;//오른쪽 링크
	struct DequeNodeType* pLLink;//왼쪽 링크
} DequeNode;

typedef struct LinkedDequeType
{
	int currentElementCount;//현재 원소 개수
	DequeNode* pFrontNode;//frontNode의 주소
	DequeNode* pRearNode;//RearNode의 주소
} LinkedDeque;

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

LinkedDeque* createLinkedDeque();
int insertFrontLD(LinkedDeque* pDeque, DequeNode element);
int insertRearLD(LinkedDeque* pDeque, DequeNode element);
DequeNode* deleteFrontLD(LinkedDeque* pDeque);
DequeNode* deleteRearLD(LinkedDeque* pDeque);
DequeNode* peekFrontLD(LinkedDeque* pDeque);
DequeNode* peekRearLD(LinkedDeque* pDeque);
void deleteLinkedDeque(LinkedDeque* pDeque);
int isLinkedDequeFull(LinkedDeque* pDeque);
int isLinkedDequeEmpty(LinkedDeque* pDeque);

#endif

#ifndef _COMMON_QUEUE_DEF_
#define _COMMON_QUEUE_DEF_

#define TRUE		1
#define FALSE		0

#endif

• deque를 구현하려면 doubly linked list를 이용해야 한다. 또, front와 rear의 주소를 가지고 있어야 front와 rear에서의 추가와 반환을 구현할 수 있기에 LinkedDeque 구조체에는 현재 원소 개수와 front노드, rear노드의 주소가 저장될 수 있도록 멤버변수가 있다.
• Linked List의 노드 부분은 data값과 오른쪽, 왼쪽 링크로 구성되어 있어 일반 링크드 리스트와는 다르게 어느 방향이던지 순회할 수 있다.

createLinkedDeque 구현

LinkedDeque* createLinkedDeque()
{
  LinkedDeque *pReturn;
  pReturn = (LinkedDeque *)calloc(1, sizeof(LinkedDeque));//LinkedDeque 변수를 동적할당 후 0으로 초기화
  if (pReturn == NULL)//동적할당 실패
  {
    printf("malloc failure\\n");
    return (NULL);
  }
  return (pReturn);
}

함수 기능 : 덱을 하나 만들고, 이 주소값을 반환하는 함수.