![#4 코테준비 - 큐(Queue)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FtZxPx%2FbtrMRHyH4BF%2FsUKUVKYrIBd7ad0RbXmpP0%2Fimg.png)
큐(Queue)
- 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄수있는 자료구조
(FIFO : First In First Out, 은행에서 번호표를 뽑고 기다리리는 것을 생각하면 편함)
-추가되는 곳은 Rear / 제거되는곳은 front
- 원소의 추가/제거 O(1)
- 제일 앞/뒤 원소확인 O(1)
- 앞/뒤가 아닌 원소의 확인 변경x
C++ STL - Queue
C++의 STL에서도 역시 Queue를 제공한다.
코테에서는 따로 구현할 필요 없이 <queue> 헤더파일을 포함시켜 사용하면 된다.
int main()
{
queue<int> Q;
Q.push(2); // 원소 삽입 2
Q.push(3); // 원소 삽입 3
if (!Q.empty()) //큐가 비어있는지 확인 후 제일 앞의 원소(2) 출력
cout << Q.front() << endl;
if (Q.size() != 0) //큐의 사이즈 확인 후 제일 뒤의 원소(3) 출력
cout << Q.back() << endl;
Q.pop(); //제일 앞의 원소 제거 (2 제거)
cout << Q.front();
return 0;
}
함수가 몇개 없기도하고 이름도 직관적이라 사용하기가 편하다.
정확한 내용은 아래 사이트에서 확인 하시면 된다.
https://cplusplus.com/reference/queue/queue/?kw=queue
https://cplusplus.com/reference/queue/queue/?kw=queue
container_typeThe second template parameter (Container)Type of the underlying container
cplusplus.com
연습문제 풀어보기 - 10845번: 큐 (acmicpc.net)
10845번: 큐
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
스택과 똑같이 명령어를 입력받고 큐의 기능들을 실행하는 문제로, 어렵다기보다는 긴 코드를 작성해야하는 문제다.
#include<iostream>
#include<queue>
#include<string>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n = 0;
queue<int> myQueue;
cin >> n;
while (n--)
{
string s;
cin >> s;
if (s == "push")
{
int n;
cin >> n;
myQueue.push(n);
}
else if (s == "pop")
{
if (myQueue.empty()) cout << -1 << '\n';
else
{
cout << myQueue.front() << '\n';
myQueue.pop();
}
}
else if (s == "size")
{
cout << myQueue.size()<< '\n';
}
else if (s == "empty")
{
if (myQueue.empty()) cout << 1 << '\n';
else cout << 0 << '\n';
}
else if (s == "front")
{
if (myQueue.empty()) cout << -1 << '\n';
else cout << myQueue.front() << '\n';
}
else
{
if (myQueue.empty()) cout << -1 << '\n';
else cout << myQueue.back() << '\n';
}
}
return 0;
}
어차피 다른 알고리즘을 사용하는 문제를 풀때 큐를 많이 사용하기때문에 큐의 응용문제들은 풀어보지 않았다.
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
스택을 활용한 수식의 괄호 쌍 (0) | 2022.09.23 |
---|---|
#5 코테준비 - 덱(Deque) (0) | 2022.09.23 |
#3 코테준비 - 스택(Stack) (0) | 2022.09.22 |
#2 코테준비 - 연결리스트 (0) | 2022.09.22 |
#1 코테 준비 - 배열 (0) | 2022.09.21 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!