Data structures

Oh man! Ad-blocking software has been detected! :'(

This website is run by the community, for the community... and it needs advertisements in order to keep running. Blocking our ads means your killing our stats!
Please disable your ad-block, or become a premium member to hide all advertisements and this notice.

OK before i put question one on this page, does anyone know anything about data structures and stacks at all. Im struggling to find out how they are worked out etc

Ed

 

Oh man! Ad-blocking software has been detected! :'(

This website is run by the community, for the community... and it needs advertisements in order to keep running. Blocking our ads means your killing our stats!
Please disable your ad-block, or become a premium member to hide all advertisements and this notice.

Yes I do. Email me if you like.

 

Thats ever so slightly vague really. I know about stacks to some extend. Whether my knowledge is enough to cover your query is only going to be apparent once you take the time to tell us the issue you are having.

I'm assuming this is a programming query, but Im aware that there are 'stacks' in other areas of IT, so perhaps not. Again, you need to give more detail.

 

Sorry for the delay in reply guys

This is the question in full as it is on the paper. The answer is -22 but how they come to that answer is beyond me

Q1) some numbers are pushed onto a stack in the following order, 2,5,-8, 12 ,-15, 3. Write down the numbers on the stack, first starting from the number on top of the stack and proceeding down the stack to the last number. Later, first 2 numbers are popped (using pop operation) off the stack and multiplied togeher and the result is pushed (using push operation) onto the stack. the following operations are then performed in the listed order

pop, pop, add, push
pop, pop, subtract , push
pop pop, add push
pop pop subtract push

what number is at the top of the stack after the above operations? what other numbers are on the stack?

Thats the question exactly as it is on my sheet, now really i need help in how they come to -22, i get that sussed and ill piss the rest.

Also im sure youll understand the scenario thats known as reverse polish, in regards to stacks??

Thanks for your time.

Eddie

 

This is indeed reverse polish - with a vengeance! Not sure that 'Data structures' is the right description - but it is debatable!

First thing you need to understand is that the 'stack' resembles the dinner plate stacks you see in some refectories - i.e. a base on springs with the stack of plates on it, and taking a plate off means the stack rises.

So lets push the values. This gives a stack of:

3
-15
12
-8
5
2

Don't forget you are putting these 'plates' on the stack.

Now pop the top two and multiply. 3 * -15 = -45. Push it and the stack is:

-45
12
-8
5
2

"pop, pop, add, push' = -45 + 12 = -33

the stack now is:

-33
-8
5
2

"pop, pop, subtract, push" = -33 - -8 = -25

the stack now is:

-25
5
2

"pop, pop, add, push" = -25 + 5 = -20

the stack now is:

-20
2

"pop, pop, subtract, push" = -20 -2 = -22

the stack now is:

-22

Harry.

 

Right lets do this mate!

Pop means to take the current top value off the stack
Push means to add the next number onto the top of the stack

So we start off and our stack looks like:

3 (top)
-15
12
-8
5
2 (bottom)

3 and -15 = 3 * -15 = -45 then that is pushed onto the stack so we have:

-45
12
-8
5
2

1. pop and pop = -45 and 12 then add them = -33 then push so stack is

-33
-8
5
2

2. pop and pop = -33 and -8 then subtract = - 25 then push so stack is

-25
5
2

3. pop and pop = -25 and 5 then add them so you get = -20 then push so stack is

-20
2

4. pop and pop = -20 and 2 then subtract them so you get -22 then push so your stack now is

-22

and there you go!!

 

Harry, thank you i know where i was going wrong

"pop, pop, subtract, push" = -33 - -8 = -25

I was not doing this i was just treating it as -8 which took me to -41 which is wrong totally.

I realise now it was meant to be -33 --8

Thanks for that

 

I'm glad you have sorted it! You need to watch the signs! <grin>

Harry.

 

Hbroomhall and Zimbo laid it out nicely. If you wish to really understand you need to investige 'queues'. A stack is a 'Last In First Out' (LIFO) queue. There are a variety of others out there (FIFO, LIFO, etc.), but I'll leave you to investigate.

Stacks are also the foundation of assembly programming, but that's a little far down the line right now.