A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Fig::A stack containing items or elements

Stack as ADT

A stack of elements of type T is a finite sequence of elements of T together with the operations

• CreateEmptyStack(S): Create or make stack S be an empty stack
• Push(S, x): Insert x at one end of the stack, called its top
• Top(S): If stack S is not empty; then retrieve the element at its top
• Pop(S): If stack S is not empty; then delete the element at its top
•  IsFull(S): Determine if S is full or not. Return true if S is full stack; return false otherwise
• IsEmpty(S): Determine if S is empty or not. Return true if S is an empty stack; return false otherwise.

Thus by using a stack we can perform above operations thus a stack acts as an ADT.

Primitive operations of stack

The following operations can be performed on a stack:

1. PUSH operation: The push operation is used to add (or push or insert) elements in a Stack.

ü  When we add an item to a stack, we say that we push it onto the stack

ü  The last item put into the stack is at the top

2. POP operation: The pop operation is used to remove or delete the top element from the stack.

  üwe remove an item, we say that we pop item from the stack.

 üWhen an item popped, it is always the top item which is removed.

The PUSH and the POP operations are the basic or primitive operations on a stack. Some others operations are:

• CreateEmptyStack operation: This operation is used to create an empty stack.
• IsFull operation: The isfull operation is used to check whether the stack is full or not ( i.e. stack overflow)
•  IsEmpty operation: The isempty operation is used to check whether the stack is empty or not. (i. e. stack underflow)
• Top operations: This operation returns the current item at the top of the stack, it doesn’t remove it

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node
• All keys in the right sub-tree of the root are greater than the key in the root node
•  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

        14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Properties of BST:

• Nodes of the tree are represented in a parent-child relationship
• Each parent node can have zero child nodes or a maximum of two subnodes or subtrees on the left and right sides.
• Every sub-tree, also known as a binary search tree, has sub-branches on the right and left of themselves.
• All the nodes are linked with key-value pairs.
• The keys of the nodes present on the left subtree are smaller than the keys of their parent node
• Similarly, The left subtree nodes' keys have lesser values than their parent node's keys.

Recursive Algorithm for Constructing BST

void insert(struct bnode *root, int item)

{

    if(root=NULL)

    {

        root=(struct bnode*)malloc (sizeof(struct bnode));

        root->left=root->right=NULL;

        root->info=item;

    }

    else

    {

        if(item<root->info)

             root->left=insert(root->left, item);

        else

             root->right=insert(root->right, item);

    }

}

Recursive Algorithm to traverse BST using preorder traverse method

void preorder(struct bnode *root)

{

    if(root!=NULL)

    {

    printf(“%c”, root->info);

    preorder(root->left);

    preorder(root->right);

    }

}

Sorting is the technique to arranging the items of list in any specific order which may be ascending or descending order.

Sort can be classified in two types:

1. Internal sort: This method uses only the primary memory during sorting process. All data items are held in main memory and no secondary memory is required in this sorting process. If all the data that is to be sorted can be accommodated at a time in memory is called internal sorting. For e.g. selection sort, insertion sort etc.

Limitation: They can only process relatively small lists due to memory constrains.

2. External sort: Sorting large amount of data requires external or secondary memory. This process uses external memory such as HDD, to store the data which is not fit into the main memory. So primary memory holds the currently being sorted data only. All external sorts are based on process of merging. Different parts of data are sorted separately and merging together. For e.g. merge sort

Quick Sort

In quick sort one of the array element is chosen as a pivot element. Then large array is partitioned into two sub arrays one on left side of pivot which holds values smaller than the pivot element and another array on right side of pivot which holds values greater than pivot the pivot value. This procedure of choosing pivot and partition the list is applied recursively until sub-arrays consisting of only one element.

Algorithm:

QuickSort(A, l, r)

{

    if(l<r)

    {

        p = Partition(A,l,r);

        QuickSort(A,l,p-1);

        QuickSort(A,p+1,r);

    }

}

Partition(A, l, r)

{

    x =l; y =r ; p = A[l];

    while(x<y)

    {

       do {

                x++;

         }while(A[x] <= p);

    do {

                y--;

         } while(A[y] >=p);

    if(x<y)

        swap(A[x],A[y]);

}

A[l] = A[y];

A[y] = p;

return y;     //return position of pivot

}

