A queue implemented using an array

Question

We've just finished learning about queues in my data structures class; I want to make sure I really understand it. I'm still feeling a bit lost on how to optimize the data use of a queue. I've created a little program here:

#include <iostream>
class Queue{
public:
 Queue(int size = 10){
 ptr = new int[size];
 head = counter = 0;
 qSize = size;
 }
 void push(int value){
 if(counter == qSize)
 doubleSize();
 ptr[counter++] = value; 
 }
 int pop(){
 if(counter == 0){
 std::cout << "The queue is empty!!! \n";
 return -1;
 }
 if(head >= counter - 1){
 int temp = ptr[head];
 std::cout << "This is the last item in the queue. \n";
 delete[] ptr;
 ptr = new int[qSize];
 head = counter = 0;
 return temp;
 }
 return ptr[head++]; 
 }
private:
 int *ptr;
 int head;
 int counter;
 int qSize;
 void doubleSize(){
 int prevSize = qSize;
 qSize *= 2;
 int *temp = new int[qSize];
 for(int i = 0; i < prevSize; i++){
 temp[i] = ptr[i];
 }
 delete[] ptr;
 ptr = temp;
 }
};

So, as you can test, the program runs fine; but what I'm looking for is how I can optimize my queues to be as efficient as possible. I.E. Is there a specific way that I should be programming these queues that uses the minimum amount of data, and has the smallest Order complexity?

P.S. I am aware that there is a queue library. I am more seeking to optimize how I program out queues themselves.

Answer 1

It would be a good idea for the Queue class to offer a .size() method, so that the caller can avoid popping an empty queue.

While your memory-management technique will work, it is not efficient. If you repeatedly push and pop elements, you'll end up reallocating the array quite a bit. Furthermore, when you call .doubleSize(), you end up copying all of the old array elements, including the ones before the head that have already been popped and are no longer relevant.

A better design would be to use the array as a circular buffer, growing it only when the capacity is exceeded.

• TheMachoMuchacho: Awesome; thank you for the pointers! (No pun intended).

Answer 2

Rule of Zero

You should follow the rule of zero where class that deal with memory ownership should deal exclusively with memory ownership. Your class allocate raw memory but do not free it when being destroyed. It will leak memory. Also issue with copying your queue. You should use std::unique_ptr instead of raw new.

Reuse memory when queue is empty

Why do you need to free the underlying memory when the queue is empty? Can't you just set head to the beginning and reuse the memory? This will save you from having to allocate new memory.

Use STD algorithm

Use std::copy_n instead of for loop in doubleSize() to make your code more readable.

• TheMachoMuchacho: Thanks for the help. Yeah, when you point those things out, I'm thinking "wow, I can't believe I didn't think to do that." Thanks again!

Answer 3

Re-use Data Structures

You should realistically be using an std::vector which would do all of the resizing internally. That's not to say that re-inventing a resizeable array isn't a worthwhile exercise, but that it is a separate problem and should be done separately from your queue.

---

Use Appropriate Data Structures

That being said, I also challenge the use of an array at all. The only reason to use an array as your underlying data structure is for contiguous memory to be more cache friendly. This isn't likely to be something you need from your queue and most are not implemented this way.

---

Write more Robust and Flexible code

Templates are not the answer to everything, but here they are almost necessary. Your queue has very limited usefulness by only working with ints. What if I need to use it with long or float? What if I make my own Event class and want to use it with that? As it is right now it is very rigid and limited. By learning some basic Template Metaprogramming (Which won't be easy) you can seriously improve your flexibility by working with any type.

---

Consider The Standard and Your Use Case

In most cases you are going to need the functionality of the standard library. In that case it is worthwhile in exercises to mimic the standard.

std::deque (or Double-Ended Queue) and std::queue are the standard versions. I just want you to look at the member functions sections of those two classes and consider how you would implement each of those.

Answer 4

Using streams to debug is a bad habit, and your error management is quite erroneous. See this bug:

Queue q{};
q.push(-1);
std::cout << "pop: " << q.pop() << '\n'; // <- will print "-1", the last int pushed
std::cout << "pop: " << q.pop() << '\n'; // <- will print "-1" too, cause the queue is empty

Instead, catch errors using exception handling, std::optional{} or terminate().

And when this and the other problems raised above are corrected, an interesting development could be to set up a Growing Policy as optional parameter.

Optionally, as well as a size() method, it would be a good addition to implement capacity() and reserve() methods.