![[자료구조] 덱 (Deque)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FptOhu%2FbtqRTSqAZRB%2FOrlMCriLQ3RTFVNB7hhRLk%2Fimg.png)
728x90
반응형
덱 (Deque)
덱?
덱(Deque)이란 Double-Ended Queue의 줄임말이다.
즉, 앞쪽 front와 뒤쪽 rear에서 모두 삽입과 삭제가 가능한 큐를 의미한다.
덱 ADT
객체
- 전단과 후단 양쪽에서의 삽입과 삭제를 허용하는 동일한 자료형의 요소들의 모음
연산
- addFront(x) : 요소 x를 덱의 맨 앞에 추가
- addRear(x) : 요소 x를 덱의 맨 뒤에 추가
- deleteFront() : 큐의 맨 앞의 요소를 삭제하고 반환
- deleteRear() : 큐의 맨 뒤의 요소를 삭제하고 반환
- getFront() : 큐의 맨 앞의 요소를 삭제하지 않고 반환
- getRear() : 큐의 맨 뒤의 요소를 삭제하지 않고 반환
- isEmpty() : 큐가 비어있으면 true 아니면 false 반환
- isFull() : 큐가 가득 차 있으면 true 아니면 false 반환
- size() : 큐 내의 모든 요소 개수를 반환
- display() : 큐 내의 모든 요소 출력
Array로 Circular Deque 구현 (C++)
/*
* array를 이용하여 Circular Deque 구현
*/
#include <iostream>
using namespace std;
#define MAX_DEQUE_SIZE 10
class Deque {
private:
int front; // 첫번째 요소 앞의 index
int rear; // 마지막 요소 index
int data[MAX_DEQUE_SIZE];
public:
Deque(){
front = 0;
rear = 0;
}
~Deque(){}
void addFront(int n){
if(isFull()){
cout << "Deque Full Error" << endl;
exit(1);
}
data[front] = n;
front = (front-1+MAX_DEQUE_SIZE)%MAX_DEQUE_SIZE; // front가 0 이하로 떨어지는 경우 max index로 순회
}
void addRear(int n){ // push
if(isFull()){
cout << "Deque Full Error" << endl;
exit(1);
}
rear = (rear+1)%MAX_DEQUE_SIZE; // rear가 max를 넘어가는 경우 다시 0번째 index로 순회
data[rear] = n;
}
int deleteFront(){ // pop
if(isEmpty()){
cout << "Deque Empty Error" << endl;
exit(1);
}
front = (front+1)%MAX_DEQUE_SIZE; // front가 max를 넘어가는 경우 다시 0번째 index로 순회
return data[front];
}
int deleteRear(){
if(isEmpty()){
cout << "Deque Empty Error" << endl;
exit(1);
}
int tmp = data[rear];
rear = (rear-1+MAX_DEQUE_SIZE)%MAX_DEQUE_SIZE; // rear가 0 이하로 떨어지는 경우 max index로 순회
return tmp;
}
int getFront(){
if(isEmpty()){
cout << "Deque Empty Error" << endl;
exit(1);
}
return data[(front+1)%MAX_DEQUE_SIZE];
}
int getRear(){
if(isEmpty()){
cout << "Deque Empty Error" << endl;
exit(1);
}
return data[rear];
}
int size(){
return front<=rear ? rear-front : (rear+MAX_DEQUE_SIZE)-front;
}
void display(){
for(int i=front+1; i<=front+size(); i++){
cout << "[" << data[i%MAX_DEQUE_SIZE] << "]";
}
cout << endl;
}
// circular array의 front와 rear 정보를 보기위한 메소드
void displayDetail(){
cout << "DEQUE :";
for(int i=front+1; i<=front+size(); i++){
cout << "[" << data[i%MAX_DEQUE_SIZE] << "]";
}
cout << endl;
cout << "index :";
for(int i=front+1; i<=front+size(); i++){
cout << " " << i%MAX_DEQUE_SIZE << " ";
}
cout << endl;
cout << "front : " << front << ", rear : " << rear << endl;
cout << endl;
}
bool isEmpty(){
return front == rear;
}
bool isFull() {
return front == (rear+1)%MAX_DEQUE_SIZE;
}
};
int main() {
Deque deque;
cout << "===== addRear x3 =====" << endl;
deque.addRear(1);
deque.addRear(2);
deque.addRear(3);
cout << " size : " << deque.size() << endl;
deque.displayDetail();
cout << "===== addFront x2 ======" << endl;
deque.addFront(5);
deque.addFront(6);
cout << " size : " << deque.size() << endl;
deque.displayDetail();
cout << "===== deleteRear x1 ======" << endl;
deque.deleteRear();
cout << " size : " << deque.size() << endl;
deque.displayDetail();
cout << "===== deleteFront x3 ======" << endl;
deque.deleteFront();
deque.deleteFront();
deque.deleteFront();
cout << " size : " << deque.size() << endl;
deque.displayDetail();
}
LinkedList로 Circular Deque 구현 (C++)
/*
* 이중 Linked List를 이용하여 Deque 구현
*/
#include <iostream>
using namespace std;
// Doubly Linked List
struct Node {
int data;
Node* prev; // 이전 Node를 가리키는 pointer
Node* next; // 다음 Node를 가리키는 pointer
public:
Node(){
prev = nullptr;
next = nullptr;
data = 0;
}
Node(int n, Node* prevNode = nullptr, Node* nextNode = nullptr){
data = n;
prev = prevNode;
next = nextNode;
}
~Node(){}
void setPrev(Node* prevNode){
prev = prevNode;
}
void setNext(Node* nextNode){
next = nextNode;
}
};
// Deque Class
class Deque {
private:
Node* front; // Deack의 front를 가리키는 Node pointer
Node* rear; // Deack의 rear를 가리키는 Node pointer
int dataSize; // Stack에 저장된 데이터 size
public:
Deque(){
front = nullptr;
rear = nullptr;
dataSize = 0;
}
~Deque(){
while(!isEmpty()){
deleteFront(); //deleteRear();
}
delete front;
delete rear;
}
//새로운 node를 생성 (prev : null, next : 기존의 front node)
//front를 새로운 node로 변경
//최초 생성이라면 rear = node 해줌
//이후 front가 추가될 때마다 기존 node의 prev에 새로 추가되는 node 대입
void addFront(int n){
Node* node = new Node(n, nullptr, front);
if(rear == nullptr){
rear = node;
}else{
front->setPrev(node);
}
front = node;
dataSize++;
}
//addFront()와 같은 맥락.
//새로운 node를 생성 (prev : 기존의 rear node, next : null)
//rear를 새로운 node로 변경
//최초 생성이라면 front = node 해줌
//이후 rear가 추가될 때마다 기존 node의 next에 새로 추가되는 node 대입
void addRear(int n){
Node* node = new Node(n, rear, nullptr);
if(front == nullptr){
front = node;
}else{
rear->setNext(node);
}
rear = node;
dataSize++;
}
//deque가 비어있는 경우 error occurred
//그렇지 않다면, 우선 front node의 데이터를 임시 변수 'data'에 담아놓음
//front를 next node로 변경한 다음, 삭제된 node(front였던)는 delete 처리 (메모리자원을위해)
//아까 담아놓은 'data'를 반환
//또한 현재 front노드의 prev를 null로 지정
int deleteFront(){
if(isEmpty()){
cout << "Deque Empty Error" << endl;
exit(EXIT_FAILURE);
}else{
int data = front->data;
Node* node = front;
front = front->next;
front->setPrev(nullptr);
delete node;
dataSize--;
return data;
}
}
//deleteFront()와 같은 맥락.
//deque가 비어있는 경우 error occurred
//그렇지 않다면, 우선 rear node의 데이터를 임시 변수 'data'에 담아놓음
//rear를 prev node로 변경한 다음, 삭제된 node(rear였던)는 delete 처리 (메모리자원을위해)
//아까 담아놓은 'data'를 반환
//또한 현재 rear노드의 next를 null로 지정
int deleteRear(){
if(isEmpty()){
cout << "Deque Empty Error" << endl;
exit(EXIT_FAILURE);
}else{
int data = rear->data;
Node* node = rear;
rear = rear->prev;
rear->setNext(nullptr);
delete node;
dataSize--;
return data;
}
}
// deque의 모든 data 출력
void display(){
if(isEmpty()){
cout << "Deque is Empty" << endl;
}else{
Node* node = front;
while(node){
cout << "[" << node->data << "]";
node = node->next;
}
cout << endl;
}
}
// deque size 반환
int size(){
return dataSize;
}
bool isEmpty(){
return dataSize == 0;
}
};
int main() {
Deque deque;
cout << "===== addRear x3 =====" << endl;
deque.addRear(1);
deque.addRear(2);
deque.addRear(3);
cout << " size : " << deque.size() << endl;
deque.display();
cout << "===== addFront x2 ======" << endl;
deque.addFront(5);
deque.addFront(6);
cout << " size : " << deque.size() << endl;
deque.display();
cout << "===== deleteRear x1 ======" << endl;
cout << deque.deleteRear() << endl;
cout << " size : " << deque.size() << endl;
deque.display();
cout << "===== deleteFront x3 ======" << endl;
cout << deque.deleteFront() << endl;
cout << deque.deleteFront() << endl;
cout << deque.deleteFront() << endl;
cout << " size : " << deque.size() << endl;
deque.display();
}
728x90
반응형