09-2 덱

1. 덱

• 전단(front)과 후단(rear)에서 모두 삽입, 삭제가 가능한 큐
• 양쪽 끝에서 높은 효율성으로 데이터 처리가 가능하다.
• getFront()는 큐의 peek() 연산과 같다.

2. 덱 구현 - (1) 배열

• 원형 큐 클래스를 확장하여 구현할 수 있다. -> 원형 덱
• 원형 큐 클래스를 상속하여 원형 덱 클래스를 생성한다.

원형 덱의 연산

원형 덱에서는 원형 큐의 연산에 추가로 반대방향의 회전이 필요하다. 따라서

• front = (front - 1 + MAX_SIZE) % MAX_SIZE
• rear = (rear - 1 + MAX_SIZE) % MAX_SIZE
  front - 1: front의 인덱스를 앞쪽으로 이동시킨다.
  rear - 1: rear의 인덱스를 앞쪽으로 이동시킨다.

• MAX_SIZE: 인덱스가 음수가 되는 것을 방지한다.
  % MAX_SIZE: 인덱스가 배열의 범위를 벗어나지 않도록 나머지 연산을 수행한다.

#include<iostream>
using namespace std;
inline void error(char* str){
	cerr << str << endl;
	exit(1);
};

#define MAX_QUEUE_SIZE 100
class CircularQueue{
protected:
	int front;
	int rear;
	int data[MAX_QUEUE_SIZE];
public:
	CircularQueue(){
		front = rear = 0;
	}
	~CircularQueue(){	}
	bool isEmpty(){return front == rear;}
	bool isFull(){return (rear+1) % MAX_QUEUE_SIZE == front;}
	void enqueue(int val){
		if(isFull()) error("포화상태\n");
		else{
			rear = (rear + 1) % MAX_QUEUE_SIZE;
			data[rear] = val;
		}
	}

	int dequeue(){
		if(isEmpty()) error("공백상태\n");
		else{
			front = (front +1) % MAX_QUEUE_SIZE;
			return data[front];
		}
	}

	int peek(){
		if(isEmpty()) error("공백상태\n");
		else return data[(front+1) % MAX_QUEUE_SIZE];
	}

	void display(){
		cout << "큐 내용 : ";
		int maxi = (front<rear) ? rear : rear + MAX_QUEUE_SIZE;
		for(int i=front+1; i<=maxi; i++){
			cout<<"["<<data[i%MAX_QUEUE_SIZE] << "] ";
		}
		cout << endl;
	}	
};

class CircularDeque : public CircularQueue{
public:
    CircularDeque(){}
    void addRear(int val){enqueue(val);}
    int deleteFront(){return dequeue();}
    int getFront(){return peek();}
    void addFront(int val){
        if(isFull())
            error("덱 포화상태\n");
        else{
            data[front] = val;
            front = (front-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
        }
    }
    int deleteRear(){
        if(isEmpty())
            error("덱 공백상태\n");
        else{
            int ret = data[rear];
            rear = (rear-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;
            return ret;
        }
    }
    int getRear(){
        if(isEmpty())
            error("덱 공백상태\n");
        else return data[rear];
    }
    void display(){
        cout << "덱의 내용: ";
        int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
        for(int i=front+1; i<=maxi; i++)
            cout << "[" << data[i%MAX_QUEUE_SIZE] << "] ";
        cout << endl;
    }
};

int main(void){
	CircularDeque deq;
	for(int i=1; i<10; i++){
        if(i%2) deq.addFront(i);
        else deq.addRear(i);
	}
	deq.display();
    deq.deleteFront();
    deq.deleteRear();
    deq.deleteFront();
	deq.display();
	return 0;
}

3. 덱 구현 - (2) 이중 연결 리스트

• 이중 연결 리스트: 하나의 노드가 이전 노드와 다음 노드를 가리키는 두 개의 링크를 가지는 리스트
• 이중 연결 리스트 클래스를 상속하여 이중연결리스트 덱 클래스 생성
• Node2 클래스: 데이터를 저장하는 data 변수, 이전 노드와 다음 노드를 가리키는 포인터인 prev, next로 구성

#include<iostream>
using namespace std;

inline void error(char *str){
    cout << stderr << str << endl;
    exit(1);
};

class Node2{
    Node2* prev;
    Node2* next;
    int data;
public:
    Node2(int val = 0): data(val), prev(NULL), next(NULL) {}
    //getPrev 함수
    //getNext 함수
    Node2* getNext(){return next;}
    //setPrev 함수
    //setNext 함수
    //display 함수
    void display(){cout << "<" << data << "> ";}
    //hasData 함수

    //insertNext 함수
    void insertNext(Node2* n){
        if(n!=NULL){
            n->prev = this;
            n->next = next;
            if(next != NULL) next -> prev = n;
            next = n;
        }
    }
    //remove 함수
    Node2* remove(){
        if(prev != NULL) prev -> next = next;
        if(next != NULL) next -> prev = prev;
        return this;
    }
};

class DbLinkedList{
    Node2 org;
public:
    DbLinkedList():org(0){}
    ~DbLinkedList(){clear();}

    //clear 함수
    void clear(){while(!isEmpty()) delete remove(0);}
    //getHead 함수
    Node2* getHead(){return org.getNext();}
    //isEmpty 함수
    bool isEmpty(){return getHead() == NULL;}
    //getEntry 함수
    Node2* getEntry(int pos){
        Node2* n = &org;
        for(int i=-1; i<pos; i++, n= n->getNext()){
            if(n==NULL) break;
        }
        return n;
    }
    //insert 함수
    void insert(int pos, Node2* n){
        Node2* prev = getEntry(pos-1);
        if(prev != nullptr){
            prev -> insertNext(n);
        }
    }
    //remove 함수
    Node2* remove(int pos){
        Node2* cur = getEntry(pos);
        return cur -> remove();
    }
    //find 함수
    //replace 함수
    void replace(int pos, Node2* n){
        Node2* prev = getEntry(pos-1);
        if(prev != NULL){
            delete prev -> getNext() -> remove();
            prev -> insertNext(n);
        }
    }
    //size 함수
    int size(){
        int cnt = 0;
        for(Node2* p = getHead(); p!=NULL; p=p->getNext()) cnt++;
        return cnt;
    }
    //display 함수
    void display(){
        cout << "[이중연결리스트 항목 수 = " << size() << "] : ";
        for(Node2* p = getHead(); p!=NULL; p=p->getNext()){
            p->display();
        }
        cout<<endl;
    }
};

class LinkedDeque : public DbLinkedList{
public:
    void addFront(Node2* n) {insert(0, n);}
    Node2* deleteFront() {return remove(0);}
    Node2* getFront() {return getEntry(0);}
    void addRear(Node2* n) {insert(size(), n);}
    Node2* deleteRear() {return remove(size()-1);}
    Node2* getRear() {return getEntry(size()-1);}
};

int main(){
    LinkedDeque deq;
    for(int i=1; i<10; i++){
        if(i % 2)
            deq.addFront(new Node2(i));
        else deq.addRear(new Node2(i));
    }
    deq.display();
    delete deq.deleteFront();
    delete deq.deleteRear();
    delete deq.deleteFront();
    deq.display();
    return 0;
}