<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
using namespace std;
struct Queue
{
private:
int* elements;
int frontIndex;
int backIndex;
public:
Queue(int n)
{
elements = new int[n];
frontIndex = 0;
backIndex = -1;
}
~Queue() {}
void push(int x)
{
elements[++backIndex] = x;
}
int pop()
{
if (empty()) return -1;
else
{
return elements[frontIndex++];
}
}
int size()
{
return backIndex - frontIndex + 1;
}
bool empty()
{
if (frontIndex > backIndex) return true;
else return false;
}
int front()
{
if (empty()) return -1;
else return elements[frontIndex];
}
int back()
{
if (empty()) return -1;
else return elements[backIndex];
}
};
int main()
{
// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
Queue q(N);
for (int i = 0; i < N; i++)
{
string order;
cin >> order;
if (order == "push")
{
int n;
cin >> n;
q.push(n);
}
else if (order == "pop")
{
cout << q.pop() << "\n";
}
else if (order == "size")
{
cout << q.size() << "\n";
}
else if (order == "empty")
{
cout << q.empty() << "\n";
}
else if (order == "front")
{
cout << q.front() << "\n";
}
else if (order == "back")
{
cout << q.back() << "\n";
}
}
return 0;
}<풀이과정>
- Queue
1. Queue라는 구조체를 선언하여 큐를 직접 구현하였다.
2. private으로 포인터 elements와 int형 변수 frontIndex, backIndex를 선언한다.
3. public으로 함수를 구현한다.
3-1. Queue(int n)
3-1-1. 이 함수는 생성자로 생성과 동시에 동작하는 함수이다.
3-1-2. n을 인수로 받아와 n 크기의 배열을 만들고 elements를 해당 배열을 가리키게 한다.
3-1-3. frontIndex는 0으로, backIndex는 -1로 초기화 시켜준다.
3-2. push(int x)
3-2-1. push는 큐의 맨 뒤에 원소를 넣어주는 작업이다.
3-2-2. x를 인자로 받아오고 elements의 backIndex를 1증가시킨 후에 해당 인덱스에 x를 넣어준다.
3-3. pop()
3-3-1. pop은 큐의 맨 앞의 원소를 빼내는 작업이다.
3-3-2. 큐가 빈 경우에는 -1을 리턴하고, 비어있지 않다면 elements의 frontIndex번째 원소를 리턴한 뒤 frontIndex를 증가시킨다.
3-4. size()
3-4-1. size는 큐의 크기를 나타낸다.
3-4-2. 맨 뒤 원소의 인덱스를 가리키는 backIndex와 맨 앞 원소의 인덱스를 가리키는 frontIndex를 빼준 뒤 1을 더해준 값을 리턴해준다.
3-5. empty()
3-5-1. empty는 큐가 비어있는지 여부를 나타낸다.
3-5-2. frontIndex가 backIndex보다 크다면 맨 앞의 원소가 맨 뒤의 원소보다 큰 경우이므로 큐가 비어있다는 의미이다. 따라서 이 경우에는 true를 리턴하고 그렇지 않으면 false를 리턴해준다.
3-6. front()
3-6-1. front는 맨 앞의 원소를 알려주는 함수이다.
3-6-2. 만약 큐가 비어있는 경우라면 -1을 리턴해주고 그렇지 않으면 elements의 frontIndex번째 원소를 리턴해준다.
3-7. back()
3-7-1. back은 맨 뒤의 원소를 알려주는 함수이다.
3-7-2. front와 마찬가지로 큐가 비어있다면 -1을 그렇지 않으면 elements의 backIndex번째 원소를 리턴해준다.
- main
1. 앞서 정의한 구조체 Queue를 이용해 q를 선언한다. 이때 정의했던 생성자를 이용해 N의 크기로 선언해준다.
2. N만큼 반복하며 명령어를 나타내는 string형 변수 order를 입력받는다.
3. order에 따라 각 함수를 실행시켜준다.
4. push인 경우에는 n을 한번 더 입력받아 큐에 원소를 넣어주는 작업을 진행하고, 나머지의 경우는 해당함수를 출력해주는 작업을 진행한다.
<코멘트>
큐를 직접 구현하여 풀어보았다!
<제출결과>
