Answer: Stacks and queues

Question: In class and in Assignments 2 and 5 you implemented a queue using a linked list. Arrays allow a more efficient method for bounded-length queues. In an array, one has two indices indicating where the top and bottom of the queue are. When the index goes over the array bound, then we circle back 0 and begin again. Implement an array queue using the following array definition.

    class Queue {
    public:
                        Queue(int max_size);
                        ~Queue() { delete[] data; }
        bool            isEmpty() { return counter == 0; }
        bool            isFull() { return counter == max_size; }
        void            put(int item);
        int             get(); // return -1 if queue empty
    private:
        int             max_size;
        int             *data; // an array of length max_size
        int             head; // the index of the front item in queue
        int             tail; // the index of the end item in queue
        int             count; // the number of items in queue
    };

Answer:

Queue::Queue(int max_size) {
    this->max_size = max_size;
    data = new int[max_size];
    head = 0;
    tail = 0;
    count = 0;
}

void
Queue::put(int item) {
    if(!isFull()) {
        data[tail] = item;
        tail = (tail + 1) % maxSize;
        ++count;
    }
}

char*
Queue::get() {
    if(isEmpty()) {
        return -1;
    } else {
        int ret = data[head];
        head = (head + 1) % maxSize;
        --count;
        return ret;
    }
}