[백준] 10866 덱 c++ 구현

 

목차

 

 

https://www.acmicpc.net/problem/10866

10866번: 덱

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

덱의 이해

덱은 스택과 큐를 합쳐놓은 것으로 양방향 연결리스트를 구현해 보았다면 무리없이 구현 할 수 있다.

 

 

 

 

 

덱의 ADT

앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조라고 이해하면 된다.

아래 코드는 일반적인 헤더파일의 모습이다.

//Deque.h
#ifndef __DEQUE_H__
#define __DEQUE_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
	Data data;
    struct _node * next;
    struct _node * prev;
}Node;

typedef struct _dlDeque
{
	Node *head;
    Node *tail;
}DLDeque;

typedef DLDeque Deque;

void DequeInit(&Deque *pdeq);
int DQIsEmpty(Deque *pdeq);

void DQAddFirst(Deque *pdeq, Data data);  //덱의 머리에 데이터 추가
void DQAddLast(Deque *pdeq, Data data);   //덱의 꼬리에 데이터 추가

Data DQRemoveFirst(Deque *pdeq); 		  //덱의 머리에서 데이터 삭제한 후 값 반환
Data DQRemoveLast(Deque *pdeq);			  //덱의 꼬리에서 데이터 삭제한 후 값 반환

Data DQGetFirst(Deque *pdeq);			  //덱의 머리에서 데이터 참조
Data DQGetLast(Deque *pdeq);			  //덱의 꼬리에서 데이터 참조

#endif

 

 

덱의 구현

나는 추가적으로 count를 넣어 갯수를 반환해주는 함수를 만들어 주었다.

아래는 c++로 구현한 모습이다.

 

struct Node {
	struct Node* next;
	struct Node* prev;
	int data;
};

class Deque {
private:
	struct List {
		Node* head;
		Node* tail;
		int count;  //추가 구현
	};
	List* list;

public:
	Deque() {
		list = DequeInit();   //생성자로 초기화
	}

	List* DequeInit() {   
		List *newList = new List;
		newList->count = 0;
		newList->head = nullptr;
		newList->tail = nullptr;
		return newList;
	}
	
	bool DQIsEmpty() {
		if (this->list->count == 0) {
			return true;
		}
		else
			return false;
	}

	void DQAddFirst(int data) {
		Node* NewNode = new Node;
		NewNode->data = data;
		if (this->list->head == nullptr) {
			this->list->head = NewNode;
			this->list->tail = NewNode;
			this->list->head->next = nullptr;
			this->list->head->prev = nullptr;
		}
		else {
			NewNode->next = this->list->head;
			this->list->head->prev = NewNode;
			this->list->head = NewNode;
			NewNode->prev = nullptr;
		}
		(this->list->count++);

	}
	void DQAddLast(int data) {
		Node* NewNode = new Node;
		NewNode->data = data;
		if (this->list->tail == nullptr) {
			this->list->head = NewNode;
			this->list->tail = NewNode;
			this->list->head->next = nullptr;
			this->list->head->prev = nullptr;
		}
		else {
			this->list->tail->next = NewNode;
			NewNode->prev = this->list->tail;
			this->list->tail = NewNode;
		    NewNode->next = nullptr;
		}
		(this->list->count++);
	}
	int DQRemoveFirst() {
		if (this->DQIsEmpty()) {
			return 0;
		}
		Node* delNode = this->list->head;
		int delData = delNode->data;
		if (this->list->head == this->list->tail) {
			this->list->tail = nullptr;
			this->list->head = nullptr;
		}
		else {
			this->list->head = this->list->head->next;
		}
		delete delNode;
		(this->list->count--);
		return delData;
	}

	int DQRemoveLast() {
		if (this->DQIsEmpty()) {
			return 0;
		}
		Node* delNode = this->list->tail;
		int delData = delNode->data;
		if (this->list->head == this->list->tail) {
			this->list->tail = nullptr;
			this->list->head = nullptr;
		}
		else {
			this->list->tail = this->list->tail->prev;
			
		}
		delete delNode;
		(this->list->count--);
		return delData;
	}
	int DQGetFirst() {
		if (this->DQIsEmpty()) {
			return 0;
		}
		return this->list->head->data;
	}
	int DQGetLast() {
		if (this->DQIsEmpty()) {
			return 0;
		}
		return this->list->tail->data;
	}
	int DQGetCount() {   //추가적인 구현
		return this->list->count;
	}

};

 

 

 

 

코드 구현

덱을 잘 구현했다면 쉽게 풀 수 있다. 따로 설명은 생략하겠다.

int Answer(string a, int b, Deque* list) {  //명령에 따른 함수 구현
	if (a == "push_back") {
		list->DQAddLast(b);
		return -2;
	}
	else if (a == "push_front") {
		list->DQAddFirst(b);
		return -2;
	}
	else if (a == "front") {
		if (list->DQIsEmpty()) {
			return -1;
		}
		else {
			return list->DQGetFirst();
		}

	}
	else if (a == "back") {
		if (list->DQIsEmpty()) {
			return -1;
		}
		else {
			return list->DQGetLast();
		}
	}
	else if (a == "size") {
		return list->DQGetCount();
	}
	else if (a == "empty") {
		if (list->DQIsEmpty()) {
			return 1;
		}
		else {
			return 0;
		}
	}
	else if (a == "pop_back") {
		if (list->DQIsEmpty()) {
			return -1;
		}
		else {
			return list->DQRemoveLast();
		}
	}
	else if (a == "pop_front") {
		if (list->DQIsEmpty()) {
			return -1;
		}
		else {
			return list->DQRemoveFirst();
		}
	}
}

int main() {
	Deque list;
	int N, i;
	char* order = new char[100];
	int print[10000];
	string a;
	int b, k=0, t;
	cin >> N;
	cin.ignore();
	for (i = 0; i < N; i++) {
		cin.getline(order, 100);
		istringstream ss1(order);
		ss1 >> a >> b;
		t = (Answer(a, b, &list));
		if (t != -2) {
			print[k++] =t;
		}
		
	}
	for (i = 0; i < k; i++) {
		cout << print[i] <<endl;
	}
	return 0;
}