Skip to content

Instantly share code, notes, and snippets.

@wsgac
Created May 17, 2019 10:15
Show Gist options
  • Select an option

  • Save wsgac/940f83de173a8e166412bd9d41cfebb8 to your computer and use it in GitHub Desktop.

Select an option

Save wsgac/940f83de173a8e166412bd9d41cfebb8 to your computer and use it in GitHub Desktop.
Simple queue implementation in C++ using templates
template <class T>
class queue {
T *buffer;
int buf_size;
int front_index;
int back_index;
int buf_grow_factor;
void realloc() {
T *tmp = new T[buf_size*buf_grow_factor];
int size = 0;
if (front_index <= back_index) {
for (int i = 0; i < buf_size; i++)
tmp[size++] = buffer[i];
} else {
for (int i = front_index; i < buf_size; i++)
tmp[size++] = buffer[i];
for (int i = 0; i < back_index; i++)
tmp[size++] = buffer[i];
}
front_index = 0;
back_index = buf_size;
delete[] buffer;
buffer = tmp;
buf_size *= buf_grow_factor;
}
public:
queue(int init_size, int grow_factor) {
buf_grow_factor = grow_factor;
buffer = new T[init_size];
buf_size = init_size;
back_index = 0;
front_index = 0;
}
~queue() {
delete[] buffer;
}
void push_back(T item) {
buffer[back_index++] = item;
if (back_index == buf_size)
back_index = 0;
if (back_index == front_index)
realloc();
}
void pop_front() {
// Decrement back_index; if it turns negative, wrap around the end
front_index++;
if (front_index == buf_size)
front_index = 0;
}
T front() {
return buffer[front_index];
}
int size() {
if (front_index <= back_index)
return back_index - front_index;
return buf_size - (front_index - back_index);
}
bool empty() {
return size() == 0;
}
};
int main() {
queue<int> q(4, 2);
for(int i = 0; i < 10; i++)
q.push_back(i);
while (!q.empty())
{
cout << q.front() << endl;
q.pop_front();
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment