일정
2024.01.16
목표
백준 10866 덱구현 c++fh wkrtjd
https://www.acmicpc.net/problem/10866
STL을 사용하는 것보다 덱을 직접 구현하는 게 문제에서 원하는 것 같아서 직접 구현해 봤습니다.
직접 구현하면서 pop_front(), pop_back() 부분에서 NULL포인터에 접근하지 않게 주의하며 구현했습니다.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Node{
public:
int data;
Node *next;
Node *prev;
Node(int input){
data = input;
next = NULL;
prev = NULL;
}
};
class Deque{
public:
int size;
Node *head;
Node *tail;
Deque(){
size = 0;
head = NULL;
tail = NULL;
}
void push_front(int input){
Node *node = new Node(input);
if(head==NULL){
tail = node;
}else{
head -> prev = node;
node -> next = head;
}
head = node;
size++;
}
void push_back(int input){
Node *node = new Node(input);
if(head==NULL){
head = node;
}else{
node->prev = tail;
tail->next = node;
}
tail = node;
size++;
}
int pop_front(){
if(head==NULL) return -1;
int value = head->data;
Node *node = head->next;
delete head;
head = node;
if(head==NULL){
tail=NULL;
}else head->prev = NULL;
size--;
return value;
}
int pop_back(){
if(tail==NULL) return -1;
int value = tail -> data;
Node *node = tail->prev;
delete tail;
tail = node;
if(tail==NULL){
head=NULL;
}else tail->next=NULL;
size--;
return value;
}
int empty(){
if(head==NULL) return 1;
else return 0;
}
int front(){
if(head==NULL) return -1;
return head->data;
}
int back(){
if(head==NULL) return -1;
return tail->data;
}
};
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
string s;
Deque dq;
cin >> n;
for(int i=0;i<n;i++){
cin >> s;
if(s=="push_front"){
int element;
cin >> element;
dq.push_front(element);
}else if(s=="push_back"){
int element;
cin >> element;
dq.push_back(element);
}else if(s=="pop_front"){
cout << dq.pop_front() << "\n";
}else if(s=="pop_back"){
cout << dq.pop_back() << "\n";
}else if(s=="size"){
cout << dq.size << "\n";
}else if(s=="empty"){
cout << dq.empty() << "\n";
}else if(s=="front"){
cout << dq.front() << "\n";
}else if(s=="back"){
cout << dq.back() << "\n";
}
}
}