Deque

Queue

이번 목표는 자료구조중 하나인 Deque를 c 언어로 구현하는 것 이다. Deque의 경우 흔히 덱 이라고 부르는데, 이는 기존 큐랑 다르게 앞, 뒤에서 다 출력이 가능하다.

기능

큐에 기본 기능들은 init, push, pop, size, empty, front, back이다.

init -> 덱 초기화

push front -> 데이터를 가장 앞에 삽입

push back -> 데이터를 가장 뒤에 삽입

pop front-> 가장 앞 데이터 추출

pop back -> 가장 뒤 데이터 추출

size -> 큐 크기 확인

empty -> 큐가 비어있는지 유무 확인

front -> 가장 앞에 데이터 확인

back -> 가장 뒤에 있는 데이터 확인

구현

#include <stdio.h>
#include <string.h>
#define SIZE 10000

typedef struct{
	int arr[SIZE];
	int front;
	int back;
}Deque;

void init(Deque *d)
{
	d->front = 0;
	d->back = 0;
	return;
}

int empty(Deque *d)
{
	return(d->front == d->back);
}


void push_front(Deque *d, int num)
{
	d->arr[d->front] = num;
	d->front = (d->front + SIZE -1) % SIZE;
	return;
}

void push_back(Deque *d, int num)
{
	d->back = (d->back +1) %SIZE;
	d->arr[d->back] = num;
	return;
}

int pop_front(Deque *d)
{
	if(empty (d))
	{
		return -1;
	}
	d->front = (d->front+1) %SIZE;
	int temp = d->arr[d->front];
	return temp;
}

int pop_back(Deque *d)
{
	if(empty (d))
	{
		return -1;
	}
	int temp = d->arr[d->back];
	d->back = (d->back + SIZE -1) %SIZE;
	
	return temp;
}

int size(Deque *d)
{
	return (d->back - d->front + SIZE )%SIZE;
}

int front(Deque *d)
{
	if(empty (d))
	{
		return -1;
	}
	int temp = (d->front+1)%SIZE;
	return d->arr[temp];
}

int back(Deque *d)
{
	if(empty (d))
	{
		return -1;
	}
	return d->arr[d->back];
}

int main()
{
	int Tc;
	int num;
	char input[12];
	Deque d;
	init(&d);
	
	scanf("%d",&Tc);
	
	for(int i = 0; i<Tc; i++)
	{
		scanf("%s",&input);
		if(strcmp(input,"push_front")==0)
		{
			scanf("%d",&num);
			push_front(&d,num);
		}
		else if(strcmp(input,"push_back")==0)
		{
			scanf("%d",&num);
			push_back(&d,num);
		}
		else if(strcmp(input,"pop_front")==0)
		{
			printf("%d\n",pop_front(&d));
		}
		else if(strcmp(input,"pop_back")==0)
		{
			printf("%d\n",pop_back(&d));
		}
		else if(strcmp(input,"size")==0)
		{
			printf("%d\n",size(&d));
		}
		else if(strcmp(input,"empty")==0)
		{
			printf("%d\n",empty(&d));
		}
		else if(strcmp(input,"front")==0)
		{
			printf("%d\n",front(&d));
		}
		else if(strcmp(input,"back")==0)
		{
			printf("%d\n",back(&d));
		}
	}
	return 0;
}