[자료구조] deque

 

double-ended queue

정의

양쪽 말단에서 데이터의 삽입과 삭제가 가능한 자료구조.

 

 

강점

- 양쪽 말단에서 데이터의 삽입 삭제를 상수시간안에 해낼수 있다.

    - 배열과 비교해보자면, 배열의 경우 최상단에 데이터를 추가할경우, 그 외의 모든 데이터를 shifting 해야 하는데, 이는 꽤 많은 시간을          요한다

    - 네트위크 통신 프로토콜 같은곳에서 용이하게 사용됨. 

 

약점

- doubly linked list로 구현한 경우, memory overhead의 위험성 존재.

    - 말단에 데이터를 추가할때마다, 새로운 포인터를 필요로 하는데, 이것이 문제를 야기할 가능성 있음.

- array로 구현한 경우, 삽입과 삭제시 모든 데이터를 shifting 해줘야 함

    - 이것은 많은 시간을 요함.

 

 

 

 

 

구현

보통 array 또는 linked list로 구현된다.

typedef struct s_node
{
	int				data;
    struct s_node	*next;
    struct s_node	*prev;
}				t_node;

typedef struct s_deque
{
	t_node	*front;
    t_node	*rear;
}				t_deque;

t_deque	*new_deque(void)
{
	t_deque *deque;
    
	deque = (deque *)malloc(sizeof(deque) * 1);
    deque->front = NULL;
    deque->rear = NULL;
    return (deque);
}

t_deque *new_node(int data)
{
	t_node *node;
    
  	node = (node *)malloc(sizeof(node) * 1);
    node->data = data
    node->next = NULL;
    node->prev = NULL;
    return (node);
}

/*
deque의 최상단에 node 1개 내보냄
*/
t_node	*pop_front(t_deque *deque)
{
	t_node *node;
    
	if (deque->front == NULL)
    	return (NULL);
    node = deque->front;
    deque->front = deque->front->next;
    if (deque->front == NULL)	//deque에 원소가 1개뿐이었던 경우,
    	deque->rear = NULL;
    else
	    deque->front->prev = NULL;
    node->next = NULL;
    return (node);
}

/*
deque의 최상단에 node 한개 추가
*/
void *push_front(t_deque *deque, t_node *node)
{
	if (deque->front == NULL)
    {
    	deque->front = node;
        deque->rear = node;
    }
    else
    {
    	node->next = deque->front;
		deque->front->prev = node;
    	deque->front = node;
    }
}

// push_rear(), pop_rear() 생략