[PCCP] 자료구조 - 덱

1. 이론

- 덱(deque): 양쪽에서 삽입, 삭제가 일어나는 자료구조

- 

- 덱 ADT: 

 

(시간복잡도)

- 임의 접근:

- 삽입:

- 삭제:

 

(선택시 고려할 점)

- 

 

 

2. 프로그램 언어별 문법

- 덱 선언 및 초기화

- 덱 접근: 맨 앞(front), 맨 뒤(rear)

- 덱 제어: 삽입, 삭제

 

<C언어>

 

 

<C++>

#include <deque>

/* 덱 생성 및 초기화 */
std::deque<int> dq1;
std::deque<int> dq2(10);    // 0으로 초기화된 10개의 원소
std::deque<int> dq3(10, 4); // 4로 초기화된 10개의 원소
std::deque<int> dq4(dq3);   // dq3를 복사한 dq4 생성

/* 삽입 */
dq.push_front(값); // 맨 앞에 요소 삽입
dq.insert(인덱스, 값); // 해당 위치에 요소 삽입
dq.push_back(값); // 맨 뒤에 요소 삽입

/* 삭제 */
dq.pop_front(); // 맨 앞에 요소 삭제
dq.erase(시작반복자, 끝반복자);
dq.pop_back(); // 맨 뒤에 요소 삭제

/* 변경 */

/* 조회(탐색) */
dq.front();  // 맨앞 요소 확인
dq[인덱스];
dq.at(인덱스);  // 유효범위 검사
dq.back(); // 맨뒤 요소 확인

/* 전체 조회 */
for (auto it = dq.begin(); it != dq.end(); ++it)
    std::cout << *it << std::endl;

/* 기타 메서드 */
dq.size(); // 덱의 요소 개수
dq.empty(); // 비어있다면 true 반환
dq.clear(); // 요소 모두 제거

 

<C#>

 

 

<Java>

 

 

<Python>

from collections import deque

# 덱 생성 및 초기화
dq = deque()
dq = deque([1, 6, 3, 9, 4])

# 삽입(맨 뒤)
dq.append(-100)

# 삽입(맨 앞)
dq.appendleft(100)

# 삭제(맨 뒤)
dq.pop()

# 삭제(맨 앞)
dq.popleft()

# 값 확인
print(f"맨 앞: {dq[0]}")
print(f"맨 뒤: {dq[-1]}")

# 비어있는지 확인
print(f"비어있는지: {len(dq) == 0}")

# 회전(양수는 오른쪽, 음수는 왼쪽)
dq.rotate(num)

 

<JavaScript>

 

 

 

 

3. 추천 문제(Programmers)

-