What do Push and Pop mean for Stacks

Question

long story short my lecturer is crap  and was showing us infix to prefix stacks via an overhead projector and his bigass  shadow was blocking everything so i missed the important stuff  he was referring to push and pop  push   0 pop   x  he gave an example but i cant see how he gets his answer at all    2 3  2-1  5  4-1    step 1 Reverse     1-4  5  1-2  3 2 ok i can see that  he then went on writing x s and o s operations and i got totally lost  answer 14-5 12-32    then reversed again to get    23-21 5-41   if some one could explain to me the push pop so i could understand i would be very greatful  i have looked online but alot stuff im finding seems to be a step above this  so i really need to get an understanding here first

User · Answer

Ok  As the other answerers explained  a stack is a last-in  first-out data structure  You add an element to the top of the stack with a Push operation  You take an element off the top with a Pop operation  The elements are removed in reverse order to the order they were put inserted  hence Last In  First Out   For example  if you push the elments 1 2 3 in that order  the number 3 will be at the top of the stack  A Pop operation will remove it  it was the last in  and leave 2 at the top of the stack   Regarding the rest of the lecture  the lecturer tried to describe a stack-based machine that evaluates arithmetic expressions  The machine operates by continuously popping 3 elements from the top of the stack  The first two elements are operands and the third is an operator     -         It then applies this operator on the operands  and pushes the result onto the stack  The process continues until there is only one element on the stack  which is the value of the expression   So  suppose we begin by pushing the values     23-21 5-41  in left-to-right order onto the stack  We then pop 3 elements from the top  The last in is first out  which means the first 3 element are  1    4   and  -  in that order  We push the number 3  the result of 4-1  onto the stack  then pop the three topmost elements  3  5     Push the result  15  onto the stack  and so on

User · Answer

The rifle clip analogy posted by Oren A is pretty good  but I ll try another one and try to anticipate what the instructor was trying to get across   A stack  as it s name suggests is an arrangement of  things  that has    A top A bottom An ordering in between the top and bottom  e g  second from the top  3rd from the bottom      think of it as a literal stack of books on your desk and you can only take something from the top   Pushing something on the stack means  placing it on top   Popping something from the stack means  taking the top  thing   off the stack   A simple usage is for reversing the order of words   Say I want to reverse the word   popcorn    I push each letter from left to right  all 7 letters   and then pop 7 letters and they ll end up in reverse order   It looks like this was what he was doing with those expressions   push p  push o  push p  push c  push o  push r  push n   after pushing the entire word  the stack looks like         n       lt - top       r           o           c           p           o           p       lt - bottom  first  thing  pushed on an empty stack               when I pop   seven times  I get the letters in this order   n r o c p o p  conversion of infix postfix prefix is a pathological example in computer science when teaching stacks   Infix to Postfix conversion   Post fix conversion to an infix expression is pretty straight forward    scan expression from left to right    For every number  operand  push it on the stack  Every time you encounter an operator    -      pop twice from the stack and place the operator between them   Push that on the stack    So if we have 53 2  we can convert that to infix in the following steps    Push 5  Push 3  Encountered    pop 3  pop 5  push 5 3 on stack  be consistent with ordering of 5 and 3  Push 2  Encountered    pop 2  pop  5 3   push  2    5 3       When you reach the end of the expression  if it was formed correctly you stack should only contain one item   By introducing  x  and  o  he may have been using them as temporary holders for the left and right operands of an infix expression   x   o  x - o  etc    or order of x o reversed    There s a nice write up on wikipedia as well   I ve left my answer as a wiki incase I ve botched up any ordering of expressions

User · Answer

Hopefully this will help you visualize a Stack  and how it works   Empty Stack                           -------   After Pushing A  you get                      A    -------   After Pushing B  you get              B       A    -------   After Popping  you get                      A    -------   After Pushing C  you get              C       A    -------   After Popping  you get                      A    -------   After Popping  you get                           -------

User · Answer

A stack in principle is quite simple  imagine a rifle s clip - You can only access the topmost bullet - taking it out is called  pop   inserting a new one is called  push   A very useful example for that is for applications that allow you to  undo   Imagine you save each state of the application in a stack  e g  the state of the application after every type the user makes  Now when the user presses  undo  you just  pop  the previous state from the stack  For every action the user does - you  push  the new state to the stack  that s of course simplified   About what your lecturer specifically was doing - in order to explain it some more information would be helpful

User · Answer

push   add to the stack pop   remove from the stack

User · Answer

The algorithm to go from infix to prefix expressions is   -reverse input  TOS   top of stack If next symbol is   - an operand - gt  output it  - an operator - gt          while TOS is an operator of higher priority - gt  pop and output TOS         push symbol  - a closing parenthesis - gt  push it  - an opening parenthesis - gt  pop and output TOS until TOS is matching         parenthesis  then pop and discard TOS   -reverse output   So your example goes something like  x PUSH  o POP    2 3  2-1  5  4-1   1-4  5  1-2  3 2  Next Symbol  Stack           Output         x   1                       1 -       x  -            1 4          -            14         o               14-         o               14-         x               14- 5                       14-5         o               14-5          x               14-5          x               14-5  1                       14-5 1 -       x   -           14-5 1 2           -           14-5 12         o               14-5 12-         o               14-5 12-         x               14-5 12- 3                       14-5 12-3         x               14-5 12-3 2                       14-5 12-32         o               14-5 12-32          o               14-5 12-32           o               14-5 12-32        23-21 5-41

User · Answer

A Stack is a LIFO  Last In First Out  data structure  The push and pop operations are simple  Push puts something on the stack  pop takes something off  You put onto the top  and take off the top  to preserve the LIFO order   edit -- corrected from FIFO  to LIFO  Facepalm   to illustrate  you start with a blank stack     then you push  x      x   then you push  y      x   y   then you pop     x

User · Answer

Simply    pop  returns the item at the top then remove it from the stack push  add an item onto the top of the stack

User · Answer

after all these good examples adam shankman still can t make sense of it   I think you should open up some code and try it   The second you try a myStack Push 1  and myStack Pop 1  you really should get the picture   But by the looks of it  even that will be a challenge for you

[stack] What do Push and Pop mean for Stacks?

Examples related to stack

Examples related to terminology

Examples related to infix-notation