Queue Delete at middle in constant time (Only possible way is using doubly linked list)
#include<bits/stdc++.h> using namespace std; struct doublyqueue { int d; doublyqueue* next=NULL; doublyqueue* prev=NULL; }; doublyqueue *front=NULL; doublyqueue *rear=NULL; doublyqueue *mid=NULL; // f->null r->null mid =null // f->1<-r mid=1 i.e when changed from even to odd by push mid updated // f->1>2><r mid =1 odd to ev no ch //f->1>2>3<r mid=2 i.e mid=mid->next when changed to odd and n!=1 // f->1>2>3<r deque 1 i.e,( changed from odd to even) then no change in mid // f->2->3<r mid =2 deque again => only 1 ele and mid is 3 i.e mid=m->next if changed from even to odd // deque => mid= 2 i.e mid= mid->prev i.e // now check for delete mid ex only 1 then mid=null //if 1 2 mid=1 and delmid=> mid=m->next; // if 1 2 3 mid= 2 del mid => mid=m->prev; // 1 2 3 4 m=2 del 2 => 1 3 4 mid = 3 i.e m->next; // i.e size reduced and if new size is odd =>...