The below program performs the following operations:
- Implements a Queue with standard Enqueue and Dequeue operations to insert and retrieve an element respectively in First In First Out order. The data stored in this case are integers.
- Implements a versioning system for the Queue to maintain a unique version number of the Queue at every Enqueue and Dequeue operations.
- Retrieve the contents of the Queue at any given state with the version number.
#include <iostream> #include <vector> using namespace std; void PrintArray(int*); class The_Queue { vector<int> value; vector<float> version_in; vector<float> version_out; int topIndex, bottomIndex; float current_version; int getStartIndex(float ver) { int index; for(index=0; index<=topIndex; index++) { if((version_out[index] > ver) || (version_out[index]=='')) { return(index); } } return(topIndex+1); } int getEndIndex(float ver) { int index; for(index=0; index<=topIndex; index++) { if(version_in[index] > ver) { return(index); } } return(index-1); } public: The_Queue() { topIndex = -1; bottomIndex = 0; current_version = 0.9; } void Enqueue(int val) { current_version += 0.1; value.push_back(val); version_in.push_back(current_version); version_out.push_back(''); topIndex++; } int Dequeue() { if(topIndex == bottomIndex-1) { return(''); } else { current_version+=0.1; version_out[bottomIndex] = current_version; bottomIndex++; return(value[bottomIndex-1]); } } int* GetAtVersion(float ver) { int index, startIndex=0, endIndex=topIndex; int size; startIndex = getStartIndex(ver); endIndex = getEndIndex(ver); if(startIndex == (endIndex+1)) { size = 0; } else { size = endIndex - startIndex + 1; } int *Result; Result = new int[size+1]; for(index=startIndex; index<=endIndex; index++) { Result[index-startIndex] = value[index]; } Result[index-startIndex] = ''; return(Result); } float getCurrentVersion() { return(current_version); } void PrintAll() { int index; for(index=0; index<=topIndex; index++) { cout<<value[index]<<" "; } cout<<endl; } void PrintAllIn() { int index; for(index=0; index<=topIndex; index++) { cout<<version_in[index]<<" "; } cout<<endl; } void PrintAllOut() { int index; for(index=0; index<=topIndex; index++) { cout<<version_out[index]<<" "; } cout<<endl; } }; void PrintArray(int *arr) { int i; for(i=0; arr[i]!=''; i++) { cout<<arr[i]<<" "; } cout<<endl; } int main(void) { The_Queue q = The_Queue(); int option,val; float ver; int *Res; while(1) { cout<<"Enter option:"<<endl<<"1.Enqueue"<<endl<<"2.Dequeue"<<endl<<"3.Print at Version"<<endl<<"Q.Quit"<<endl; cin>>option; if(option == 1) { cout<<"Enter the value to Enqueue :"<<endl; cin>>val; q.Enqueue(val); } else if(option == 2) { val = q.Dequeue(); if(val == '') { cout<<"Cannot deque. Queue is empty"<<endl; } else { cout<<"The Dequeued value was : "<<val<<endl; } } else if(option == 3) { cout<<"Enter the version number for getting the state of Queue :"<<endl; cin>>ver; if(ver<1.0) { cout<<"No such version present."<<endl; } else { if(ver > q.getCurrentVersion()) { cout<<"No such version present.Returning results for latest version "<<q.getCurrentVersion()<<" instead."<<endl; } Res = q.GetAtVersion(ver); PrintArray(Res); } } else { return 0; } } return(0); }
INPUT / OUTPUT
Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 5 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 12 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 19 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 2 The Dequeued value was : 5 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 212 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 14 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 2 The Dequeued value was : 12 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 299 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 2 The Dequeued value was : 19 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 1000 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 2949 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 1 Enter the value to Enqueue : 789 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 2 The Dequeued value was : 212 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 2 The Dequeued value was : 14 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 2 The Dequeued value was : 299 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 3 Enter the version number for getting the state of Queue : 2.1 212 14 299 1000 2949 789 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 3 Enter the version number for getting the state of Queue : 1.5 12 19 212 14 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 3 Enter the version number for getting the state of Queue : 1.1 5 12 19 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit 3 Enter the version number for getting the state of Queue : 2.2 14 299 1000 2949 789 Enter option: 1.Enqueue 2.Dequeue 3.Print at Version Q.Quit