[자료구조] 큐 (2) - 덱

📕덱: double ended queue, 큐의 전단과 후단에서 모두 삽입삭제가 가능하다. 원형큐를 조금 변형시키면 구현 가능

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

#define N 10

typedef char element;  //char라는 기본 데이터 타입을 element라는 이름으로 정의하겠다.

typedef struct //typedef 하면 구조체 이름 생략 가능, 자기 참조 필드가 없기 때문에 생략 가능함
{
	element queue[N];
	int front, rear;
}Dequetype;

void init(Dequetype* D) //구조체 포인터로 받기
{
	D->front = D->rear = 0;
}

int isEmpty(Dequetype* D)
{
	//top처럼 올라갔다 내려오는게 아니라 계속 오른쪽으로 가니까, 한번이라도 뭔가 있었다면 -1이 될 수 없음
	return D->rear == D->front;
}

int isFull(Dequetype* D)
{
	return ((D->rear + 1) % N == D->front); //전체 배열의 크기 -1만큼
}

void addFront(Dequetype* D, element e)
{
	if (isFull(D))
		printf("FULL!\n");
	else
	{
		D->queue[D->front] = e;
		D->front = (D->front - 1 + N) % N;
	}

}

void addRear(Dequetype* D, element e)// enqueue
{
	if (isFull(D))
		printf("FULL!\n");
	else
	{
		D->rear = (D->rear + 1) % N;
		D->queue[D->rear] = e;
	}
}

element deleteFront(Dequetype* D)
{
	if (isEmpty(D))
	{
		printf("Empty!!\n");
		return -1;
	}

	D->front = (D->front + 1) % N;
	return D->queue[D->front];
}

element deleteRear(Dequetype* D)
{
	if (isEmpty(D))
	{
		printf("Empty!!\n");
		return -1;
	}

	int pos = D->rear;
	D->rear = (D->rear - 1 + N) % N;
	return D->queue[pos];
}

element getFront(Dequetype* D)
{
	if (isEmpty(D))
	{
		printf("Empty!!\n");
		return -1;
	}

	return D->queue[(D->front + 1) % N];
}

element getRear(Dequetype* D)
{
	if (isEmpty(D))
	{
		printf("Empty!!\n");
		return -1;
	}

	return D->queue[D->rear];
}


void print(Dequetype* D)
{
	printf("Front Pos : %d, Rear Pos: %d\n", D->front, D->rear);

	int i = D->front;
	while (i != D->rear)
	{
		i = (i + 1) % N;
		printf("[%c] ", D->queue[i]);
	}
	printf("\n");
}

int main()

{
	Dequetype D;
	init(&D); //Q의 주소가 날라간다
	srand(time(NULL));

	for (int i = 0; i < 7; i++)
		addRear(&D, rand() % 26 + 65); //아스키코드 대문자, 알파벳 값 난수로 발생

	print(&D);

	for (int i = 1; i < 3; i++)
		printf("[%c]", deleteFront(&D));
	printf("\n\n");

	print(&D);

	for (int i = 0; i < 7; i++)
		addFront(&D, rand() % 26 + 65);

	print(&D);

	for (int i = 1; i < 3; i++)
		printf("[%c]", deleteRear(&D));
	printf("\n\n");

	print(&D);
}