Merge Sort

The basic concept of merge sort is divides the list into two smaller sub-lists of approximately equal size. Recursively repeat this procedure till only one element is left in the sub-list. After this, various sorted sub-lists are merged to form sorted parent list. This process goes on recursively till the original sorted list arrived.

Algorithm:

MergeSort(A, l, r)

{

    If ( l < r)

    { 

         m = (l + r)/2

        MergeSort(A, l, m) 

        MergeSort(A, m + 1, r)

        Merge(A, l, m+1, r)

}

}

Merge(A, B, l, m, r)

{

    x=l, y=m;

    k=l;

    while(x<m && y<r)

    {

        if(A[x] < A[y])

        {

            B[k]= A[x];

            k++;

            x++;

        }

        else

        {

            B[k] = A[y];

            k++;

            y++;

        }

A Fibonacci sequence is the sequence of integer in which each element in the sequence is the sum of the two previous elements.

Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.

       Fn = Fn-1 + Fn-2

E.g.

F8 = 0,  1,  1,  2,  3,   8,  13  or, F8 = 1,  1,  2,  3,  5,  8,  13,  21

Recursive algorithm to get Fibonacci sequence:

1. START

2. Input the non-negative integer ‘n’

3. If (n==o || n==1)

        return n;

    else

        return fib(n-1)+fib(n-2);

4. Print, nth Fibonacci number

5. END

Given postfix expression:

AB + C*DC – -FG + $

Expression tree for given expression is constructed below:

Singly Linked List

Singly linked list is a sequence of elements in which every element has link to its next element in the sequence. In any single linked list, the individual element is called as "Node". Every "Node" contains two fields, data and next. The data field is used to store actual value of that node and next field is used to store the address of the next node in the sequence.

In this type of linked list, only one link in each node, where the link points to the next node in the list. The link of last node has a NULL pointer.

The graphical representation of a node in a single linked list is as follows...

The following example is a singly linked list that contains three elements 12, 99, & 37.

Doubly Linked List (DLL)

Doubly linked list is a sequence of elements in which every element has links to its previous element and next element in the sequence.

In double linked list, every node has link to its previous node and next node. So, we can traverse forward by using next field and can traverse backward by using previous field. Every node in a double linked list contains three fields and they are shown in the following figure...

Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is used to store the address of the next node in the sequence and 'data' field is used to store the actual value of that node.

Example:

Circular Linked List (CLL)

Circular linked list is a sequence of elements in which every element has link to its next element in the sequence and the last element has a link to the first element in the sequence.

Example:

Circular list has no end.

In a circular linked list there are two methods to know if a node is the first node or not.

• Either a external pointer, list, points the first node or
• A header node is placed as the first node of the circular list.

Doubly Circular Linked List (DCLL)

A circular doubly linked list is one which has the successor and predecessor pointer in circular manner. It is a doubly linked list where the next link of last node points to the first node and previous link of first node points to last node of the list. E.g.

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

Graphical representation of a circular queue is as follows.

Initialization of Circular queue:

rear=front=MAXSIZE-1

Operations of Circular Queue

1. enQueue(value): This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.

Algorithms for inserting an element in a circular queue:

This algorithm is assume that rear and front are initially set to MAZSIZE-1.

1. if (front==(rear+1)%MAXSIZE)

print Queue is full and exit

    else

rear=(rear+1)%MAXSIZE; [increment rear by 1]

2. cqueue[rear]=item;

3. end

2. deQueue(): This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position.

Algorithms for deleting an element from a circular queue:

This algorithm is assume that rear and front are initially set to MAZSIZE-1.

1. if (rear==front) [checking empty condition]

print Queue is empty and exit

2. front=(front+1)%MAXSIZE; [increment front by 1]

3. item=cqueue[front];

4. return item;

5. end.

Collision resolution techniques

If collision occurs then it should be handled by applying some techniques. Such a technique is called collision handling technique. Collision resolution techniques are:

    1.Chaining

    2.Open addressing (linear probing)

    3.Quadratic probing

    4.Double hashing

    5.Rehashing

Quadratic Probing:

Quadratic probing operates by taking the original hash value and adding successive values of an arbitrary quadratic polynomial to the starting value. This method uses following formula:

where m can be table size or any prime number

For e.g. If we have to insert following elements in the hash table with table size 10:

37, 90, 55, 22, 11, 17

37 % 10 = 7 

90 % 10 = 0 

55 % 10 = 5 

22 % 10 = 2 

11 % 10 = 1

Now if we want to place 17 a collision will occur as 17%10 = 7 and  bucket 7 has already an element 37. Hence we will apply  quadratic probing to insert this record in the hash table.

Consider i = 0 then

(17 + 0 ² ) % 10 = 7

(17 + 1² ) % 10 = 8, when i =1

The bucket 8 is empty hence we will place the element at index 8.

Double Hashing

Double hashing is technique in which a second hash function is applied to the key when a collision occurs. By applying the second hash function we will get the number of positions from the point of collision to insert. There are two important rules to be followed for the second function:

it must never evaluate to zero.

must make sure that all cells can be probed.

The formula to be used for double hashing is

where M is a prime number smaller than the size of the table.

Consider the following elements to be placed in the hash table of size 10

37, 90, 45, 22, 17

Initially insert the elements using the formula for H1(key).

Insert 37, 90, 45, 22 

H1(37) = 37 % 10 = 7

H1(90) = 90 % 10 = 0

H1(45) = 45 % 10 = 5

H1(22) = 22 % 10 = 2

H1(49) = 49 % 10 = 9

Now if 17 to be inserted then

Here M is prime number smaller than the size of the table. Prime number smaller than table size 10 is 7

Hence M = 7

That means we have to insert the element 17 at 4 places from 37. In short we have to take 4 jumps. Therefore the 17 will be placed at index 1.

 MST (Minimum Cost Spanning Tree)

A spanning tree is a subset of Graph G, which has all the vertices of G with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.

In a weighted graph, a minimum spanning tree (MST) is a spanning tree that has minimum weight than all other spanning trees of the same graph.

There are three different algorithms to construct the minimum spanning tree:

• Prim’s algorithm: Grows the tree in stages. Selects an edge with lowest cost that can be added to the tree without forming cycle.
• Kruskal’s algorithm: In each stage select the edge in non-decreasing order of cost.
• Sollin’s algorithm: Select several edges at each stage.

The Shortest Path

Consider a weighted graph G. The length of a path in a weighted graph is the sum of the weights of the edges of this path and the shortest path between two vertices is the minimum length of the path.

The Dijkstra’s Algorithm finds the shortest path between two vertices in weighted graph.

Merits of Contiguous List / array

• It is used to represent multiple data items of same type by using only single name.

• It can be used to implement other data structures like linked lists, stacks, queues, trees, graphs etc.

• 2D arrays are used to represent matrices.

• Implementation of list using array is easier as compared other implementation.

Demerits of Contiguous List / array

• The size of the array is fixed. Most often this size is specified at compile time. This makes the programmers to allocate arrays, which seems "large enough" than required.

• Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.

• Deleting an element from an array is not possible. Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are weak.

• Generally array's allocates the memory for all its elements in one block whereas linked lists use an entirely different strategy. Linked lists allocate memory for each element separately and only when necessary.

Merits of Linked List

1. Linked lists are dynamic data structures. i.e., they can grow or shrink during the execution of a program.

2. Linked lists have efficient memory utilization. Here, memory is not preallocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.

3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.

4. Many complex applications can be easily carried out with linked lists.

5. There is no need to define an initial size for a Linked list.

6. Linked List reduces the access time.

Demerits of Linked List

1. They use more memory than arrays because of the storage used by their pointers.

2. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.

3. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.

4. Nodes are stored in-contiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.

A priority queue is a collection of elements such that each element has been assigned a priority and the order in which elements are deleted and processed comes from the following rules:.

• An element of higher priority is processed before any element of lower priority.
• If two elements has same priority then they are processed according to the order in which they were added to the queue.

There are two types of priority queues they are as follows...

1. Max Priority Queue
2. Min Priority Queue

1. Max Priority Queue: In max priority queue, elements are inserted in the order in which they arrive the queue and always maximum value is removed first from the queue. For example assume that we insert in order 8, 3, 2, 5 and they are removed in the order 8, 5, 3, 2.

2. Min Priority Queue: Min Priority Queue is similar to max priority queue except removing maximum element first, we remove minimum element first in min priority queue.

Priority Queues can be implemented using common data structures like arrays, linked-lists, heaps and binary trees.