What is Stack
A stack is a ADT which has LIFO i.e. last in first out behavior. Which means the element which is enetered at the later would be accessed at first. A Stack has two basic operations which are called push and pop which are used to store and retrieve data from the stack.

Required Functions
Though only push and pop are the necessary function but lets define the following function for the stack implementation in C using LinkList.

A Heap is a partially sorted binary tree. Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If α has child node β then −

key(α) ≥ key(β)

Why use a heap? A heap can be thought of as a priority queue, the most important node will always be at the top, and when removed, its replacement will be the most important. This can be useful when coding algorithms that require certain things to processed in a complete order, but when you don't want to perform a full sort or need to know anything about the rest of the nodes. For instance, a well-known algorithm for finding the shortest distance between nodes in a graph, Dijkstra's Algorithm, can be optimized by using a priority queue. Heaps can also be used to sort data.

As the value of parent is greater than that of child, this property generates Max Heap. Based on this criteria, a heap can be of two types −

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap − Where the value of the root node is less than or equal to either of its children.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.

Both trees are constructed using the same input and order of arrival.

Heap Construction Algorithm

Step 1 − Create a new node at the end of heap. Step 2 − Assign new value to the node. Step 3 − Compare the value of this child node with its parent. Step 4 − If value of parent is less than child, then swap them. Step 5 − Repeat step 3 & 4 until Heap property holds.

Heap Deletion Algorithm

Step 1 − Remove root node. Step 2 − Move the last element of last level to root. Step 3 − Compare the value of this child node with its parent. Step 4 − If value of parent is less than child, then swap them. Step 5 − Repeat step 3 & 4 until Heap property holds.

Given below a C Program to Implement a Heap & provide Insertion & Deletion Operation:-

#include <stdio.h>

int array[100], n;

main()

{

int choice, num;

n = 0; /*Represents number of nodes in the heap*/

while(1)

{

printf("1.Insert the element \n");

printf("2.Display all elements \n");

printf("3.Quit \n");

printf("Enter your choice : ");

scanf("%d", &choice);

switch(choice)

{

case 1:

printf("Enter the element to be inserted to the list : ");

scanf("%d", &num);

insert(num, n);

n = n + 1;

break;

case 2:

display();

break;

case 3:

exit(0);

default:

printf("Invalid choice \n");

} /*End of switch */

} /*End of while */

} /*End of main()*/

display()

{

int i;

if (n == 0)

{

printf("Heap is empty \n");

return;

}

for (i = 0; i < n; i++)

{

printf("%d ", array[i]);

printf("\n");

}

} /*End of display()*/

insert(int num, int location)

{

int parentnode;

while (location > 0)

{

parentnode =(location - 1)/2;

if (num <= array[parentnode])

{

array[location] = num;

return;

}

array[location] = array[parentnode];

location = parentnode;

} /*End of while*/

array[0] = num; /*assign number to the root node */

Linked Listis a linear data structure and it is very common data structure which consists of group of nodes in a sequence which is divided in two parts. Each node consists of its own data and the address of the next node and forms a chain. Linked Lists are used to create trees and graphs.

Following are the important points to be considered:

Linked List contains an link element called first.

Each Link carries a data field(s) and a Link Field called next.

Each Link is linked with its next link using its next link.

Last Link carries a Link as null to mark the end of the list.

Types of Linked List

Simple Linked List

Doubly Linked List

Circular Linked List

Basic Operations

Insertion − add an element at the beginning of the list.

Deletion − delete an element at the beginning of the list.

Display − displaying complete list.

Search − search an element using given key.

Delete − delete an element using given key.

Advantages of Linked Lists

They are a dynamic in nature which allocates the memory when required.

Insertion and deletion operations can be easily implemented.

Stacks and queues can be easily executed.

Linked List reduces the access time.

Disadvantages of Linked Lists

The memory is wasted as pointers require extra memory for storage.

No element can be accessed randomly; it has to access each node sequentially.

Reverse Traversing is difficult in linked list.

Insertion Operation

Insertion is a three step process −

Create a new Link with provided data.

Point New Link to old First Link.

Point First Link to this New Link.

code snippet for insertion is given below:

void insertFirst(int key, int data)

{ struct node *link = (struct node*) malloc(sizeof(struct node)); link->key = key; link->data = data; link->next = head; //point it to old first node head = link; //point first to new first node }

Deletion Operation

Deletion is a two step process −

Get the Link pointed by First Link as Temp Link.

Point First Link to Temp Link's Next Link.

The code snippet for deletion is given below:

struct node* deleteFirst()

{ struct node *tempLink = head; head = head->next; //mark next to first link as first return tempLink; //return the deleted link }

Navigation Operation

Navigation is a recursive step process and is basis of many operations like search, delete etc. −

Get the Link pointed by First Link as Current Link.

Check if Current Link is not null and display it.

Point Current Link to Next Link of Current Link and move to above step.

The code snippet for Navigation is given below:

void printList()

{ struct node *ptr = head; printf("\n[ "); while(ptr != NULL) //start from the beginning

A binary search tree (BST) binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right sub-tree.

Many a times binary tree and binary search tree looks same but they are not: a binary tree is a tree where each node has up to two leaves. In a binary tree, a left child node and a right child node contain values which can be either greater, less, or equal to parent node. But in Binary Search Tree each left child contains the value less then the parent node and each right child contains the value greater then Parent.