알고리즘 : 자료구조(3) 덱 (Deque) (C++로 구현)

스택 : 한쪽에서만 자료를 빼고 넣을 수 있다.

큐 : Front 에는 삭제가, Back 에서는 삽입이 일어난다.

 

덱 (Deque)

덱(deque)은 양쪽에서 삽입과 삭제가 가능하며 스택(stack)과 큐(queue)의 연산을 모두 지원한다. Double-Ended Queue라는 뜻으로 front, rear에서 모두 삽입 삭제가 가능한 큐를 생각하면 된다.

enqueue : 덱에서 요소를 추가
dequeue : 덱에서 요소를 삭제
front : 덱의 맨 앞
rear : 덱의 맨 뒤

큐와 같은 용어를 쓴다. 하지만 enqueue와 dequeue가 앞과 뒤 모두에서 일어난다는 것을 잊지밀자!

 

class Deque {
private:
	int front; // front에 가까운 원소의 바로 앞
	int rear; // back에 있는 원소의 element
	int data[10];

public:
	Deque();
	void addFront(int n);
	void addRear(int n); // push
	void deleteFront(); // pop
	void deleteRear()
	void showElement();
	bool isEmpty();
	bool isFull();
};

Deque::Deque() {
	front = 0;
	rear = 0;
}

덱을 구현해보도록 하겠다. 그 전에 큐에서는 선형 큐를 구현했는데, 이번엔 원형덱을 구현하도록 하겠다. 만약 원형 큐를 만들고 싶다면, 주석에 push, pop으로 표시한 것만 사용하면 된다!

 

1. addFront & addRear

void Deque::addFront(int n) {
	if (isFull()) {
		cout << "Error! Deque is Full\n";
	}
	else {
		data[front] = n;
		front = (front - 1 + 10) % 10; // front가 0 이하로 떨어지면 max index인 9가 된다
		// 그런게 아니라면 앞으로 간다
	}
}

void Deque::addRear(int n) {
	if (isFull()) {
		cout << "Error! Deque is Full\n";
	}
	else {
		rear = (rear + 1) % 10; // rear가 max를 넘어가는 경우 0번째가 된다
		data[rear] = n;
	}
}

 

2. deleteFront & deleteRear

void Deque::deleteFront() {
	if (isEmpty()) {
		cout << "Error! Deque is Empty\n";
	}
	else {
		front = (front + 1) % 10;
		cout << "Delete : " << data[front] << "\n";
	}
}

void Deque::deleteRear() {
	if (isEmpty()) {
		cout << "Error! Deque is Empty\n";
	}
	else {
		int temp = data[rear];
		rear = (rear -1 + 10) % 10;
		cout << "Delete : " << data[rear] << "\n";
	}
}

 

3. showElement

void Deque::showElement() {
	int size = rear - front;
	if (front > rear) {
		size = rear + 10 - front;
	}
	for (int i = front + 1; i <= front + size; i++) {
		cout << "[" << data[i % 10] << "]";
	}
	cout << endl;
}

 

4. isEmpty & isFull

bool Deque::isEmpty() {
	return front == rear;
}
bool Deque::isFull() {
	return front == (rear + 1) % 10;
}

 

5. 최종코드

int main() {
	Deque dq;
	int ch = 0, val;
	cout << "1) Insert element into the Front of the queue" << endl;
	cout << "2) Insert element into the Back of the queue" << endl;
	cout << "3) Delete element from the Front of the queue" << endl;
	cout << "4) Delete element from the Back of the queue" << endl;
	cout << "5) Display all the elements of queue" << endl;
	cout << "6) Exit\n";
	while (ch != 6) {
		cout << "Enter your choice : ";
		cin >> ch;
		switch (ch) {
		case 1: {
			cout << "Enter value to be pushed into the Front: ";
			cin >> val;
			dq.addFront(val);
			break;
		}
		case 2: {
			cout << "Enter value to be pushed into the Back: ";
			cin >> val;
			dq.addRear(val);
			break;
		}
		case 3: {
			dq.deleteFront();
			break;
		}
		case 4: {
			dq.deleteRear();
			break;
		}
		case 5: {
			dq.showElement();
			break;
		}
		case 6: cout << "Exit" << endl;
			break;
		default: cout << "Invalid choice" << endl;
		}
	}
	return 0;
}

최종 코드이다

 

6. STL을 이용한  Deque 구현

#include<deque>
deque<int> dq;
deque<int> d2(5); // 0으로 초기화된 size가 5인 deque
deque<int> d3(5,10); // 10으로 초기화된 size가 5인 deque

c++ STL을 이용해서 Deque을 구현할 수도 있다.

 

dq.push_back(element); // 맨 끝에 추가
dq.push_front(element) // 맨 앞에 추가
dq.pop_back() // 맨 뒤 삭제
dq.pop_front() // 맨 앞 삭제
dq.front(); // 맨 앞에 값 반환
dq.back(); // 맨 뒤에 값 반환
swap(dq1, dq2); // 덱 1과 덱 2의 내용 바꾸기

이러한 함수를 사용할 수 있다.

 

이 자료구조는 그래프와 BFS에서 집중적으로 다루게 될 것이다.

 

 

 

https://velog.io/@nnnyeong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D-Stack-%ED%81%90-Queue-%EB%8D%B1-Deque

[자료구조] 스택 Stack, 큐 Queue, 덱 Deque

https://suyeon96.tistory.com/24

[자료구조] 덱 (Deque)

위 티스토리를 참고하였다.

 

활용

데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우