(알고리즘) 바킹독의 실전 알고리즘 0x06강 ( 큐 )
바킹독의 실전 알고리즘 0x06강 ( 큐 )
목차
- 0x00 정의와 성질
- 0x01 기능과 구현
- 0x02 STL list
- 0x03 연습 문제
1. 정의와 성질
- 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝애서 원소를 뺄 수 있는 자료구조
- 스택에서는 먼저 들어간 원소가 나중에 나왔는데, 큐에서는 먼저 들어간 원소가 먼저나오게 됨
- ex) 공항에서 입국수속을 하는 줄과 같은 상황
- FIFO(First In First Out)
1) 큐의 성질
- 원소의 추가가 O(1)
- 원소의 삭제가 O(2)
- 제일 앞/뒤 원소 확인이 O(1)
- 제일 앞/뒤가아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
2. 기능과 구현
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0
void push(int x){
dat[tail++] = x;
}
void pop(){
head++;
}
int front(){
return dat[head];
}
int back(){
return dat[tail-1];
}
void test(){
...
}
int main(void){
test();
}
1) push 함수
2) pop 함수
3) front/back 함수
3. STL queue
#include<bits/stdc++.h>
using namespace std;
int main(void){
queue<int> Q;
Q.push(10); //10
Q.push(20); //10 20
Q.push(30); //10 20 30
cout << Q.size() << '\n'; //3
if(Q.empty()) cout << "Q is empty\n";
else cout << "Q is not empty\n"; Q is not empty
Q.pop(); //20 30
cout << Q.front() << '\n' // 20
cout << Q.back() << '\n' // 30
Q.push(40); // 20 30 40
Q.pop(); // 30 40
cout << Q.front() << '\n' // 30
}
4. 연습문제
1) BOJ 10845: 큐
BackJoon Algorithm 10845 큐 (Java)
댓글남기기