queue implementation using stack

queue implementation using stack

Page 1 of 1

8 Replies - 32550 Views - Last Post: 20 May 2010 - 10:57 AM Rate Topic: -----

#1 pankaj_modi2001  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 1
  • Joined: 25-August 07

queue implementation using stack

Posted 25 August 2007 - 03:49 PM

how to implement queue using  :rolleyes: two stack

Is This A Good Question/Topic? 1

Replies To: queue implementation using stack

#2 PennyBoki  Icon User is offline

  • system("revolution");
  • member icon

Reputation: 53
  • View blog
  • Posts: 2,334
  • Joined: 11-December 06

Re: queue implementation using stack

Posted 25 August 2007 - 03:55 PM

Hi, welcome. You need to show us some code if you have trouble with it, but if this is only a question and if you mean two stacks for one queue:

The top of stack one will be front of the queue, and the top of the stack two, would be back of the queue.
Was This Post Helpful? 0
  • +
  • -

#3 musya  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,012
  • Joined: 25-April 07

Re: queue implementation using stack

Posted 25 August 2007 - 06:20 PM

View Postpankaj_modi2001, on 25 Aug, 2007 - 03:49 PM, said:

how to implement queue using  :rolleyes: two stack


Why would you use two stacks for a queue? why not just use a queue? Or am i not understanding something here?
Was This Post Helpful? 0
  • +
  • -

#4 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: queue implementation using stack

Posted 25 August 2007 - 06:45 PM

the reason you use 2 is because the first item goes into 1st stack then the second goes into the second stack and and the first item is popped from the first stack and placed on top of the second.
Now your items are in order of a queue with the first stack empty.
As an item is added it the properly ordered stack flips all members into the other stack so they reverse the order. The new item is added in the now empty stack and the elements are then placed back on top ALL in the correct order. Since you reversed the existing part twice.

This is not efficient, but a good exercise. The code will be difficult i imagine if you could not even think of how/why to use a stack to accomplish this.
Was This Post Helpful? 1

#5 musya  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,012
  • Joined: 25-April 07

Re: queue implementation using stack

Posted 25 August 2007 - 07:01 PM

View PostWilliam_Wilson, on 25 Aug, 2007 - 06:45 PM, said:

the reason you use 2 is because the first item goes into 1st stack then the second goes into the second stack and and the first item is popped from the first stack and placed on top of the second.
Now your items are in order of a queue with the first stack empty.
As an item is added it the properly ordered stack flips all members into the other stack so they reverse the order. The new item is added in the now empty stack and the elements are then placed back on top ALL in the correct order. Since you reversed the existing part twice.

This is not efficient, but a good exercise. The code will be difficult i imagine if you could not even think of how/why to use a stack to accomplish this.


Ive seen this done before with stack and queues, my book talked about it, im familiar with it, just not that familiar with it, never needed to use it yet :D.
Was This Post Helpful? 0
  • +
  • -

#6 William_Wilson  Icon User is offline

  • lost in compilation
  • member icon

Reputation: 205
  • View blog
  • Posts: 4,807
  • Joined: 23-December 05

Re: queue implementation using stack

Posted 25 August 2007 - 07:12 PM

no one will ever "need" to use it, it's clearly a school exercise.

If the average user really knew what was going on, they'd realize how truly a waste this is, since both are actually implemented using arrays in the language, thus this exercise adds a complex abstraction to the queue, only to teach the students how to use stacks and so they understand queues... oddly enough I miss school, lol
Was This Post Helpful? 0
  • +
  • -

#7 musya  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 11
  • View blog
  • Posts: 1,012
  • Joined: 25-April 07

Re: queue implementation using stack

Posted 25 August 2007 - 09:14 PM

View PostWilliam_Wilson, on 25 Aug, 2007 - 07:12 PM, said:

no one will ever "need" to use it, it's clearly a school exercise.

If the average user really knew what was going on, they'd realize how truly a waste this is, since both are actually implemented using arrays in the language, thus this exercise adds a complex abstraction to the queue, only to teach the students how to use stacks and so they understand queues... oddly enough I miss school, lol


Hence my first reply, why not just use a queue the first place?
Was This Post Helpful? 0
  • +
  • -

#8 Bench  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 855
  • View blog
  • Posts: 2,338
  • Joined: 20-August 07

Re: queue implementation using stack

Posted 26 August 2007 - 03:41 AM

The simple answer is - You can use a stack to reverse the order of elements stored in a container, so create one stack, and reverse it using the second.

But I'm equally puzzled as to what your tutor is trying to teach you, except, perhaps, how to abuse the tools of the language whilst far better facilities are available to do the job.
Was This Post Helpful? 0
  • +
  • -

#9 Guest_Alex*


Reputation:

Re: queue implementation using stack

Posted 20 May 2010 - 10:57 AM

View PostWilliam_Wilson, on 25 August 2007 - 05:45 PM, said:

the reason you use 2 is because the first item goes into 1st stack then the second goes into the second stack and and the first item is popped from the first stack and placed on top of the second.
Now your items are in order of a queue with the first stack empty.
As an item is added it the properly ordered stack flips all members into the other stack so they reverse the order. The new item is added in the now empty stack and the elements are then placed back on top ALL in the correct order. Since you reversed the existing part twice.


I don't think that is how it is supposed to work. Instead, you have two stacks. When you push an item on to the queue, you push it onto the first stack. When you pop an item off the queue, you pop it off of the second stack. If however, there are no items on the second stack, you pop all of the items off the first stack and onto the second stack, there by reversing the order. The reason why this is a good implementation is because it will only choke up a few times, all other times the operations will be insanely fast.
Was This Post Helpful? 0

Page 1 of 1