0

I've seen this way of implementing a queue with two stacks: https://stackoverflow.com/a/2050402/494094

And I've read that this way the queue is immutable and thread-safe. What's the point that separates this from a normal queue and makes it immutable and thread-safe?

I'd really appreciate it if someone could explain it in a simple, non-professional way.

Community
  • 1
  • 1
hattenn
  • 4,371
  • 9
  • 41
  • 80
  • possible duplicate of [How to implement a queue using two stacks?](http://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks) – Peter O. Dec 02 '11 at 14:16

1 Answers1

2

How to implement a queue using two stacks? explains more and has some code.

If you do this in a low-level way you will have two memory areas and two pointers One pointer increments when you write, the other when you read

Once the read area is used up, you reverse the write area and swap the two.

So there is no chance of the reading interfering with the writing and vice versa. The only connection between the two operations is during the "reverse and swap" operation, and then everybody has to wait.

Community
  • 1
  • 1
Alftheo
  • 868
  • 7
  • 17
  • singly-linked list backed queue (like this one http://stackoverflow.com/a/69206/1294552) can achieve immutability and concurrency with CAS and volatile. why do we need to invoke the cost of copying with 2-stack approach? Can you explain in more details. Thanks. – ying May 20 '13 at 20:08
  • Same question to impl stack with 2-queue. – ying May 20 '13 at 20:10