// Part 1: Implement a queue
// Restrictions:
// 1. Backed by a fixed memory buffer
// 2. Memory buffer has to be contigous in memory

// Implementation
// Type integer
// Queue of a fixed capacity
// Enqueue() void
// Dequeue() return the value that we're dequeue

// Example:
// Create a queue of capacity 5:
// x x x x x
// Enqueue 1
// 1 x x x x
// Enqueue 2..4
// 1 2 3 4 x
// Dequeue() = returns -> 1
// x 2 3 4 x
// ^ capacity = 5, size = 3

#include<bits/stdc++.h>
using namespace std;
class Queue{
private:
int* buffer;
int capacity;
int front;
int rear;
int size;
public:
//Constructor which inits the queu with given capacity
Queue(int queueCapacity){
    capacity = queueCapacity;
    buffer = new int[capacity];
    front=0;
    rear=0;
    size=0;
}
~Queue(){
    delete[] buffer;
}

void enqueue(int value){
    if(isFull()){
        cout<<"Queue is full, cant add anythihng more"<<value<< endl;
        return;
    }
    
    buffer[rear] = value; // assigning the rear block to value 
    rear = (rear+1)%capacity; // circular increment 
    size++; // making sure we have the acctual size
}

int dequeue(){
    if(isEmpty()){
        cout<<"queue is empty right not, try adding something and then taking it off"<<endl;
        return -1;
    }
    int value=buffer[front];
    front = (front+1)%capacity;
    size--;
    return value;
    
}

bool isEmpty(){
    return size==0;
}
bool isFull(){
    return size==capacity;
}

};

int main(){
    Queue q(3);
    q.enqueue(9);
    q.enqueue(18);
    cout<<q.dequeue()<<endl; //prints 9 
    q.enqueue(27);
    q.enqueue(11);
    cout<<q.dequeue()<<endl; // prints 18
    cout<<q.dequeue()<<endl; // prints 27 
    q.enqueue(10);
    cout<<q.dequeue()<<endl; // print 11 

    // queue with size 3 
    //9 x x 
    //9 18 x 
    //x 18 x 
    // x 18 27 
    //11 18 27 
    //11 x 27 
    // 11 x x 
    // 11 10 x 
    
    // TC : O(1) for both functions 
    // SC : O(n) where n is the capacity of the queue 
    
}

// Part 2:
// Walk me through the design of a queue data structure that stores
// 2 queues over the same shared fixed size memory buffer

// Restrictions:
// - Share the same memory buffer
// - Qeues can be dynamic in size
// - - As long as there is space in the shared buffer, we can continue to grow the size of either queue
// - Be memory efficient

// Solution 
//We're gonna create a linked list with size n 
//we're gonna have 2 queues that are dealing with this linked list so we have the front as the head of the first linkedlist and the last node as the first node for the 2nd queue, basically we try to expand inwards.
//In case we encounter an overflow where there is no more space to add new nodes we can create a new node and assign the end of first queue to point to the new node that we just created and the next of the new node to point to the rear end of the 2nd queue. 
// In case of an underflow we deallocate the memory, we do it if the front and rear of any queue are pointing to the same value. 
//In case we want to recreate any queue we'll follow the recreation again checking if its in the front or the back of the existing queue, if its the front, we point the next of the newly created node to the second queue this way we make sure that both are in the same block of memory and in case we wanna add it in the end, we point the next of current queue to the newly created block