versioned_queue.cpp

#include <iostream>
#include <cassert>
#include <vector>
using namespace std;

typedef struct qsnap {
    int first;
    int last;
    qsnap(int f, int l) : first(f), last(l) {}
} qsnap;

class Queue {
    vector<int> queue;
    vector<qsnap> versions;
    int first=0, length=0;
    int cur_version = 0;

  public:
    Queue();
    ~Queue();
    void snapshot();
    int pop();
    void push(int elem);
    void print(int version);
};

Queue::Queue() {}
Queue::~Queue() {}

void Queue::snapshot() {
    this->versions.push_back(qsnap(this->first, this->queue.size()));
    this->cur_version++;
}

int Queue::pop() {
   assert(this->length > 0);

   // store version information
   this->snapshot();

   // update queue
   int elem = this->queue[this->first];
   this->first++;
   this->length--;
   return elem;
}

void Queue::push(int elem) {
    // store version information
    this->snapshot();

    this->queue.push_back(elem);
    this->length++;
}

void Queue::print(int version) {
    assert(version <= cur_version);

   if (version == cur_version) {
        for (int i = this->first; i < this->queue.size(); ++i) {
            cout<<this->queue[i]<<", ";
        }
        cout<<endl;
    } else {
        qsnap qs = this->versions[version];
        for (int i = qs.first; i < qs.last; ++i) {
            cout<<this->queue[i]<<", ";
        }
        cout<<endl;
    }
}

int main() {
    int n, elem, version;
    char cmd;
    Queue q;
    cin>>n;
    for (int i = 0; i < n; ++i) {
        cin>>cmd;
        switch(cmd) {
        case 'e':
            cin>>elem;
            q.push(elem);
            break;
        case 'p':
            cin>>version;
            q.print(version);
            break;
        case 'd':
            q.pop();
            break;
        default:
            cout<<"Error: invalid command"<<endl;
        }
    }
}