Week 2 (자료 구조) - 문제 10845번 (큐)

문제:

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력:

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

예제 입력1:

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

 

예제 출력1:

1
2
2
0
1
2
-1
0
1
-1
0
3

 

코드:

#include <iostream>
#include <string>

using namespace std;

class queue
{

int number; //자료구조 안의 데이터 개수
int Front; //가장 앞을 나타내는 인덱스 (원형 큐)
int Back; //가장 뒤를 나타내는 인덱스 (원형 큐)
int* Q; //배열 저장

public:

queue() //생성자 함수
{
Q = new int[10000]; //배열 사용(명령의 개수만큼)
Front = 0; //앞 인덱스
Back = 0; //뒤 인덱스
number = 0; //자료 개수
}

void push(int X) //push  함수
{
Q[Back] = X; //가장 뒤 인덱스 초기화

Back++; //Back +1

if (Back >= 10000) //Back이 배열가장 끝보다 크다면
{
Back = Back % 10000;
}

number++;
}

int pop() //pop 함수
{
if (number == 0) //아무것도 없다면 -1
{
return -1;
}

else
{
Front++; //앞의 것을 빼므로 Front +1

if (Front >= 10000) //Front가 배열 끝보다 커지면
{
Front = Front % 10000;
}

number--; //pop되므로 갯수 -1

if (Front == 0) //Front가 위에서 배열 끝보다 커져 0이 된 경우
{
return Q[10000 - 1];
}

else //앞에서 증가연산자로 미리커졌으므로 -1한 값 리턴
{
return Q[Front-1];
}
}
}

int Size() //size 함수
{
return number;
}

bool empty() //empty 함수
{
if (number == 0)
{
return 1;
}

else
{
return 0;
}
}

int front() //front 함수
{
if (number == 0)
{
return -1;
}

else
{
return Q[Front];
}
}

int back() //back 함수
{
if (number == 0)
{
return -1;
}

else
{
return Q[Back-1];
}
}
};

void go(queue q1, int size) //밖에서 입력받는 함수
{
string str;
int Psh;

if (size == 0)
return;

cin >> str;
if (str == "push")
{
cin >> Psh;
q1.push(Psh);
}

else if (str == "pop")
{
cout << q1.pop() << endl;
}

else if (str == "empty")
{
cout << q1.empty() << endl;
}

else if (str == "size")
{
cout << q1.Size() << endl;
}

else if (str == "empty")
{
cout << q1.empty() << endl;
}

else if (str == "front")
{
cout << q1.front() << endl;
}

else if (str == "back")
{
cout << q1.back() << endl;
}

go(q1, size - 1); //재귀 사용

}

int main() //메인 함수
{

queue q;
int size;

cin >> size;
go(q, size);

return 0;
}

 

설명:

주석 참고