Self doubt

Question

What are the minimum number of pointers required to implement a stack using single ended queue ( the queue is NOT a dequeue )?

 

Comments

i think 2 , cause if u take 1 pointer then how will get to know whether queue is full or not

i have a doubt that ur question is incomplete

Answer 1

As per I think... Its 2 (FRONT and REAR) (If u r thinking of having single pointer then it will not be a queue anymore bcoz queue has enqueue and dequeue operations in constant time).

Comments

I think we need two queues to implement a stack..then shouldn't we consider two sets of front and rear pointer for the two queues?

Then total will be 4..

---

true , but thats a bruteforce approach. If we are talking about minimum then one more solution is possible. Try to keep the latest inserted element at the Front pointer.

1: Insert x at rear node

2: perform dequeue followed by enqueue until x reaches the FRONT.

---

I was thinking the same. In that case we can get away with just one queue.

However for this to work I think the queue should be circular queue. Otherwise we will quickly reach to the end of queue and no more enque will be possible.

Answer 2

since there is no Dequeue then we need three pointers