prashant4224 · March 29, 2021 17:48 · Mar 21, 2020
diff --git a/Implement LRU cache b/Implement LRU cache
@@ -0,0 +1,87 @@
+// We can use stl container list as a double 
+// ended queue to store the cache keys, with 
+// the descending time of reference from front 
+// to back and a set container to check presence 
+// of a key. But to fetch the address of the key 
+// in the list using find(), it takes O(N) time. 
+// This can be optimized by storing a reference 
+//	 (iterator) to each key in a hash map. 
+#include <bits/stdc++.h> 
+using namespace std; 
+
+class LRUCache { 
+	// store keys of cache 
+	list<int> dq; 
+
+	// store references of key in cache 
+	unordered_map<int, list<int>::iterator> ma; 
+	int csize; // maximum capacity of cache 
+
+public: 
+	LRUCache(int); 
+	void refer(int); 
+	void display(); 
+}; 
+
+// Declare the size 
+LRUCache::LRUCache(int n) 
+{ 
+	csize = n; 
+} 
+
+// Refers key x with in the LRU cache 
+void LRUCache::refer(int x) 
+{ 
+	// not present in cache 
+	if (ma.find(x) == ma.end()) { 
+		// cache is full 
+		if (dq.size() == csize) { 
+			// delete least recently used element 
+			int last = dq.back(); 
+
+			// Pops the last elmeent 
+			dq.pop_back(); 
+
+			// Erase the last 
+			ma.erase(last); 
+		} 
+	} 
+
+	// present in cache 
+	else
+		dq.erase(ma[x]); 
+
+	// update reference 
+	dq.push_front(x); 
+	ma[x] = dq.begin(); 
+} 
+
+// Function to display contents of cache 
+void LRUCache::display() 
+{ 
+
+	// Iterate in the deque and print 
+	// all the elements in it 
+	for (auto it = dq.begin(); it != dq.end(); 
+		it++) 
+		cout << (*it) << " "; 
+
+	cout << endl; 
+} 
+
+// Driver Code 
+int main() 
+{ 
+	LRUCache ca(4); 
+
+	ca.refer(1); 
+	ca.refer(2); 
+	ca.refer(3); 
+	ca.refer(1); 
+	ca.refer(4); 
+	ca.refer(5); 
+	ca.display(); 
+
+	return 0; 
+} 
+// This code is contributed by Satish Srinivas