Description
Please consider the following c++ struct code. Implement a circular queue function without using c++ STL.
#include <iostream>
using namespace std;
class QueueArray{
public:
QueueArray():capacity(5),front(-1),rear(-1){
queue = new int[capacity];
};
bool IsEmpty() const ;
int GetCapacity() const ;
void Push(int x);
void Pop();
private:
int *queue;
int capacity, front, rear;
void DoubleCapacity();
};
void QueueArray::DoubleCapacity(){
int *newQueue = new int[capacity*2];
int j = -1;
for (int i = (front + 1) % capacity; i != (rear + 1) % capacity; i = (i + 1)%capacity) {
j++;
newQueue[j] = queue[i];
}
capacity *= 2;
front = -1;
rear = j;
delete [] queue;
queue = newQueue;
}
bool QueueArray::IsEmpty() const {
// TODO
}
void QueueArray::Push(int x){
// TODO
}
void QueueArray::Pop(){
// TODO
}
int QueueArray::GetCapacity() const {
return capacity;
}
int main(){
QueueArray q;
string cmd;
while(cin >> cmd){
if(cmd == "push"){
int x;
cin >> x;
q.Push(x);
}else if(cmd == "pop"){
q.Pop();
}else if(cmd == "isEmpty"){
q.IsEmpty() ? cout << "true" << endl : cout << "false" << endl;
}else if(cmd == "getCapacity"){
cout << "capacity: " << q.GetCapacity() << endl;
}
else if(cmd == "exit"){
return 0;
}
}
return 0;
}
Hint:
1. 只需實作有寫 //TODO 的三個 function。
Push: 將 integer x 放入 queue 中。當 push 會填滿整個 queue 時，要做 doubling queue 的動作。（May simply call QueueArray::DoubleCapacity()）
Pop: 除了執行刪除元素的動作之外，還須把該元素 output 出來。（後面請加換行符號）另外，若 queue 為空，則不做任何事。
IsEmpty: 當 queue 為空時，回傳 true；否則回傳 false。
2. 因為我們實作的是 circular queue，請留意它的 capacity。
Input
多行的 string（push 包含數字），依據不同的 string 做不同的指令。
push x : 執行 QueueArray::Push， 將 x push 入 queue 之中。
pop: 執行QueueArray::Pop，並output該刪除的數字，如queue為空，則不須動作。
isEmpty: 執行 QueueArray::IsEmpty。當 queue 為空時 output "true"；反之，output "false"。
getCapacity: 執行 QueueArray::GetCapacity。並 output "capacity: " 加上當前 queue 的 capacity。
exit: 結束程式。
Output
當讀到 pop, isEmpty, getCapacity 時，做出相對應的 output。
Tags