[자료구조 복습5] 이중연결리스트로 덱(double- ended queue) 구현하기

이미지 출처: https://iq.opengenus.org/deque-in-cpp-stl/

덱 이란? 덱은 큐와 스택의 기능을 모두 갖춘 만능 리스트라고 생각하면 된다. 즉, 앞 ,뒤 모두에서 데이터가 삽입가능하고, 앞, 뒤 모두에서 데이터가 삭제가 가능한 자료구조이다. 

즉 add rear 와 delete front는 큐의 성질이고, add rear 와 delete rear는 스택의 성질이라고 보면 된다.

 

덱은 주로 이중연결리스트로 구현이 되는데, 그 이유는 front와 rear에서 모두 삽입 , 삭제하려면 양쪽으로 링크를 가진 이중연결리스트가 편리하기 때문이다. 

 

또한 덱은 앞,뒤에서 삭제삽입이 이루어지기 때문에, 큐처럼 head 포인터와 tail포인터를 모두 가지고 있어야한다.

 

덱은 앞서 봤던 큐와 스택을 짬뽕?! 해놓은 개념이라 까다롭지 않으므로 바로 소스코드를 살펴보도록 하겠다!

역시나 세 클래스 1) data type 정의 클래스 2) 이중연결리스트 클래스 3) 덱 클래스로 이루어져있다.

#include <iostream>
using namespace std;

/*이중연결리스트로 덱 구현*/
class NodeType { //데이터타입 
public:
	int data;
	NodeType* pre;
	NodeType* next;
};

class DoublyLinkedList { //이중연결리스트
private:
	NodeType* head;
	NodeType* tail;
public:
	DoublyLinkedList() {
		head = tail = NULL;
	}

	void insert_front(NodeType* new_node) {
		if (head == NULL) { //첫노드 
			head = tail = new_node;
			new_node->pre = NULL;
			new_node->next = tail;
		}
		else {
			new_node->next = head;
			head->pre = new_node;
			head = new_node;
		}
	}

	void insert_rear(NodeType* new_node) {
		if (tail == NULL) {
			head = tail = new_node;
			new_node->pre = head;
			new_node->next = NULL;
		}
		else {
			new_node->pre = tail;
			tail->next = new_node;
			tail = new_node;
		}
	}

	int remove_front() {
		if (head == NULL) { //list가 비었을때
			cout << "deuque is empty" << endl;
			return -1;
		}
		int num = head->data;
		if (head ->next ==NULL) { //삭제 후, 빈 리스트가 된다면?
			delete head;
			head = tail = NULL;
			return num;
		}
		head = head->next;
		delete head->pre; //이전 head삭제 
		head->pre = NULL; //에러 안나도록 null값으로 바꿔줌
		return num;
	}

	int remove_rear() {
		if (tail == NULL) { 
			cout << "deuque is empty" << endl;
			return -1;
		}
		int num = tail->data;
		if (tail->pre==NULL) { //삭제 후 빈 리스트가 된다면?
            delete tail;
			tail=head = NULL;
			return num;
		}
		tail = tail->pre;
		delete tail->next; //이전 tail삭제
		tail->next = NULL; //에러 안나도록 null값으로 바꿔줌
		return num;
	}

	int peek_front() {
		if (head == NULL) {
			cout << "deuque is empty" << endl;
			return -1;
		}
		return head->data;
	}

	int peek_rear() {
		if (tail == NULL) {
			cout << "deuque is empty" << endl;
			return-1;
		}
		return tail->data;
	}

	int get_length() {
		int count = 0;
		NodeType* tmp = head;
		while (tmp != NULL) {
			count++;
			tmp = tmp->next;
		}
		return count;
	}

	void display() {
		NodeType* tmp = head;
		while (tmp != NULL) {
			cout << tmp->data << " ";
			tmp = tmp->next;
		}
		cout << endl;
	}

	~DoublyLinkedList() {
		DestroyDoublyLinkedList();
	}

	void DestroyDoublyLinkedList() {
		NodeType* tmp = head;
		while (tmp != NULL) {
			tmp = tmp->next;
			delete head;
			head = tmp;
		}
		tail = head;
	}


};

class Deque { //덱
private:
	DoublyLinkedList list;
public:
	Deque() {};
	void add_front(int x) { //맨 앞에 추가
		NodeType* node = new NodeType();
		node->data = x;
		node->next = node->pre = NULL;
		list.insert_front(node);
	}
	void add_rear(int x) { //맨 뒤에 추가
		NodeType* node = new NodeType();
		node->data = x;
		node->next = node->pre = NULL;
		list.insert_rear(node);
	}
	int delete_front() { return list.remove_front(); } //맨 앞의 요소 삭제
	int delete_rear() { return list.remove_rear(); } //맨 뒤의 요소 삭제
	int peek_front() { return list.peek_front(); } //맨 앞의 요소 
	int peek_rear() { return list.peek_rear(); } //맨 뒤의 요소
	int get_length() { return list.get_length(); } //덱 길이
	void display() { list.display(); } //덱 출력
};

주의할점은, head나 tail을 삭제시, 먼저 head, tail을 삭제 한 후 리스트 자체가 empty가 되는지 살펴보아야 한다.

이는 head가 삭제되면 그 다음 head가 될 head->next나, tail이 삭제되면 그 다음 tail이 될 tail->pre가 null 인지 아닌지로 알 수 있으며, 만약 head->next == NULL 이거나 tail->next==NULL 일경우, head를 head->next로 바꾸고, tail을 tail->pre로 바꾼 후  이 전 head, 이전 tail을 삭제하는 그 다음 연산에서 (delete head->pre, delete tail->next) 오류가 발생하기 때문이다. (바뀐 head와 tail이 null이므로 pre와 next를 찾을 수 없음)