[C++] deque 클래스 정리
🦥 deque?
1) Double Ended Queue
queue는 데이터를 front에서만 삭제하고, end에서만 삽입한다. 하지만 double ended queue는 이름에서 알 수 있듯이, front와 back 양쪽에서 삽입과 삭제가 모두 가능한 구조이다.
2) Sequence container, but not stored contiguously
deque는 sequence container, 즉 임의의 원소에 접근 가능한 구조이다. deque는 vector와 달리 메모리가 연속적으로 할당되지는 않아서 (not stored contiguously), 원소를 추가할 때에 기존 원소들을 복사하여 새로운 메모리 공간을 만드는 작업을 할 필요가 없다. 그래서 원소의 삽입과 삭제에 있어 좀더 효율적이다.
✅ 이 포스트는 C++ STL에서의 deque에 대한 글입니다. deque 자료구조의 특징, 장/단점, 시간 복잡도에 대해서 더 알아보려면 ▶ [자료구조] 스택(Stack), 큐(Queue), 덱(Deque)
🦥 deque의 생성자와 초기화
deque 헤더 추가
#include <deque>
1) 비어있는 deque 생성
deque<int> dq1;
2) 0으로 초기화 된 4개의 원소를 가진 deque를 생성
deque<int> dq2(4);
3) 1, 2, 3을 원소로 하는 deque 생성
// 두 가지 방법 다 가능
deque<int> dq3 = { 1, 2, 3 };
deque<int> dq4{ 1, 2, 3 };
🦥 deque의 함수들
🌴 Iterator
Iterator를 활용하여 deque의 원소에 접근할 수 있다
dq.begin(): deque의 첫번째 원소를 가리키는 iteratordq.end(): deque의 마지막 원소 다음을 가리키는 iterator (마지막 원소 아님!!)
/* deque의 모든 원소 출력 */
for (auto i = dq.begin(); i != dq.end(); i++) {
cout << *i << endl;
}
🌴 Fuction
vector 컨테이너의 멤버 함수들
1) 초기화
dq.assign(5): 원소 5개 0으로 초기화dq.assign(5,10): 원소 5개 10으로 초기화
2) 원소 접근
dq.front(): 첫 번째 원소dq.back(): 마지막 원소dq.at(i): i번째 원소
3) 원소 삽입 / 삭제
dq.push_front(5): 첫 번째 원소 앞에 ‘5’ 삽입dq.push_back(5): 마지막 원소 뒤에 ‘5’ 삽입dq.pop_front(): 첫 번째 원소 삭제dq.pop_back(): 마지막 원소 삭제dq.insert(v.begin(), 3): deque 처음에 (iterator가 가리키는 위치에) ‘3’ 추가. ex) dq.insert(3, 4) - 3번 위치에 4 추가하고, 가리키는 iterator 반환
4) deque 크기 관련
dq.empty(): deque가 비어있는지 확인dq.size(): 실제 원소 수dq.resize(10): 메모리 공간 크기를 10으로 변경. 늘어난 공간은 0으로 초기화.
* deque는 capacity 함수 없음
5) 원소 삭제
dq.clear() : 전체 원소 삭제
dq.erase(v.begin()) : iterator가 가리키는 원소 삭제. size만 변함.
실습 코드
#include <iostream>
#include <deque>
using namespace std;
void showAll(deque <int> dq)
{
while (!dq.empty())
{
cout << dq.front() << ' ';
dq.pop_front();
}
}
int main()
{
deque<int> dq;
dq.push_back(10);
dq.push_back(20);
dq.push_front(30);
cout << "Show all queue elements : ";
showAll(dq);
cout << "\nq.size() : " << dq.size();
cout << "\nq.front() : " << dq.front();
cout << "\nq.back() : " << dq.back();
cout << "\nq.pop_front()\n";
dq.pop_front();
cout << "Show all queue elements : ";
showAll(dq);
cout << "\ndq.pop_back()\n";
dq.pop_back();
cout << "Show all queue elements : ";
showAll(dq);
dq.clear();
cout << "\nShow all queue elements : ";
showAll(dq);
return 0;
}
[실행 결과]
Show all queue elements : 30 10 20
q.size() : 3
q.front() : 30
q.back() : 20
q.pop_front()
Show all queue elements : 10 20
dq.pop_back()
Show all queue elements : 10
Show all queue elements :
Reference
Leave a comment