Solved

# question about push and pop and stacks (very URGENT)

Posted on 2004-11-12
271 Views
Hi,
I have a question about stacks, push, and pop, related to postfix and prefix notation. Say I have a the postfix notation of abc x+ and the reverse Polish prefix of cb x a +. Right now I have the stacks like this:

Prefix             Postfix
c                     +
b                     x
x                     c
a                     b
+                     a

Am I stacking these correctly?  With the pre-fix I'm stack LIFO (I think) and the post-fix FILO (first in last out). Sorry if this is confusing. What I basically want to know is if the stacking method is correct and if there is anything from having both stacks be LIFO or FILO.  Or put another way, how do you know how to stack a problem like this? The infix notation of this is a+ (bxc) if this helps any. I hope this makes some kind of sense. If all is lost hopefully someone can explain stacks to me and push and pop.

Thanks

Angela
0
Question by:collegegirl

LVL 3

Accepted Solution

Your correct in your stacks. It was a little difficult understanding the LIFO / FIFO ordering but now that I took 45 minutes to look at it and understand it. It looks good.

To answer your question of why would you choose one method LIFO over FIFO, its all about user preference and what would make the problem the easiest to solve. When I wrote my Pascal Compiler for my Comp. Sci Bachelors degree I used 2 FILO stacks simultaneously. One stack for the variables, and one stack for the operators because it was easier to think about it, and hence code it that way. It also made tracking my variables and operators easier because my program didnt have to figure out if it was examining an operator or a variable because they were seperated in different stacks.

To describe push and pop, you must first understand that a stack is a data structure in which the last item you put in the data structure is normally the next item you would take off the stack.  The word Push means to put an item on top of the stack. The word pop means to take an item off the top of the stack.

There is nothing that would prevent you from coding any stack to be used in LILO or FILO order.  But, if you code it using LILO order the industry would probably call it a it a "queue" instead of a stack. Also, Its an industry convention that the concept of a stack is FILO ordered, just for the ease of communicating with others what your talking about..
0

LVL 2

Assisted Solution

I agree with djwillms.
A stack is a data structure and it is commonly FIFO (first in, first out).
I do not understand your example, however if you want to do this simple calculation: a+b*c in reverse polish the stack will look like this:

FIFO:
*
c
+
b
a

A good reference for data structures is in: Data Structures in C++ by L.A. Tenenbaum -  ISBN: 0135293227
0

LVL 44

Assisted Solution

there is a bit of confusion about terminlogy here.  A STACK is always LIFO - think of a stack of plates.  The last plate you put ON the stack will be the first plate you later take OFF the stack.

A QUEUE (pronounced CUE if you aren't familiar with the word), is always FIFO - a queue is like the line at your bank or super market.  When you get into the line, you wait your turn until you get to the head of the line, and then you are serviced.  A queue always services items in the exact order that they were added to the queue.  A stack always services items in the REVERSE order that they were added to the stack.

AW
0

LVL 2

Expert Comment

Yes... Arthur is right.
My example is a LIFO...

Sorry bout that.
-tom
0

LVL 44

Expert Comment

Angela, one of the purposes of this site is to facilitate a DIALOG bewtten teh asker and the answerer(s).  That means that you should say something.  If what we told you was not clear, then you should askl for clarification.  But to NOT SAY ANYTHING, and then accept an answer, and simply grade it a B is not going to go very far in encouraging Experts here, in the future, to offer you any assistance.

Just a simple word of advice.

Glad we could assist you, in what would seem to be ab incomplete manner.

AW
0

Author Comment

Hi,
I didn't understand that  a B was a bad grade.... in college it means above average. What does it mean here? Are you supposed to give explaination if you grade below an A? Can you show me where it talks about how to grade questions on this site? I will admit that the answers wasn't clear to me so that's why I didn't give it an A but I didn't think they were bad answers. It didn't occur to me to say something back because I didn't even know where to start so I ended the question. I kind of understand how to do stacks but it still confuses me. I tried to give everyone who helped me some of the points. I didn't realize that the grade would be a problem. I always appreciate the help I get from the experts on this sites. It really helps me. That's why I wanted to give points to everyone because at least they tried to help me.

Anyway sorry for the confusion. In my world a B is pretty good but I'll keep it in mind next time.

Angela
0

LVL 2

Expert Comment

Angela,

I agree with you.
Anyway if you are looking for some additional information, please refer to the book that I mentioned in my first post.

Hope it helps
-tom
0

Author Comment

Thanks Tom and everyone else for your help. I really do appreciate it.

Angela :)
0

LVL 44

Expert Comment

Angela, you say "I will admit that the answers wasn't clear to me so that's why I didn't give it an A but I didn't think they were bad answers.", in which case, you should ask for more explanation.  We are trying to make it as clear as possible, so that you can learn from the experts here.  And a while a B is a 'good' grade, if you don't ask for more expalantion when something is not clear, how are we to be able to guess that you need more in the way of information.  When you don't ask we must assume that what has been provided satisfies your current needs, and no further effort is needed.  In that casxe, a 'B' seems to be a 'slap in trhe face'.  Most of the people here have many claims on their time, and cannot/will not volunteer more details that seems to be needed, just to see their words types on the screen.  If more details are needed, and that need is expressed, then we are more than willing to explain, but when the need is not expressed, then very few will offer what would appear to be un-needed verbage.

AW
0

LVL 2

Expert Comment

Let it go Arthur... let's move on.

-tom
0

Author Comment

Hi again,
I'm sorry but I am confused. I didn't mean to slap anyone in the face and I'm not sure how I did. I really do appreciate the help everyone gives me....its been crucial for me this semester. I really didn't think a B would offend anyone. I have read the help section about grading and I will take it into consideration next time I ask a question and grade someone, as I know that its important to the experts. I'm new to this site and I tried to explain why I gave the grade I did but it still seems to be misunderstood. I don't know anything else to say except I'm learning as I go along so please be patient with me.

Thanks again Tom and everyone else who helped,

Angela
0

LVL 2

Expert Comment

No problem Angela, your decision was correct to my eyes... it is what I had done in your position.
You not have to explain your actions here to anyone. Who cares A, B or C anyway... the purpose here is "help each other" not "compete each other, be the first and the hell with others" so... again, you not have to explain anything!!!

Enjoy the information!!! Enjoy the site!!! Keep going...
-tom
0

## Featured Post

### Suggested Solutions

This article will show, step by step, how to integrate R code into a R Sweave document
A short article about problems I had with the new location API and permissions in Marshmallow
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…