Stacks

* Stacks are efficient data structures because data can be added or removed only from the
top of a stack, making these procedures fast and easy to implement.

*Stacks are used extensively in programming language implementations for everything from expression
evaluation to handling function calls.
 

LIFO (Last-In First-Out)

A stack is a list of elements that are accessible only from one end of the list, which is
called the top. One common, real-world example of a stack is the stack of trays at a
cafeteria. Trays are always removed from the top, and when trays are put back on the
stack after being washed, they are placed on the top of the stack. The stack is known as
a last-in, first-out (LIFO) data structure.

Stack operations
Operation on a stack:
push() - adds another stack item to the top of the list 
peek() - returns the value of the item at the top of the list
pop() - remove the item from the top of the list

The different uses of stacks

There are several problems for which a stack is the perfect data structure needed for the
solution. In this section, we look at several such problems.

Multiple Base Conversions

First lets go trough the mathematical way of converting bases.

The simplest way to convert from decimal to binary is to divide by 2 and kepping the reminder, then dividing the result of  step 1 by 2 and keeping the reminder.
So on until you deplete your number.
Example:

16 % 2 = 8      reminder 0
8 % 2 = 4        reminder 0
4 % 2 = 2        reminder 0
2%2 = 1         reminder 0
1% 2 = 0        reminder 1         

Then reverse the array of the reminders to get the binary number for 16, which is 10000

The same is done to convert between other bases, for example to convert to base 6 you just deviding by 6, following the same steps.

This procedure, is perfect for stacks, because you create a stack of the reminders (array/list), then you go from top to bottom (from end of the array/list) pushing the top number into a new array, thus reversing the array. This a LIFO procedure because you operate only on the top of the stack, meaning the last item pushed to the top of the array will be the first to be pushed to the second array.
 

Palindromes

Palindromes are words that are spelled the same when reversed, if excluding strings a simple flip procedure on a stack will give us the same string as the original string.
Take for example the string "race car". if the space character is extracted the string will be the same value after a flip.
So, the steps for this algorithms are:
1. split the string into an array off characters.
2. iterate over the array to find the indices to any space characters.
3. extract those space characters out of the array.
4. iterate over the resulting string from top to bottom (FILO, from end of array), pushing each value into a new array.

 

Demonstrating Recoursion

Since recursion creates a stack of active functions, its an excellent way to demonstrate stacks.
A good way to demonstrate recursion and the how it creates stacks of function calls is using factorials.
for example, taking the factorial of 5, 5! = 5*4*3*2*1. We can open up a stack of function calls, each passing up the previous number minus one, till the number is 1.
When we reach the number 1 we start returning results, resolving the stack as each function returns the value for the multiplication of n * n-1. 
Example: 

function factorial(n) {
    if (n === 0) {
        return 1;
    }
    else {
        return n * factorial(n-1);
    }
}

which will look like:

factorial(5) 
             |_> factorial(4)
                    |_> factorial(3)
                          |_>factorial(2)
                                |_> factorial(1)
                                       |_> factorial(0)
                                            return 1 <_|
                           return 1 <_|
                       return 2 <_| 
                    return 6 <_|         
              return 24 <_| 
           return 120 <_|