Double-Ended Queue
큐의 front와 rear에서 모두 삽입 삭제가 가능한 큐
연산
create : 덱을 생성한다
init : 덱을 초기화한다.
is_empty(dq) : 덱이 비어있는지 검사한다.
is_full(dq) : 덱이 가득찼는지 검사한다.
add_front(dq, e) : 덱의 앞에 요소를 추가한다.
add_rear(dq, e) : 덱의 뒤에 요소를 추가한다.
delete_front(dq) : 덱의 앞에 요소를 반환하고 삭제한다.
delete_rear(dq) : 덱의 뒤에 요소를 반환하고삭제한다.
get_front(dq) : 덱의 앞에 요소를 반환한다.
get_rear(dq) : 덱의 뒤에 요소를 반환한다.
이중연결리스트를 이용한 구현
#include <iostream>
typedef int element;
typedef struct DqeueNode{
element data;
DqeueNode *front, *rear;
}DqeueNode;
typedef struct{
DqeueNode *head, *tail;
}linkedDqeue;
void init(linkedDqeue *dq){
dq->head = dq->tail = nullptr;
}
DqeueNode *create_node(DqeueNode *front, DqeueNode *rear, element data){
DqeueNode *temp = (DqeueNode *)malloc(sizeof(DqeueNode));
if(temp == nullptr){
std::cerr << "Memory Allocation Error\n";
exit(-1);
}
temp->data = data;
temp->front = front;
temp->rear = rear;
return temp;
}
bool is_full(linkedDqeue *dq){
return false;
}
bool is_empty(linkedDqeue *dq){
return dq->head == nullptr;
}
void add_front(linkedDqeue *dq, element data){
DqeueNode * newNode = create_node(nullptr, dq->head, data);
if(is_empty(dq)){
dq->tail = newNode;
}else{
dq->head->front = newNode;
}
dq->head = newNode;
}
void add_rear(linkedDqeue *dq, element data){
DqeueNode * newNode = create_node(dq->tail, nullptr, data);
if(is_empty(dq)){
dq->head = newNode;
}else{
dq->tail->rear = newNode;
}
dq->tail = newNode;
}
element delete_front(linkedDqeue *dq){
if(is_empty(dq)){
std::cerr << "Dqeue is empty\n";
exit(-1);
}
DqeueNode * temp = dq->head;
element data = temp->data;
dq->head = dq->head->rear;
if(dq->head == nullptr)dq->tail = nullptr;
else dq->head->front = nullptr;
free(temp);
return data;
}
element delete_rear(linkedDqeue *dq){
if(is_empty(dq)){
std::cerr << "Dqeue is empty\n";
exit(-1);
}
DqeueNode * temp = dq->tail;
element data = temp->data;
dq->tail = dq->tail->front;
if(dq->tail == nullptr)dq->head = nullptr;
else dq->tail->rear = nullptr;
free(temp);
return data;
}
element get_front(linkedDqeue *dq){
return dq->head->data;
}
element get_rear(linkedDqeue *dq){
return dq->tail->data;
}
int main(){
linkedDqeue dq;
init(&dq);
add_front(&dq, 1);
add_rear(&dq, 3);
add_rear(&dq, 2);
std::cout << delete_front(&dq) << "\n"; // 1
std::cout << delete_rear(&dq) << "\n"; // 2
std::cout << get_front(&dq) << "\n"; // 3
std::cout << get_rear(&dq) << "\n"; // 3
std::cout << delete_front(&dq) << "\n"; // 3
std::cout << std::boolalpha << is_empty(&dq) << "\n"; // true
}
'공부 > 자료구조' 카테고리의 다른 글
[자료구조] 우선 순위 큐(Priority Queue) (0) | 2023.05.12 |
---|---|
[자료구조] 이진트리(Binary Tree) (0) | 2023.05.11 |
[자료구조] 큐(Queue) (0) | 2023.04.30 |
[자료구조] 스택(Stack) (0) | 2023.04.26 |