![#5 코테준비 - 덱(Deque)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FLq58D%2FbtrMN8q6XP3%2F1Kt5urDax37VlmP9Xej6e1%2Fimg.png)
덱(Deque)
- 양쪽끝에서 삽입/삭제가 가능한 자료구조
- 큐,스택,덱을 합쳐서 Restricted Structure라고 부름.
- Deque / Double Ended Queue라는 뜻을 가지고 있다.
- 원소의 추가/제거 O(1)
- 제일 앞/뒤의 원소 확인이 O(1)
C++ STL - Deque
Deque의 문서를 보면 앞쪽에 원소를 추가/제거 할 수 있다는 것만 빼면 Vector와 상당히 유사한것을 알 수 있다.
자료구조의 Deque은 앞/뒤가 아니면 확인이 불가능하지만 STL의 Deque는 인덱스로도 접근이 가능하다.
C++ stl vector vs deque 를 검색하면 많은 글들이 나오니 차이점들은 나중에 파보기로 하고,
코테에서 Vector와 deque중에 어떤걸 쓸지 판단하는 기준은 '앞/뒤 전부 추가/제거가 필요할 때' Deque를 쓰면 된다고 한다.
stl의 Vector는 배열처럼 연속한 메모리 공간을 가지지만, deque는 연속된 메모리 공간을 가지지 않는다.
연속한 메모리 공간을 가지면 삽입/삭제할때 그만큼의 연속된 공간을 찾아서 할당해야 하기때문에 이점도 생각할 부분이다.
문제 풀어보기 - 10866번: 덱 (acmicpc.net)
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
이것도 스택/큐의 문제와 똑같이 명령어대로 실행시키면 되는 문제다.
stl의 deque를 사용했다.
#include<iostream>
#include<string>
#include<deque>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
deque<int> myDeque;
int n = 0;
cin >> n;
while (n--)
{
string s;
cin >> s;
if (s == "push_front")
{
int temp = 0;
cin >> temp;
myDeque.push_front(temp);
}
else if (s == "push_back")
{
int temp = 0;
cin >> temp;
myDeque.push_back(temp);
}
else if (s == "pop_front")
{
if (myDeque.empty()) cout << -1 << '\n';
else
{
cout << myDeque.front() << '\n';
myDeque.pop_front();
}
}
else if (s == "pop_back")
{
if (myDeque.empty()) cout << -1 << '\n';
else
{
cout << myDeque.back() << '\n';
myDeque.pop_back();
}
}
else if (s == "size")
{
cout << myDeque.size() << '\n';
}
else if (s == "empty")
{
if (myDeque.empty()) cout << 1 << '\n';
else cout << 0 << '\n';
}
else if (s == "front")
{
if (myDeque.empty()) cout << -1 << '\n';
else cout << myDeque.front() << '\n';
}
else
{
if (myDeque.empty()) cout << -1 << '\n';
else cout << myDeque.back() << '\n';
}
}
return 0;
}
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
#6 코테준비 - BFS(Breadth First Search) (0) | 2022.09.23 |
---|---|
스택을 활용한 수식의 괄호 쌍 (0) | 2022.09.23 |
#4 코테준비 - 큐(Queue) (0) | 2022.09.23 |
#3 코테준비 - 스택(Stack) (0) | 2022.09.22 |
#2 코테준비 - 연결리스트 (0) | 2022.09.22 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!