안녕하세요. C++을 다루기 위한 기본 적인 자료 구조와 코딩 테스트 등에서 응용될 수 있는 알고리즘을 알아보는 시간을 가지겠습니다.
이번 게시물은 std::deque를 간단히 설명해 보려 합니다.
게시물 끝에 std::deque를 사용한 stack과 queue 구현 예시도 있으니까 참고 바랍니다!
1) 특징
std::deque는 C++ 표준 라이브러리 컨테이너(C++ STL container) 중 하나로, Double-Ended Queue의 약자입니다. deque는 동적으로 크기가 조절되는 Queue 와 비슷한 동작을 제공하면서, 양쪽 끝 모두에서 삽입 및 삭제가 가능한 특징을 가지고 있습니다.이와같은 std::deque에 대한 attributes와 관련 메서드 사용 예시를 알아보겠습니다.
2) 코딩 테스트 활용 예시
- Sliding Window: Sliding Window 알고리즘은 고정된 크기의 윈도우를 슬라이딩 하면서 연속된 부분 배열 또은 부분 시퀀스의 최적 솔루션을 찾는 유형입니다. std::deque는 양 끝 모두에서 데이터를 수정할 수 있기 때문에 유용하게 사용될 수 있습니다.
- Queue: 큐를 활용하는 문제에서 deque는 큐와 관련된 기본적인 메서드들이 이미 구현되어 있기 때문에 쉽게 활용할 수 있습니다.
3) 속성 (Attributes)
std::deque는 <deque> 헤더를 포함해서 사용할 수 있습니다.
우선 다음과 같은 std::deque의 주요 속성과 멤버 함수를 통해 해당 자료 구조를 활용하는 방법을 자세하게 알아보겠습니다.
- push_front()
: 요소를 deque의 맨 앞에 추가합니다. - push_back()
: 요소를 deque의 맨 뒤에 추가합니다. - pop_front()
: deque의 맨 앞의 요소를 제거합니다. - pop_back()
: deque의 맨 뒤의 요소를 제거합니다. - front()
: deque의 맨 앞의 요소에 대한 참조를 반환합니다. - back()
: deque의 맨 뒤의 요소에 대한 참조를 반환합니다. - size()
: deque에 저장된 요소의 개수를 반환합니다. - empty()
: deque가 비어 있는지 여부를 확인합니다.
4) 속성 사용 예시
다음은 std::deque의 속성 사용 예시입니다.
- push_front()
: 요소를 deque의 맨 앞에 추가합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque;
deque.push_front(1);
deque.push_front(2);
deque.push_front(3);
for (const auto& element : deque) {
std::cout << element << " ";
}
return 0;
}- push_back()
: 요소를 deque의 맨 뒤에 추가합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque;
deque.push_back(1);
deque.push_back(2);
deque.push_back(3);
for (const auto& element : deque) {
std::cout << element << " ";
}
return 0;
}- pop_front()
: deque의 맨 앞의 요소를 제거합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque {1, 2, 3};
deque.pop_front();
for (const auto& element : deque) {
std::cout << element << " ";
}
return 0;
}- pop_back()
: deque의 맨 뒤의 요소를 제거합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque {1, 2, 3};
deque.pop_back();
for (const auto& element : deque) {
std::cout << element << " ";
}
return 0;
}- front()
: deque의 맨 앞의 요소에 대한 참조를 반환합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque {1, 2, 3};
std::cout << deque.front();
return 0;
}- back()
: deque의 맨 뒤의 요소에 대한 참조를 반환합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque {1, 2, 3};
std::cout << deque.back();
return 0;
}- size()
: deque에 저장된 요소의 개수를 반환합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque {1, 2, 3};
std::cout << deque.size();
return 0;
}- empty()
: deque가 비어 있는지 여부를 확인합니다.
#include <deque>
#include <iostream>
int main() {
std::deque<int> deque;
if (deque.empty()) {
std::cout << "Deque is empty.";
} else {
std::cout << "Deque is not empty.";
}
return 0;
}
5) std::deque를 활용한 stack과 queue 구현 예시
1. Stack 구현 예시
#include <deque>
#include <iostream>
template<typename T>
class Stack {
private:
std::deque<T> deque;
public:
void push(const T& value) {
deque.push_back(value);
}
void pop() {
deque.pop_back();
}
T& top() {
return deque.back();
}
bool empty() const {
return deque.empty();
}
};
int main() {
Stack<int> stack;
stack.push(1);
stack.push(2);
stack.push(3);
while (!stack.empty()) {
std::cout << stack.top() << " ";
stack.pop();
}
return 0;
}
2. Queue 구현 예시
#include <deque>
#include <iostream>
template<typename T>
class Queue {
private:
std::deque<T> deque;
public:
void enqueue(const T& value) {
deque.push_back(value);
}
void dequeue() {
deque.pop_front();
}
T& front() {
return deque.front();
}
bool empty() const {
return deque.empty();
}
};
int main() {
Queue<int> queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
while (!queue.empty()) {
std::cout << queue.front() << " ";
queue.dequeue();
}
return 0;
}반응형