How can we implement two stack in an array?

Question

How can we implement an LRU cache using just a single container i.e. map or unordered_map?

Expected operations:
1. find(key_t) - find a certain value in cache
2. insert(key_t, value_t) - insert a new value to the cache

Answer 1

Just an algo -
1. start two stacks from two extreme corners of array.
2. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0.
3. stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1).
4. Both stacks grow (or shrink) in opposite direction.

How to check overflow
Check space between top elements of the two stacks.

Comments

Implemented your algo :)
#include<iostream>
#include<stdlib.h>
 
using namespace std;
 
class twoStacks
{
    int *array;
    int size;
    int top_stack1, top_stack2;

public:
   twoStacks(int n)  
   {
       size = n;
       array = new int[n];
       top_stack1 = -1;
       top_stack2 = size;
   }
 
   void push1(int x)
   {
       // check for one empty space
       if (top_stack1 < top_stack2 - 1)
       {
           top_stack1++;
           array[top_stack1] = x;
       }
       else
       {
           cout << "Overflow";
           exit(1);
       }
   }
 
   void push2(int x)
   {
       // check for one empty space
       if (top_stack1 < top_stack2 - 1)
       {
           top_stack2--;
           array[top_stack2] = x;
       }
       else
       {
           cout << "Overflow";
           exit(1);
       }
   }
 
   int pop1()
   {
       if (top_stack1 >= 0 )
       {
          int x = array[top_stack1];
          top_stack1--;
          return x;
       }
       else
       {
           cout << "Underflow";
           exit(1);
       }
   }
 
   int pop2()
   {
       if (top_stack2 < size)
       {
          int x = array[top_stack2];
          top_stack2++;
          return x;
       }
       else
       {
           cout << "Underflow";
           exit(1);
       }
   }
};