※ Queue
큐는 FIFO(First-In-First-Out) 입출력 형태, 즉 선입선출 방식을 가진 자료구조이다.
enqueue와 dequeue의 시간복잡도는 둘 다 O(1)의 시간을 갖는다.
단, 탐색의 시간복잡도는 특정 data를 찾을 때까지 돌아야 하므로 O(n)의 시간을 갖는다.
※ queue Container (STL) ★★★
queue 컨테이너는 deque 클래스의 인터페이스를 제한해 전형적인 큐 메모리 구조의 인터페이스를 제공하는 형태이다.
※ queue 선언방식
#include <queue>
queue<데이터타입> 이름;
[queue 관련 백준문제]
백준 10854번: https://www.acmicpc.net/problem/10854
10854번: Divisions
David is a young boy and he loves numbers. Recently he learned how to divide two numbers. David divides the whole day. He is happy if the result of the division is an integer, but he is not very amused if this is not the case. After quite a while he decide
www.acmicpc.net
백준 11866번: https://www.acmicpc.net/problem/11866
11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
백준 1158번: https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
백준 2164번: https://www.acmicpc.net/problem/2164
2164번: 카드2
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가
www.acmicpc.net
백준 12789번(stack+queue): https://www.acmicpc.net/problem/12789
12789번: 도키도키 간식드리미
인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두
www.acmicpc.net
※ deque Container (STL) ★★★★★
deque 컨테이너는 double-ended queue를 의미하며 양쪽에 끝이 있는 큐이다.
이 컨테이너는 양 끝에서 빠르게 요소를 삽입, 삭제할 수 있다는 점에서 매우 powerful하다!
또한, 중간에서 원소를 추가, 삭제하는 경우(insert, erase), vector보다 효율이 좀 더 좋다.
(vector는 앞에서 원소를 추가하는 것이 불가능 하기 때문에 모든 원소를 뒤쪽으로 밀어야 하기 때문)
※ deque 선언방식
#include <deque>
deque<데이터타입> 이름;
[deque 관련 백준문제]
백준 10866번: https://www.acmicpc.net/problem/10866
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
백준 1021번: https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
백준 2161번:
https://www.acmicpc.net/problem/2161
2161번: 카드1
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가
www.acmicpc.net
백준 2346번: https://www.acmicpc.net/problem/2346
2346번: 풍선 터뜨리기
1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선
www.acmicpc.net
백준 20301번: https://www.acmicpc.net/problem/20301
20301번: 반전 요세푸스
첫째 줄에 정수 $N$, $K$, $M$이 주어진다. ($1 \leq N \leq 5\ 000$, $1 \leq K, M \leq N$)
www.acmicpc.net
※ Queue 자료구조의 구현
위에서 STL 즉, 이미 구현되어 있는 자료구조를 사용한 것을 보았다. 우리는 그 자료구조가 어떻게 구현되어 있는지 뜯어볼 필요가 있다.
(pseudo code) 의사코드로 먼저 표현
※ Deque자료구조의 구현
위에서 STL 즉, 이미 구현되어 있는 자료구조를 사용한 것을 보았다. 우리는 그 자료구조가 어떻게 구현되어 있는지 뜯어볼 필요가 있다.
(pseudo code) 의사코드로 먼저 표현
§ 예제.
'C | C++ > Data Structure & STL' 카테고리의 다른 글
| this.code(5).DS_ List (4) | 2022.12.23 |
|---|---|
| this.code(4).DS_ Recursion (재귀)_최대공약수 (0) | 2022.10.30 |
| this.code(2).DS_ Stack & Stack Container(STL) (0) | 2022.10.29 |
| this.code(1).DS_ Array & Vector (STL) (★★★★★★) (0) | 2022.10.28 |
| this.code(0).DS_ Data Structure & Algorithms (0) | 2022.10.28 |