CODEWITHSUNDEEP
javaalgorithmstackqueue
AMH9
AMH9

Reputation: 179

copying Queue and Stack into each other

I want to use an empty stack S to check whether a Queue Q contaitns element x, thus my solution was to copy elements of Q into S and check if contain x, but I'm also asked to return S elements into Q again as it was originaly, this must be done using only a Q and S without any other arrays of SL, so I have written this algorithm:

Boolean found ← false
int element ←  0
While(Q is not empty) 

  element ← Q.dequeue()
  if(element equal x)
           found ← true
  S.push(element)

While(S is not empty)
 ( elements back to Q) ?

stuck in last step, if I used Q.enqueue(S.pop) then the order of elements in Q will be reversed

Upvotes: 0

Views: 1416

Answers (4)

Roudy Tarabay
Roudy Tarabay

Reputation: 449

I am not sure how java default Queue work.

  1. Remove element from the end of the queue.
  2. Check if that element is x, if so return true.
  3. Else, push it into the stack
  4. Repeat until you find x or all the Queue is empty.
  5. When you are done, pop elements one by one from the stack and add them at the beginning of the queue everytime, the last element in the stack would become the first element in the queue. Thus you maintain the order.

Upvotes: 0

Tomer Shahar
Tomer Shahar

Reputation: 343

Correct, the order will be reversed. This means that if you repeat the algorithm yet again (all to S and back to Q) you will reverse it yet again, meaning you will get back to the original order of elements, which is what you want.

Upvotes: 1

Ishay Peled
Ishay Peled

Reputation: 2868

This feels like a HW question so I won't solve it for you, but I will give you a hint - what happens when you dequeue a queue into a stack and then dequeue the stack back to the queue?

How can you use that phenomena to restore the original queue?

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726599

if I used Q.enqueue(S.pop) then the order of elements in Q will be reversed

That's right, it will be reversed. You can use it to your advantage by observing that once you run the same loop again, you would get the original order back.

You can avoid writing the same loop twice if you make a method that does the search, and leaves the queue in reversed state. You can call your search method twice, and ignore the second return value.

Upvotes: 1

Related Questions