is it possible to construct a stack using queques?

michal

p.s. is there a group devoted to algoritms?

Michal Adamczakk wrote:

Since I've never heard of queques, I'll assume it's a typo. :-)

(BTW Your subject line reads "fifo 2 lilo", but stacks are LIFO, not LILO.)

Okay, let's see...

Depends what you mean by "queue", I guess. If you are prepared to accept a
double-ended queue (or "deque"), it's trivial - just block off one end of
the deque!

Otherwise, it's trickier, and I don't immediately see how you would do this.
Interestingly, Knuth sets the opposite problem as an exercise: "Suppose you
are allowed to use only stacks as data structures. How can you implement a
queue efficiently with two stacks?" (Yes, it's possible.)

Unfortunately, I don't see a way to do the converse operation. A stack
reverses the flow of the data, so you can do this twice to simulate a
queue. But since queues are "one-way", I don't see any way to join them up
so as to twist the data round, so to speak.

Perhaps there is a way that I'm just not seeing. Anyone?

That's more or less what comp.programming is supposed to be about, so you
are already in the right place, I think.

--
Richard Heathfield : binary@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

On Fri, 19 Dec 2003 02:06:30 +0000 (UTC), Richard Heathfield
<dontmail@address.co.uk.invalid> wrote:

I dunno, does it matter if it is efficient or not? If not, we can
reverse a queue using three queues. Suppose we have three queues, A,
B, and S. Start with everything in A, B and S empty. Peel off
everything in A, putting it in B, except for the last thing, which you
put in S. Do the same thing with B, putting everything in A except
the last, which you add to S. Continue until everything in is in S.

That's a proof of principle. It's your turn to make it efficient.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
A man with money is always charming - pomposity is just
an eccentricity, forgivable in the rich.

Michal Adamczakk wrote:
Sure, it's pretty much the same way you'd implement a queue using two
stacks.

Given queue A and queue B, define these operations:

push(x): remove elements from queue A and add them to queue B, one by
one, until queue A is empty. Add x to A. Remove elements from B and
put them back on A.

pop(): remove element from A.

--
Pull out a splinter to reply.

Richard Heathfield <dontmail@address.co.uk.invalid> wrote in message news:<brtmf5$qf8$1@sparta.btinternet.com>...
I suppose you could flush the queue into another queue and catch the
last piece piece of data as if 'falls out' of queue 1 then claim it's
behaving like stack! That's a fairly grotesque way though!

What i'd do is... well.. i'd use a stack!

yeah, i didn't find anything effective still i believe that's why we have
both
thanks for all the suggestions

michal

Peter Ammon wrote:

Very neat.


(Having said that, when I need a stack, I'll use a stack!)

--
Richard Heathfield : binary@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

Richard Heathfield wrote:
They're electronic vegetables, as in "piqles are made from quequmbers."
Personally, I find them quequmbersome.