There are a few weaknesses in your code, that @Edward already pointed out, such as using namespace std and, worse, #include <bits/stdc++.h>. But I really like that you tried to rely on std functionalities. Building your queue upon std::vector is almost right.
Delve further into the STL
A queue is a "FIFO" container: the first element in is also the first element out. It means that you won't discard elements from the end you insert them into: so the right container isn't std::vector, which is optimized for insertion/deletion of the last element, but std::deque, which provides fast insertion/deletion at both ends. With std::vector, you need to reallocate memory every time you delete the front member, and that's inefficient.
Make your own deque
Of course, you might not want to use std::deque directly, especially if you're looking for a good exercise. Then I'd suggest you implement your own. As cppreference says:
typical implementations use a sequence of individually allocated fixed-size arrays
So, still relying on the STL, we can use an std::list of std::arrays.
Let's begin with that:
template <typename T, std::size_t N = 5>
// N is the size of the statically allocated arrays
class Queue {
using block = std::array<T, N>; // cosmetic alias
using iterator = typename block::iterator;
public:
Queue();
void push(const T& value);
void pop();
T front() const;
private:
std::list<block> storage; // our sequence of arrays
iterator first, last; // pointers to first and last elements
};
So we have a class with two template arguments: the type your deque will contain, and the size of inner arrays. The user might want big arrays if speed is more important than memory, or the opposite. I've chosen a default size without putting much thought into it.
block and iterator are aliases; in this case, I only use them to make the code more readable.
Now let's implement the different functions:
template <typename T, std::size_t N>
Queue<T, N>::Queue() {
storage.push_back(block{});
first = std::begin(*std::begin(storage));
last = first; // last == first <=> empty queue
}
No difficulty here, a simple constructor ensures the queue is ready to use by allocating a first array, and initializing the iterators to the first and last element. They're equal, meaning the queue is empty.
template <typename T, std::size_t N>
void Queue<T, N>::push(const T& value) {
if (last == std::end(*std::rbegin(storage))) { // rbegin!!
storage.push_back(block{});
last = std::begin(*std::rbegin(storage));
}
*last++ = value;
}
In order to push a new element, you need to be sure that there's some room left. last is increment after every push, so you need to verify it hasn't reached the end of the last allocated array. std::rbegin returns an iterator to the last element (!= std::end, which returns an iterator past the last element).
If there isn't any room left, we add another block to our sequence.
Then pop is a mirror, and front doesn't present any difficulty:
template <typename T, std::size_t N>
void Queue<T, N>::pop() {
if (++first == std::end(*std::begin(storage))) {
storage.pop_front();
first = std::begin(*std::begin(storage));
}
}
template <typename T, std::size_t N>
T Queue<T, N>::front() const { // const here means you don't modify your object
return *first;
}
A working example
to toy with:
#include <iostream>
#include <list>
#include <array>
template <typename T, std::size_t N = 5>
class Queue {
using block = std::array<T, N>;
using iterator = typename block::iterator;
public:
Queue();
void push(const T& value);
void pop();
T front() const;
private:
std::list<block> storage;
iterator first, last;
};
template <typename T, std::size_t N>
Queue<T, N>::Queue() {
storage.push_back(block{});
first = std::begin(*std::begin(storage));
last = first;
}
template <typename T, std::size_t N>
void Queue<T, N>::push(const T& value) {
if (last == std::end(*std::rbegin(storage))) {
std::cout << "requiring new storage" << '\n';
storage.push_back(block{});
last = std::begin(*std::rbegin(storage));
}
*last++ = value;
}
template <typename T, std::size_t N>
void Queue<T, N>::pop() {
if (++first == std::end(*std::begin(storage))) {
std::cout << "freeing unused memory" << '\n';
storage.pop_front();
first = std::begin(*std::begin(storage));
}
}
template <typename T, std::size_t N>
T Queue<T, N>::front() const {
return *first;
}
int main() {
Queue<int> queue;
queue.push(5);
queue.push(4);
queue.push(3);
queue.push(2);
queue.push(1);
queue.push(0);
queue.push(-1);
queue.push(-2);
for (auto x = 0; x < 8; ++x) {
std::cout << queue.front() << '\n';
queue.pop();
}
}