덱 (연결리스트로 구현)

덱의 기본 설명은 '덱 (구조체로 구현)'에서 설명을 했으므로 생략하겠다. 백준 10866번 문제를 베이스로 구현한 코드다. 코드 자체는 이중 연결리스트와 유사하다. 또한, 연결리스트로 구현했으므로 full() 함수는 없다.

덱 직접 입력 코드 구현

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

typedef struct Node {
	int data;
	struct Node *left;
	struct Node *right;
}Node;

typedef struct Deque {
	Node *front;
	Node *rear;
	int size;
}Deque;

void init_deque(Deque *deque)
{
	deque->front = NULL;
	deque->rear = NULL;
	deque->size = 0;
}

int empty(Deque *deque)
{
	return deque->size == 0 ;
}

int size(Deque *deque) 
{
	return deque->size;
}

int front(Deque *deque)
{
    if(empty(deque))
    	return -1;
    return deque->front->data;
}

int back(Deque *deque)
{
    int re = -1;
    if(empty(deque))
	    return re;

    re = deque->rear->data;
    return re;
}

void push_front(Deque *deque, int data)
{
	Node *now = (Node *)malloc(sizeof(Node));
	now->data = data;
	if(empty(deque)) 
	{
		deque->front = now;
		deque->rear = now;
		now->right = NULL;
		now->left = NULL;
	} 
	else 
	{
		deque->front->left = now;
		now->right = deque->front;
		now->left = NULL;
		deque->front = now;
	}
	deque->size++;
}

void push_back(Deque *deque, int data)
{
	Node *now = (Node *)malloc(sizeof(Node));
	now->data = data;
	if(empty(deque)) 
	{
		deque->front = now;
		deque->rear = now;
		now->right = NULL;
    	now->left = NULL;
	} 
	else 
	{
    	deque->rear->right = now;
    	now->left = deque->rear;
		now->right = NULL;
		deque->rear = now;
	}
	deque->size++;
}

int pop_front(Deque *deque)
{
    int re = -1;
    Node *now;
    if(empty(deque))
    	return re;
		
    now = deque->front;
    re = now->data;
    deque->front = now->right;
    free(now);
    deque->size--;
    return re;
}

int pop_back(Deque *deque)
{
    int re = -1;
    Node *now;
    if(empty(deque))
    	return re;
	
    now = deque->rear;
    re = now->data;
    deque->rear = now->left;
    free(now);
    deque->size--;
    return re;
}

int main(void) 
{
	Deque* deque=(Deque*)malloc(sizeof(Deque));
	init_deque(deque);
	char Get_Com[11];
	int N,num;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%s",Get_Com);
		if(strcmp(Get_Com,"push_front")==0)
		{
			scanf("%d",&num);
			push_front(deque,num);
		}
		else if(strcmp(Get_Com,"push_back")==0)
		{
			scanf("%d",&num);
			push_back(deque,num);
		}
		else if(strcmp(Get_Com,"front")==0)
			printf("%d\n",front(deque));
		else if(strcmp(Get_Com,"back")==0)
			printf("%d\n",back(deque));
		else if(strcmp(Get_Com,"empty")==0)
			printf("%d\n",empty(deque));
		else if(strcmp(Get_Com,"size")==0)
			printf("%d\n",size(deque));
		else if(strcmp(Get_Com,"pop_front")==0)
			printf("%d\n",pop_front(deque));
		else if(strcmp(Get_Com,"pop_back")==0)
			printf("%d\n",pop_back(deque));
	}
	return 0;
}

 

추가 설명

push_front() 함수와 push_back() 함수를 좀 더 짧게 줄일 수 있다. 위 코드와 동일한 코드이지만 위의 코드는 가독성을 좀 더 높인 코드고, 밑의 코드들은 코드 길이를 줄이기 위한 코드다.

void push_front(Deque *deque, int data)
{
	Node *now = (Node *)malloc(sizeof(Node));
	now->data = data;
	now->left = NULL;
	if(empty(deque)) 
	{
		deque->rear = now;
		now->right = NULL;
	} 
	else 
	{
		deque->front->left = now;
		now->right = deque->front;
	}
	deque->front = now;
	deque->size++;
}

void push_back(Deque *deque, int data)
{
	Node *now = (Node *)malloc(sizeof(Node));
	now->data = data;
	now->right = NULL;
	if(empty(deque)) 
	{
		deque->front = now;
		now->left = NULL;
	} 
	else 
	{
		deque->rear->right = now;
		now->left = deque->rear;
	}
	deque->rear = now;
	deque->size++;
}