5 Replies - 499 Views - Last Post: 17 November 2012 - 12:45 PM Rate Topic: -----

#1 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 48
  • View blog
  • Posts: 250
  • Joined: 02-February 09

Trouble understanding pop operations (stack)

Posted 17 November 2012 - 08:35 AM

Having some trouble understanding this question (from the book Algorithms, 4th edition):

"Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order onto the stack; the pop operations print out the return values. Which of the following sequence(s) could NOT occur?"

a. 4 3 2 1 0 9 8 7 6 5
b. 4 6 8 7 5 3 2 9 0 1
c. 2 5 6 7 4 8 9 3 1 0
[...]

I'd really appreciate if someone who understands the question would give an explanation :)

This post has been edited by oha055: 17 November 2012 - 08:36 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Trouble understanding pop operations (stack)

#2 g00se  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2720
  • View blog
  • Posts: 11,433
  • Joined: 20-September 08

Re: Trouble understanding pop operations (stack)

Posted 17 November 2012 - 08:52 AM

Quote

[...]

Are we to understand there are more than 3 sequences?
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10561
  • View blog
  • Posts: 39,084
  • Joined: 27-December 08

Re: Trouble understanding pop operations (stack)

Posted 17 November 2012 - 08:55 AM

Remember that Stacks store elements in a last-in-first-out order. So if I push 0, then 1, then 2, the 2 would be the first element to be popped from the Stack. This line is a big hint, by the way:

Quote

The push operations put the integers 0 through 9 in order onto the stack

Was This Post Helpful? 1
  • +
  • -

#4 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 48
  • View blog
  • Posts: 250
  • Joined: 02-February 09

Re: Trouble understanding pop operations (stack)

Posted 17 November 2012 - 12:21 PM

View Postg00se, on 17 November 2012 - 04:52 PM, said:

Quote

[...]

Are we to understand there are more than 3 sequences?


Yes, there are about 6-7 scenarios :)
Was This Post Helpful? 0
  • +
  • -

#5 oha055  Icon User is offline

  • D.I.C Regular

Reputation: 48
  • View blog
  • Posts: 250
  • Joined: 02-February 09

Re: Trouble understanding pop operations (stack)

Posted 17 November 2012 - 12:27 PM

View Postmacosxnerd101, on 17 November 2012 - 04:55 PM, said:

Remember that Stacks store elements in a last-in-first-out order. So if I push 0, then 1, then 2, the 2 would be the first element to be popped from the Stack. This line is a big hint, by the way:

Quote

The push operations put the integers 0 through 9 in order onto the stack


Yes, but doesn't this imply that the stack looks like this: (last)0 1 2 3 4 5 6 7 8 9(first)? then the only solution for a pop sequence would be pop 0, pop 1, etc.

This post has been edited by oha055: 17 November 2012 - 12:28 PM

Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10561
  • View blog
  • Posts: 39,084
  • Joined: 27-December 08

Re: Trouble understanding pop operations (stack)

Posted 17 November 2012 - 12:45 PM

If they push in order, then 9 would be the first element popped.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1