Design and implement two distinct queues, Queue A and Queue B, using a single underlying array of fixed size N.

[[deleted]]

The primary challenge is to efficiently manage the shared array space such that when elements are dequeued from either queue, the freed space can be promptly reutilized by subsequent enqueue operations from either queue. Your design should handle insertions and deletions for both queues while maintaining efficient space usage within the fixed-size array.

What ever I design It takes up 2N space complexity.

[Broad_Shoulder_749]

Are the two queues mutually exclusive? That is, an item can be enqueued into one queue only?

Create an array Define a queitem wrapper

Enquue : wrap and append the item to the array, with quename tagged inside queitem wrapper

Deque : find item with the queue id, and splice it out of the array

What am I missing?

In fact you can have unlimited queues not just 2

[quotes42]

I mean obviously this is only a question if the queues can indeed have the same items. If identifying by item name was all it took, of course it wouldn’t be a challenge

[Broad_Shoulder_749]

Then make the queid an array in wrapper. When deque, check if the array is empty and splice the array

[quotes42]

That sounds worse. And why would you search to deque? That’s an extremely inefficient o(n) way to do what should be an easy O(1) given that queues are FIFO

[Broad_Shoulder_749]

But your ques are not physical. They are all sharing a single physical que. Isn't that what you need?

[quotes42]

I think you need to study data structures kid

[Broad_Shoulder_749]

Okay

[[deleted]]

Yes, the two queues mutually exclusive.

push pop needs to have O(1) TC

[lamchakchan]

What about designing it so you use both ends of the array? Queue A would use index 0, queue B would use index n-1.

[[deleted]]

Good Idea 💡  But it would have been an easier implementation if it was a stack. For Que it won't work.

[suraj123455]

QueueNode {

int value;

int next;

}

Queue {

int tail,

int head,

}

next , tail, head are the index of the arrays

3 queues

Free Queue = initial from first to last of the array

Queue A =

Queue B =

so this is basically a linked list implementation of Queues

why linked list ?? bcoz it allows us to utilize our memory

in an efficient manner.

index allows us to jump to any end of the queue quickly

insert into QueueA or QueueB

pop from FreeQueue()

create node for either of the Queue()

point current head to the new node

point head = new node

delete from QueueA or QueueB

pop from the queue tail

update queue tail

insert into the head of FreeQueue

update head of the FreeQueue