Data Structure : Stack

A stack is a data structure in which nodes are added vertically one over the other. To understand it better, consider a stack of books. Because each book is heavy and they are stacked, you can really only do one of three things:

A stack of books

1. Look at the surface of the top book
2. Take the top book off the stack
3. Put a new book on top of the stack

A Data Structure Stack

In programming, a stack is a container that holds other variables (much like an array). However, whereas an array lets you access and modify elements in any order you wish, a stack is more limited. The operations that can be performed on a stack are identical to the ones above:

1) Look at the top item on the stack (usually done via a function called top())
2) Take the top item off of the stack (done via a function called pop())
3) Put a new item on top of the stack (done via a function called push())


Since it has restrictions regarding insertion and deletion of nodes it is also called "restricted" or "closed ended linked list".  A stack is a last in, first out (LIFO) data structure. If you put a new book on top of the stack, anybody who takes a book from the stack will take the book you just pushed on first. This means that the element which will be added last will be the first one to be removed. As items are pushed onto a stack, the stack grows larger — as items are popped off, the stack grows smaller.Whenever a new element is added to stack the existing elements are pushed a step downwards, similarly when items are removed from the top all the elements are shifted a step upwards. Therefore insertion and deletion in a stack are also called "push" and "pop" respectively.  The push operation adds an item to the top of the stack, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the stack, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty stack.
  The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are those that have been on the stack the longest.

Advantages and Disadvantages:

1. Memory allocated on the stack stays in scope as long as it is on the stack. It is destroyed when it is popped off the stack.
2. All memory allocated on the stack is known at compile time. Consequently, this memory can be accessed directly through a variable.
3. Because the stack is relatively small, it is generally not a good idea to do anything that eats up lots of stack space. This includes allocating large arrays, structures, and classes, as well as heavy recursion.

Application of Stack
Stacks can be used to evaluate postfix expressions. An ordinary mathematical expression such as 2+(15-12)*17 is called an infix expression. In an infix expression, an operator comes in between its two operands, as in "2 + 2". In a postfix expression, an operator comes after its two operands, as in "2 2 +". The infix expression "2+(15-12)*17" would be written in postfix form as "2 15 12 - 17 * +". The "-" operator in this expression applies to the two operands that precede it, namely "15" and "12". The "*" operator applies to the two operands that precede it, namely "15 12 -" and "17". And the "+" operator applies to "2" and "15 12 - 17 *". These are the same computations that are done in the original infix expression.

Now, suppose that we want to process the expression "2 15 12 - 17 * +", from left to right, and find its value. The first item we encounter is the 2, but what can we do with it? At this point, we don't know what operator, if any, will be applied to the 2 or what the other operand might be. We have to remember the 2 for later processing. We do this by pushing it onto a stack. Moving on to the next item, we see a 15, which is pushed onto the stack on top of the 2. Then the 12 is added to the stack. Now, we come to the operator, "-". This operation applies to the two operands that preceded it in the expression. We have saved those two operands on the stack. So, to process the "-" operator, we pop two numbers from the stack, 12 and 15, and compute 15 - 12 to get the answer 3. This 3 will be used for later processing, so we push it onto the stack, on top of the 2, which is still waiting there. The next item in the expression is a 17, which is processed by pushing it onto the stack, on top of the 3. To process the next item, "*", we pop two numbers from the stack. The numbers are 17 and the 3 that represents the value of "15 12 -". These numbers are multiplied, and the result, 51 is pushed onto the stack. The next item in the expression is a "+" operator, which is processed by popping 51 and 2 from the stack, adding them, and pushing the result, 53, onto the stack. Finally, we've come to the end of the expression. The number on the stack is the value of the entire expression, so all we have to do is pop the answer from the stack, and we are done! The value of the expression is 53.