[PCCP] 자료구조 - 큐

1. 이론

- 큐(queue): 먼저 들어간 데이터가 먼저 나오는 자료구조(FIFO: First In First Out)

- 삽입 연산을 enqueue, 꺼내는 연산을 dequeue

- 큐 ADT: push(삽입), pop(꺼내기), isFull(), isEmpty(), front(오래된 삽입 데이터), rear(최근 삽입 데이터), data(데이터 저장공간)

- 큐 활용 분야: 작업 대기열, 로드밸런서, 이벤트 처리

 

(시간복잡도)

- 임의 접근: 

- 삽입: 

- 삭제: 

 

(선택시 고려할 점)

- 

 

 

2. 프로그램 언어별 문법

- 큐 선언 및 초기화

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

- 큐 제어: 삽입(push), 삭제(pop)

 

<C언어>

 

 

<C++>

#include <queue>

/* 큐 생성 및 초기화 */
std::queue<자료형> q;

/* 삽입 */
q.push(값); // 맨 뒤에 삽입. O(1)

/* 삭제 */
q.pop(); // 맨 앞에서 꺼냄. O(1)

/* 변경 */

/* 조회 */
q.front(); // 맨 앞 요소 확인. O(1)
q.back(); // 맨 뒤 요소 확인

/* 전체 조회 */
while (!q.empty()) {
    std::cout << q.front() << std::endl;
    q.pop();
}

/* 기타 메서드 */
q.size();  // 
q.empty(); // 비어 있다면 true 반환. O(1)

 

<C#>

 

 

<Java>

 

 

<Python>

from collections import deque

# 큐 생섬 및 초기화
q = deque()

# 삽입
q.append(10)
q.append(3)
q.append(1)

# 삭제
q.popleft()

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

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

 

<JavaScript>

 

 

 

 

3. 추천 문제

(프로그래머스)

- Lv 2: 기능개발(42586) / 기능개발(42586) 해설
- Lv 1: 카드 뭉치(159994) / 카드 뭉치(159994) 해설

- Lv 2: 다리를 지나는 트럭(42583) / 다리를 지나는 트럭(42583) 해설

 

(leetcode)

-