Stack and Queue

1.      Stack

Stack is one of data structure concept that store data in orderly way. For stack the data order is LIFO or Last In First Out manner.  It’s was like you see a pile of chair it’s was make with chair stacked from the bottom one but when you need a chair you take the last (upper one) first.

There are 2 way you can make a stack. The first one is using array and the second is using linked list. Even thought using array is easier when using array, we need to declare a fixed size, but linked list doesn’t need to declare size and can keep make a new space.so when we don’t know the size of stack we make it using linked list.

   a.      Stack Operation

There are 3 operation for stack:

-        Push(x)  : push is operation to add x to top of the stack.

-        Pop()      :pop is operation to remove an item from the top of the stack.

-        Top()      :top is operation to return the top from the stack.

We must remember to use a same push and pop so if you push from head you need to pop from head to because LIFO order.

   b.      Stack Application

Stacks are widely used to:

-        Reverse the order of data

-        Convert infix expression into postfix

-        Convert postfix expression into infix

-        Backtracking problem

-        System stack is used in every recursive function

-        Converting a decimal number into its binary equivalent

-        Depth First Search.

   2. Infix, Postfix, and Prefix Notation

Infix, Postfix, and Prefix Notation are one of stack application. For simple they can be explained like:

        -        Prefix     : operator is written before operands

        -        Infix       : operator is written between operands

        -        Postfix   : operator is written after operands

3.      Queue

Queue is like stack both are concept that store data in an order. but in queue we use FIFO or First In First Out order. If stack was like a pile of chair queue was like a line for restaurant if you line first, you can go in first.

               To make queue we use the same ways with stack. We can make queue using array and using linked list. Same with stack, using array are easier but because the size is fixed, we need to use linked list if we don’t know the size.

   a.      Queue Operation

 There are 3 operation for queue:

-        Push(x) :push is operation to add x to the back of the queue.

-        Pop()     :pop is operation to remove an item from the front of the stack.

-        Top()     :top is operation to return the front from the stack.

If stack must use the same push and pop in queue, we must use different push and pop so if you push the front you must pop the back. It was because the first in will go out first (FIFO).

   b.      Queue Application.

-        Deques

-        Priority Queues

-        Breadth First Search

   c.      Type of Queue

-        Circular queue

Circular queue is queue where the first index is connected with the last index.so first index will come after last index.

-        Deques

Deques is queue where we do deletion and insertion from both side. There are 2 type of queue, input restriction and output restriction deque. Input restriction mean deletion can happen at both side but insertion can only happen in one side and the output restriction is the opposite.

-        Priority queue

Priority queue is queue where we assign an priority to each element. Queue will procced the highest priority first, if there are same priority it will procced with First Come First Served basis.

4.      Deep first search and breadth first search
   a.      Deep First Search
              Deep first search (DFS) is algorithm for traversing in tree or graph. DFS start at the root
         of the tree and explore ass far as possible along each branch before backtracking.
         
   b.Breadth First Search
              Breadth first search (BFS) like DFS is also an algorithm for traversing or searching in a tree or graph. BFS start at the root of the tree and explore all neighboring nodes level per level until we find   the goal.
   

      The difference between both are only in the data structure concept that used. DFS use  stack while BFS use queue.