위 글은 큰돌의 터전 님의 강의자료를 참조해서 정리하고 제가 알고리즘을 풀면서 더 추가적으로 사용할 만한 내용들을 정리한 글입니다.
알고리즘 풀이 강의로 큰돌의 터전님의 강의 강력 추천드립니다.
강의링크
queue란 무엇인가
큐(queue)는 먼저 집어넣은 데이터가 먼저 나오는 성질인 선입선출(FIFO, First In First Out)을 지닌 자료 구조이며, 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가졌습니다.
삽입 및 삭제에 O(1), 탐색에 O(n)이 걸립니다.
예시코드
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main()
{
for(int i = 1; i <= 10; i++)q.push(i);
while(q.size())
{
cout << q.front() << ' ';
q.pop();
}
return 0;
}
/* 1 2 3 4 5 6 7 8 9 10 */메소드
push(value) : value를 큐에 추가합니다.
pop() : 가장 앞에 있는 요소를 제거합니다
size() : 큐의 크기입니다.
front() : 가장 앞에 있는 요소를 참조합니다.
deque
앞서 설명한 queue는 앞에서만 끄집어낼 수 있다면 이것은 앞뒤로 삽입, 삭제, 참조가 가능한 자료구조입니다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
deque<int> dq;
dq.push_front(1);
dq.push_back(2);
dq.push_back(3);
cout << dq.front() << "\n";
cout << dq.back() << "\n";
cout << dq.size() << "\n";
dq.pop_back();
dq.pop_front();
cout << dq.size() << "\n";
return 0;
} /* 1 3 3 1 */
Uploaded by
N2T