# Trouble understanding pop operations (stack)

Page 1 of 1

## 5 Replies - 907 Views - Last Post: 17 November 2012 - 12:45 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=300569&amp;s=1028d95f16f1683ee520407957108975&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 oha055

• D.I.C Regular

Reputation: 49
• Posts: 273
• 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

• D.I.C Lover

Reputation: 2998
• Posts: 12,852
• 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?

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11315
• Posts: 42,625
• 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

### #4 oha055

• D.I.C Regular

Reputation: 49
• Posts: 273
• Joined: 02-February 09

## Re: Trouble understanding pop operations (stack)

Posted 17 November 2012 - 12:21 PM

g00se, 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

### #5 oha055

• D.I.C Regular

Reputation: 49
• Posts: 273
• Joined: 02-February 09

## Re: Trouble understanding pop operations (stack)

Posted 17 November 2012 - 12:27 PM

macosxnerd101, 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

### #6 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11315
• Posts: 42,625
• 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.