Write a generic container of your own.
What to build
A class template holding items in first-in, first-out order.
Requirements
- Write
Queue<T>withpush(const T&),bool pop(T& out),int size() constandbool empty() const. - Commands are
push X,popandsize.popprints the value, orempty. - Use one
Queue<string>to follow the commands.
Input
The first line has n. Each of the next n lines is a command.
Output
One line for each pop and size.
Constraints
n is from 1 to 1000.
Example
Input:
4
push a
push b
pop
size
Output:
a
1
Why it works
An index for the front means nothing has to be moved when an item leaves, and the template means that the same code would work for any type.
Examples
Example 1 · Input
4 push a push b pop size
Expected output
a 1
Example 2 · Input
2 pop size
Expected output
empty 0
Hints
Hint 1
Keep a vector<T> and an index of the front element.
Hint 2
front() returns the element at the index.
Hint 3
Report an empty queue with a bool return value.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template <typename T>
class Queue {
vector<T> items;
int head;
public:
Queue() : head(0) {}
void push(const T& x) { items.push_back(x); }
bool pop(T& out) {
if (empty()) return false;
out = items[head];
head++;
return true;
}
int size() const { return static_cast<int>(items.size()) - head; }
bool empty() const { return size() == 0; }
};
int main() {
int n;
cin >> n;
Queue<string> q;
for (int i = 0; i < n; i++) {
string command;
cin >> command;
if (command == "push") {
string x;
cin >> x;
q.push(x);
} else if (command == "pop") {
string value;
if (q.pop(value)) cout << value << endl;
else cout << "empty" << endl;
} else {
cout << q.size() << endl;
}
}
return 0;
}