Data structures !!

   What are data structures?? Its not as complex they seem to be when you hear of them.Data structure is some structure where you can store the data in your computer.How should we select a data structure for a particular data??There is no fixed rule for this it is completely based on the application you are using.Some of the data structures are Stack,Queues,lists,trees,etc..And every data type  is also a data structure because it provides you a structure to save data.
CLASS,ARRAYS are also dat structures to be precise because it again provides a structure to save the data you want in the memory.

What is a stack??
  A stack is a data structure which follows the LIFO.The item which is pushed last comes out first ly then the other items can be popped out.This stack will come to use in many instances .All the instances where the various data structure will come to use for storing in a memory will be discussed nw!

Let me tell you about call stack..
When a function executes the order in which the control flow jumps must be kept track through some data structure.This is taken care by the stack...Let me tell you,The memory in the computer is totally divided into the following sections:
-->A code section
-->Global variable section
-->Stack
-->Heap
-->B.S.S
-->Data Section

The code section contains the executable code.All the global variables are stored in the global section.The B.SS contains all the uninitialised variables.The data section contains all the static and constant variables that are declared in the code.Now what is the stack and heap used for??
Consider this problem:

000:main()
       {
            int i,j;
            abc(e,r);
010: }
100:  abc(int a,int p)
            {
            int x,y,z;
            cde()
110:            }
300:  cde(int h)
        {
           int h1,j1
         }
Initially when the main function executes,the return address is pushed on to the stack ,then the parameters are also pushed into the stack.

the above three sections together forms the section fr fn main().Then the next fn abc() is called.Again its return address,parameters and the local parameters are pushed into the stack,This fn in turn calls the cde() fn adn its paremeters r pushed abv the abc() fn.So once cde() gets over that respective section is popped out,and so in abc() you cannot access the variable h1 which is local to cde().There is a pointer SP,the Stack pointer which always points to the top of the stack.Then you may have a ques if 

--->in the func main the variables are pushed one after the another.so x will go to the bottom nd y at the top..then if v do x=8; in that case shud v pop out y and then do the operation??Nooo.We ve another pointer BP stack base pointer which dynamically moves over the stack and assigns values.

Heap:In case  you dynamically create and delete memory then this gets allocated in the heap area.The heap memory needs to be de-allocated once it's work is over,but the stack gets dealloc automatically.Stack is the method of implementation.To allocate to the stack a particular memory may be taken from the heap and can be implemented as a stack.

Man m=new Man();

will allocate place in the heap.

Other data that may be stored in the stack...

-->state of the respective function

-->If it is a long arithmetic operation then the operators may also be pushed to the stack..

Heap in computer science point to 2 diff things ,one is the memory which is explained above and the other is the heap DATA STRUCTURE..Heap data structure is used in priority queues.There are 2 kinds,minheap and the maxheap which is also used in sorting with an effective complexity.In maxheap always the maximum element will be at the root of the heap.

RECURSION used in the stack!!

When functions are calling itself it is called as recursion.

Consider 

f(int x)

{
if(x==0) return 1
else x*f(x-1)
}

The fn f(5) keeps callin itself and pushes it into the stack as shown,which will start computing in the reverse order once it returns 1 at x==0...1*2*3*4*5

Now some of the data structures..
Queue:First in first out.Used in the processor queues in the system and in real time ant queue in which we wait is an example.
Linked List:They are of non contigious memory locations.A memory  block is created for each chunk of data and a pointer is constructed pointing it to the next memory location,thus forming a chain of data.Any item can be included in the middle or in the end or the begining.A list of routers in a network where any router can be included or deleted.
-->circular linked list
-->doubly linked list
-->Circularly Doubly/Singly linked list.

Other Data Structures.
Trees-Kinds are BST,splay tree,AVL treeetc.
Its structure has pointers for al branches and one for the data.
Trie:Used in Dictionary.
Graphs:Networking mostly.They can also be trees with cycles.



- Sourcebits University
Cloud Computing
www.sourcebits.com