문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
워낙에 문제가 간단하여, 바로 풀이한다. 이지만, 생각해야 할 것이 있다.
우선 큐의 구현에는 크게 2가지의 방법이 있다.
1. 배열 이용
2. 링크드 리스트를 이용
여기서는 단순 배열을 이용한다.
배열을 이용하는 큐는 기본적으로 메모리 공간 낭비라는 문제점이 있다.
왜냐하면 큐는 스택과 달리 입출력이 2개 이므로 front/rear를 갖는 인덱스가 필요하는데 ( front 삭제 , rear 삽입 )
삭제 시 front++, 삽입 시 rear++ 된다. 그런데 계속 삽입이 된다면 배열의 구조 상으로 0,1,2,3~~ 앞의 인덱스는 영원히
사용하지 못하게 될 뿐만 아니라. 메모리가 부족해지고 나중에는 아무것도 삽입 할 수가 없다.
이런 현상을 표류 현상(Drift, Rightward Shift)이라고 한다.
이를 해결하기 위하여 특정 rear가 배열의 특정 index에 도달하면 배열의 모든 큐 값들은 왼쪽으로 정리(Shift Left)할 수 있으나, 비용이 매우 크다.
그러므로 왼쪽 이동(Shift Left)을 피하면서 빈 공간을 재사용하고자 원형 배열(Circular Array)를 사용한다.
이를 위한 개념은 단순히 rear/front의 인덱스를 ++하는 것이 아니라 원형으로 증가해야한다.
7개의 배열 크기를 예로써
7에서 1을 증가시킨 인덱스가 8이 아닌 다시 0을 가리키게 하는 것이다.( 이는 리어 인덱스를 증가시킬 공간이 없으므로 다시 처음 인덱스인 0을 되돌려 그곳에 삽입하기 위함이다.)
이 인덱스를 다시 처음으로 돌릴 수 있게 하는 연산자가 모듈로(Module,%)함수로서, (Rear + 1) % MAX로 표시할 수 있다.
이 모듈로 함수에 대한 힌트는 본인도 교재에서 힌트를 얻었다.
역시 삽입/삭제시 검사를 해야한다. 삭제는 인덱스를 증가하면 되지만, 삽입은, 기존의 큐 값을 지울 수가 있다. (
이를 위하여 삽입시 count변수를 두어 ++, 삭제 시 count변수를 --하는 식으로 현재 큐안의 값을 알아내고, 이것을 이용하여 count값이 배열의 크기를 초과하지 않았을 때만 push하여 기존의 큐 값이 덮어씌워지는 것을 방지할 수 있다.
#include
#include
#define MAX 10000
using namespace std;
class Queue {
public:
void push(int value);
int pop();
bool empty() { if (count == 0) return true; else return false; };
int size() {return count;};
int front() {
if (empty()) return -1;
return q[front_];
}
int back() {
if (empty()) return -1;
return q[rear_];
}
private:
int q[MAX];
int front_{ 0 };
int rear_{ -1 };
int count{ 0 };
};
void Queue::push(int value) {
if (count <= MAX) {
++count;
rear_ = (rear_ + 1) % MAX;
q[rear_] = value;
}
}
int Queue::pop() {
int temp;
if (empty()) {
return -1;
}
temp = q[front_];
front_ = (front_ + 1) % MAX;
--count;
return temp;
}
int main() {
int end{ 10000 };
int num{ 0 };
string cmd{ "" };
int i = 0;
Queue queue;
cin >> end;
while (i < end) {
cin >> cmd;
if (cmd == "push") {
cin >> num;
queue.push(num);
}
else if (cmd == "front") {
cout << queue.front() << endl;
}
else if (cmd == "pop") {
cout << queue.pop() << endl;
}
else if (cmd == "size") {
cout << queue.size() << endl;
}
else if (cmd == "back") {
cout << queue.back() << endl;
}
else if (cmd == "empty") {
cout << queue.empty() << endl;
}
++i;
}
return 0;
}
C++ 17버전이고 이하버전에서는 {}이용한 변수 초기화 빌드 에러등이 발생 할 수 있다.
