Class Templates

Lab C++ Intermediate 20 points

Write template <typename T> class Stack backed by a vector with push, pop, top and empty. Use a Stack<string> to reverse the words of each input line.

Input

n, then n lines.

Output

n lines.

Example

Input

2
hello big world
one

Output

world big hello
one

Sample input available Sample output available

Editor

C++

Hints

The template parameter T is used wherever the element type is needed.

Solution explanation

This is roughly how std::stack is built.

Show solution

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
class Stack {
public:
    void push(const T &x) { items_.push_back(x); }
    void pop() { items_.pop_back(); }
    const T &top() const { return items_.back(); }
    bool empty() const { return items_.empty(); }

private:
    vector<T> items_;
};

int main() {
    int n;
    cin >> n;
    string line;
    getline(cin, line);
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        istringstream in(line);
        Stack<string> s;
        string w;
        while (in >> w) s.push(w);
        bool first = true;
        while (!s.empty()) {
            cout << (first ? "" : " ") << s.top();
            s.pop();
            first = false;
        }
        cout << "\n";
    }
    return 0;
}

Output

Answer