1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Data structures

Discussion in 'Training & Development' started by zxspectrum, Oct 16, 2008.

  1. zxspectrum

    zxspectrum Gigabyte Poster Premium Member

    1,666
    54
    139
    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
     
    Certifications: BSc computing and information systems
    WIP: 70-680
  2. dmarsh

    dmarsh Terabyte Poster

    3,782
    302
    184
    Yes I do. Email me if you like. :D
     
    Certifications: CITP, BSc, HND, SCJP, SCJD, SCWCD, SCBCD, SCEA, N+, Sec+, Proj+, Server+, Linux+, MCTS, MCPD, MCSA, MCITP, CCDH
  3. Fergal1982

    Fergal1982 Petabyte Poster

    4,196
    171
    211
    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.
     
    Certifications: ITIL Foundation; MCTS: Visual Studio Team Foundation Server 2010, Administration
    WIP: None at present
  4. zxspectrum

    zxspectrum Gigabyte Poster Premium Member

    1,666
    54
    139
    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
     
    Certifications: BSc computing and information systems
    WIP: 70-680
  5. hbroomhall

    hbroomhall Petabyte Poster Gold Member

    6,623
    115
    224
    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.
     
    Certifications: ECDL A+ Network+ i-Net+
    WIP: Server+
  6. zimbo
    Honorary Member

    zimbo Petabyte Poster

    5,215
    98
    181
    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!! :biggrin
     
    Certifications: B.Sc, MCDST & MCSA
    WIP: M.Sc - Computer Forensics
  7. zxspectrum

    zxspectrum Gigabyte Poster Premium Member

    1,666
    54
    139
    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
     
    Certifications: BSc computing and information systems
    WIP: 70-680
  8. hbroomhall

    hbroomhall Petabyte Poster Gold Member

    6,623
    115
    224
    I'm glad you have sorted it! You need to watch the signs! <grin>

    Harry.
     
    Certifications: ECDL A+ Network+ i-Net+
    WIP: Server+
  9. Mathematix

    Mathematix Megabyte Poster

    969
    35
    74
    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. :biggrin
     
    Certifications: BSc(Hons) Comp Sci, BCS Award of Merit
    WIP: Not doing certs. Computer geek.

Share This Page

Loading...