[C++] queue, deque with Cpp

 

1. queue

 

정의 및 특징

• 먼저 집어넣은 데이터가 먼저 나오는 성질인 FIFO
• 스택과 반대 개념

 

시간 복잡도

• 삽입 및 삭제 -> 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
*/

 

 

method

• push(value)
  • value를 큐에 추가한다.
• pop()
  • 가장 앞에 있는 요소를 제거
• size()
  • 큐의 크기
• front()
  • 가장 앞에 있는 요소를 참조

---

2. deque

• 앞에서 본 queue는 앞에서만 끄집어낼수 있다면
• deque는 앞뒤로 삽입, 삭제 참조가 가능한 자료구조

 

예시 코드

#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
*/

 

 

더 상세한 설명은 아래 게시글 참고

 

2022.09.09 - [CS/자료구조] - [자료구조] 큐(Queue) - 선형 큐, 원형 큐, 우선순위 큐 with Python

[자료구조] 큐(Queue) - 선형 큐, 원형 큐, 우선순위 큐 with Python

 

2022.09.09 - [CS/자료구조] - [자료구조] 큐(Queue)활용 - 버퍼(Buffer), deque with Python

[자료구조] 큐(Queue)활용 - 버퍼(Buffer), deque with Python