Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- struct Node {
- Node(Node *n, int v) : next_(n), value(v){}
- Node *next_;
- int value;
- };
- struct PersistentStack {
- vector<Node* > versions;
- vector<Node* > memory;
- PersistentStack() {
- versions.push_back(nullptr);
- }
- void push(int version, int value) {
- auto newRoot = new Node(versions[version], value);
- versions.push_back(newRoot);
- memory.push_back(newRoot);
- }
- void pop(int version) {
- versions.push_back(versions[version]->next_);
- }
- void print(int version) {
- cout << version << ": ";
- auto curr = versions[version];
- while (curr) {
- cout << curr->value << ' ';
- curr = curr->next_;
- }
- cout << "\n";
- }
- // void destroy(Node* n) {
- // while (n) {
- // Node *newRoot = n->next_;
- // delete n;
- // n = nullptr;
- // n = newRoot;
- // }
- // }
- ~PersistentStack(){
- for (auto & m : memory) {
- delete m;
- }
- }
- };
- int main() {
- PersistentStack st;
- st.print(0);
- st.push(0, 1);
- st.print(1);
- st.push(1, 3);
- st.print(2);
- st.pop(1);
- st.print(3);
- st.push(3, 10);
- st.print(4);
- st.push(4, 15);
- st.print(5);
- st.push(5, 20);
- st.print(4);
- st.print(6);
- st.print(3);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement