Building a queue with two stacks

[pozorvlak]

Here's a data-structure I use almost every day. It's an implementation¹ of a queue. You have two stacks, an in-stack and an out-stack. To add a new item, push it onto the in-stack. To remove an item, take the top item off the out-stack; if the out-stack's empty, push all the items on the in-stack onto the out-stack in reverse order and then take

Comments

[stronae]

I love the application to laundry, and I also love the kitties. Kitties!

[pozorvlak]

They're gorgeous, aren't they? We've had them for just over two months now (since Burns Night, which is part of the reason we called him Haggis).

[fanf]

This is the standard implementation of a queue in functional programming languages :-)

Are your t-shirts immutable?

[pozorvlak]

They're very rarely modified, unless you count getting them dirty.

[fanf]

That's just a garbage collection problem, isn't it? At least, for very small garbage objects.

[pozorvlak]

:-)

[kragen]

Very nice

[kragen]

More laundry algorithms: on the complexity of sock-matching.

[anonymous]

This was in the first or so homework of the first data structures compsci class I took back in the day.

[anonymous]

When the out-stack is empty, why not just swap the stack references? The out-stack becomes the new in-stack, and the old-instack becomes the new out-stack. Then, proceed as usual. (Resembles stop n' copy GC algorithm :)

[pozorvlak]

Because then the in-stack would be upside-down :-)

[anonymous]

Oops. I couldn't take wearing my Sunday t-shirt on a Thursday ...

[pozorvlak]

I'm not so worried about that; I guess your system does have the desired property that all T-shirts are worn approximately as often as each other.