Deque(C++)

Deque

Deque는 데이터를 담는 자료구조로, Stack, Queue와 다르게 데이터를 양방향으로 저장하는 자료구조이다. Deque는 데이터를 가장 앞(front)에 저장할 수 있고, 데이터를 가장 뒤(back)에 저장할 수 있다. Stack과 Queue를 합쳐 놓았다고 생각하면 쉽다.

Queue는 다음과 같은 연산을 가진다.

1. pushFront() - 맨 앞(Front)에 데이터를 넣는다.

2. pushBack() - 맨 뒤(back)에 데이터를 넣는다.
3. popFront() - 맨 앞(Front)에서 데이터를 pop 한다.
4. popBack() - 맨 뒤(Back)에서 데이터를 pop 한다.
5. peekFront() - 맨 앞(Front)의 데이터를 확인한다.
6. peekBack() - 맨 뒤(Back)의 데이터를 확인한다.
7. getSize() - 현재 크기를 반환한다.
8. isEmpty() - Deque가 비었는지 여부를 반환한다.

상황에 따라 추가적인 연산을 구현할 수 있고, 연산의 이름은 달라질 수 있다.

그림을 통해 Deque를 이해해 보자.

비어 있는 Deque이다.

pushFront 연산

pushFront를 하면 데이터가 Deque의 맨 앞(Front)에 들어간다. Front에서 Back으로 Node가 연결되는 이유는 지난 Queue 포스팅에서 다루었다,

https://dev-allday.tistory.com/70

pushBack 연산

pushBack을 하면 데이터가 Deque의 맨 뒤(Back)에 들어간다.

popFront 연산

popFront를 하면 맨 앞(Front)에 있는 데이터가 pop 된다.

popBack()

popBack을 하면 맨 뒤(Back)에 있는 데이터가 pop 된다.

구현

Deque를 LinkedList를 사용해 구현해 보자.

우선, LinkedList를 구현하는 Node 클래스를 작성한다.

class Node {
	public:
		int data;
		Node* next;
		Node* prev;
		Node(int data);
};

Node::Node(int data) {
	this->data = data;
	this->next = NULL;
	this->prev = NULL;
}

그다음, Deque를 선언한다.

class Deque{
	private:
		Node* front;
		Node* back;
		int size;
	public:
		Deque();
		void pushFront(int data);
		void pushBack(int data);
		int popFront();
		int popBack();
		int peekFront();
		int peekBack();
		int getSize();
		bool isEmpty();
		void print();
};

생성자

Deque::Deque() {
	this->front = NULL;
	this->back = NULL;
	this->size = 0;
}

front와 back을 NULL로 초기화한다.

pushFront

void Deque::pushFront(int data) {
	Node* newNode = new Node(data);
	if (this->front == NULL) {
		this->front = newNode;
		this->back = newNode;
	}
	else {
		newNode->next = this->front;
		this->front->prev = newNode;
		this->front = newNode;
	}
	this->size++;
}

front가 NULL 이면(Deque가 비어 있으면) front, back을 새로운 newNode로 만들어 준다.

else 문이 핵심인데

front가 NULL이 아니라면(Deque가 비어 있지 않다면) newNode의 next를 front로 만들어준 후

front의 prev를 newNode로 만들어준다. 이렇게 하면 front와 newNode가 연결된다.

마지막으로 front를 newNode로 만들어주면 끝이다.

pushBack

void Deque::pushBack(int data) {
	Node* newNode = new Node(data);
	if (this->front == NULL) {
		this->front = newNode;
		this->back = newNode;
	}
	else {
		newNode->prev = this->back;
		this->back->next = newNode;
		this->back = newNode;
	}
	this->size++;
}

front가 NULL 이면(Deque가 비어 있으면) front, back을 새로운 newNode로 만들어 준다.

else 문이 핵심인데

front가 NULL이 아니라면(Deque가 비어 있지 않다면) newNode의 prev를 back으로 만들어준 후

back의 next를 newNode로 만들어준다. 이렇게 하면 back과 newNode가 연결된다.

마지막으로 back을 newNode로 만들어주면 끝이다.

popFront

int Deque::popFront() {
	if (this->front == NULL) {
		return -1;
	}
	else {
		Node* temp = this->front;
		int data = temp->data;
		this->front = this->front->next;
		if (this->front != NULL) {
			this->front->prev = NULL;
		}
		else {
			this->back = NULL;
		}
		delete temp;
		this->size--;
		return data;
	}
}

front를 temp에 담은 후, return 할 데이터를 따로 저장한다.

그 후, front를 front의 next로 만들어준다.