data-structure-frequently asked-questions
Data structure is representation of the logical relationship existing between individual elements of data. In other words, a data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.
Data structure affects the design of both structural & functional aspects of a program.
“Program = algorithm + Data Structure”
Linear: The data structures where the data elements are organised in some sequence is called linear data structure.
Here the various operations on a data structure are possible only in a sequence i.e. we cannot insert the element into any location of our choice.
E.g. A new element in a queue can come only at the end, not anywhere else.Examples of linear data structures are array, stacks, queue, and linked list.
Non-Linear: When the data elements are organised in some arbitrary function without any sequence, such data structures are called non-linear data structures.Examples of such type are trees, graphs.
Data structures are applied extensively in the following areas of computer science:
- Compiler Design, Operating System, Database Management System, Statistical analysis package, Numerical Analysis, Graphics, Artificial Intelligence, Simulation and so on..
- Difference between file structure and storage structure:
- Storage structure: It is the representation of the data structure in the computer memory.
- File structure: It is the representation of the storage structure in the auxiliary memory.
- DMA stands for Dynamic Memory Allocation, DMA allows us to allocate memory at run time.
- Generally variable allocates the memory at compile time, for example int a; here, a will allocate memory at compile time. But in case of Dynamic Memory Allocation, memory allocates at run time. Using the concept of DMA you can allocate exact memory for the variables.
- Here are the functions that are used to allocate or free the memory at run time:
- Malloc (): To allocate dynamic memory for one dimensional array that means contiguous memory allocation.
- Calloc (): To allocate dynamic memory for two dimensional array that means memory allocates in row and column manner.
- Realloc (): To re allocate dynamic memory.
- Freealloc ()To free dynamically allocated memory.
- A Compiler allocates the memory for the declared variable at compiler time, it is known as static memory allocation. The size is fixed when the program is created. It applies to global variables, file scope variables, and variables qualified with static defined inside functions.
- For example, if you declare a variable int num the memory for num will be declared at compile time. The variables which occupy memory statically are stored in stack and data segment.
- While in Dynamic Memory Allocation, memory allocates at run time. With this, you can now control the exact size and the lifetime of these memory locations. If you don’t free it, you’ll run into memory leaks, which may cause your application to crash, since at some point of time, system cannot allocate more memory.Malloc (), calloc () and realloc () functions are used to declare memory dynamically. Dynamic Memory Allocation is done in heap segment.
- Malloc() and calloc() both allocation of the memory is at the run time (dynamic), these functions are very useful to allocated dynamic memory, when you are dealing with a large amount of data or want to create memory according your need at run time.
- For example if you want to create memory for N number of toys then these functions are needed.
- Malloc() allocates the memory in single block according to given size, while calloc() allocates in multiple blocks according to given size.
int num=20;
int *ptr;
ptr=(int*)malloc(num*size of(int));- Here, Malloc() allocates the memory for 10 integers and returns the address, which is getting store in ptr.
int row=20,col=3;
int *ptr;
ptr=(int*)calloc(row,col*sizeof(int));- Here, calloc () allocates the 20 (row) memory blocks of 20 bytes (3*size of (int) and returns the address, which is getting store in ptr.
- Malloc () and calloc () both functions return void* (a void pointer), to use/capture the returned value in pointer variable we convert its type.
- Suppose we create memory for 10 integers then we have to convert it into int*.
int *ptr;
ptr=(int*)malloc(N*sizeof(int));- Here, malloc() will return void* and ptr variable is int* type, so we are converting it into (int*).
- Memory leak is really a panic, the insufficient memory/ memory resources leaks are known as memory leaks. Memory leak occurs when program does not manage the memory allocation correctly.
- Consider the following examples:
Example 1.
char* myFunction(){
char text[25];
Strcpy (text,"Hello, kodnest!");
return(test);
}
//returned pointer points to text which has gone out of scope;
//it might cause a Segmentation fault.Example 2.
char *ptr = (char*)malloc(3*size of(char));
free(ptr);
ptr[1] = 'k'; //invalid access through dangling pointer!
//It might cause a Segmentation fault.The preprocessor takes a look at your source code just before it goes off to the compiler, does a little formatting, and carries out any instructions you have given it.
Well, preprocessor instructions are called preprocessor directives, and they all start with a #.
#include, #define… and so on it modifies the code before compilation.
Macro is a preprocessor directive, which is used to replace text/tokens in the code at compile time. Compiler will replace a macro’s
#define DEFAULT_CITY “Bangalore”
DEFAULT macro will be changed (replaced) with “Bangalore” at the time of compilation.
It is a variable which is used to store the address of another variable.
Advantages of pointer
- Return multiple values from function
- Access any memory location
- Improves the performance
- Reduces the code
- Used for dynamic memory allocation
- Used in arrays, functions and structures
| Symbol | Name | Description |
| & | address of operator | Determines the address of a variable. |
| * | indirection operator | Accesses the value at the address. |
Example
#include
#include
void main(){
Clrscr ();
Int n=30;
Int *p; //declaration of pointer
p=&n; //stores the address of number variable
printf (“Address of n variable is %x \n”, &n);
printf (“Address of p variable is %x \n”,p);
printf(“Value of p variable is %d \n”,*p);
getch ();
}
Output
Address of n variable is fff4
Address of p variable is fff4
Value of p variable is 30Data type is a collection of values and a set of operations on these values. Abstract data type refer to the mathematical concept that define the data type.
It is a useful tool for specifying the logical properties of a data type.
ADT consists of two parts
1) Operation execution
2) value execution
Example:-The value definition for the ADT RATIONAL states that RATIONAL value consists of two integers, second doesn’t equal to zero.
RDBMS – Array (i.e. Array of structures)
Network data model – Graph
Hierarchical data model – Trees.
When new data is to be inserted into the data structure but there is no available space that means free storage list is empty this situation is called overflow.
When we want to delete data from a data structure that is empty this situation is called underflow.
i) Return address is retrieved.
ii) Function’s data area is freed.
iii) Branch is taken to the return address.
When a function is called
i) Arguments are passed.
ii) local variables are allocated and initialized.
iii) Transferring control to the function.
The definition which defines an object in terms of simpler cases of itself is called recursive definition.
A free Pool is a list consisting of unused memory cells which has its own pointer.
It is a technique in which the operating system periodically collects all the deleted space onto the free storage list.
It takes place when there is minimum amount of space left in storage list or when CPU is ideal.
The alternate method to this is to immediately reinsert the space into free storage list which is time consuming.
STACK:
i) Stack is an ordered collection of items.
ii) Stack is a dynamic object whose size is constantly changing as items are pushed and popped.
iii) Stack may contain different data types.
iv) Stack is declared as a structure containing an array to hold the element of the stack, and an integer to indicate the current stack top within the array.
ARRAY:
i) Array is an ordered collection of items.
ii) Array is a static object i.e. no of item is fixed and is assigned by the declaration of the array.
iii) It contains same data types.
iv) Array can be home of a stack i.e. array can be declared large enough for maximum size of the stack.
Inserting in array.
If we want to insert something into an array, first we have to make space by “scooting over” everything starting at the index we’re inserting into:
In the worst case we’re inserting into the 0th index in the array (prepending), so we have to “scoot over” everything in the array. That’s O (n) O (n) time.
Deleting in an array function with notations
Array elements are stored adjacent to each other. So when we remove an element, we have to fill in the gap—”scooting over” all the elements that were after it:
In the worst case we’re deleting the 0th item in the array, so we have to “scoot over” everything else in the array. That’s O (n) O (n) time.
Let us consider the following example, which uses an array of 3 integers −
#include
const int MAX = 3;
int main () {
int var[] = {15, 120, 200};
int i;
for (i = 0; i < MAX; i++) {
Printf (“Value of var [%d] = %d\n”, i, var[i]);
}
return 0;
}When the above code is compiled and executed, it produces the following result −
Value of var[0] = 15
Value of var[1] = 120
Value of var[2] = 200
Here we can also use an array of pointers to character to store a list of strings −
#include
Const int MAX = 4;
int main () {
char *names[] = {
“Akarsh”,
“Punith”,
“Prabhakar”,
“Amruth”
};
int i = 0;
for ( i = 0; i < MAX; i++) {
Printf (“Value of names [%d] = %s\n”, i, names[i] );
}
return 0;
}When the above code is compiled and executed, it produces the following result
Value of names[0] = Akarsh.
Value of names[1] = punith
Value of names[2] = prabhakar
Value of names[3] = amruth
A linked list is a linear collection of data elements, called nodes, where the linear order is given by pointers. Each node has two parts first part contain the information of the element second part contains the address of the next node in the list.
The disadvantages of array are:
i) Unlike linked list it is expensive to insert and delete elements in the array.
ii) One can’t double or triple the size of array as it occupies block of memory space.
In linked list
i) Each element in list contains a field, called a link or pointer which contains the address of the next element.
ii) Successive element’s need not occupy adjacent space in memory.
We cannot apply binary search algorithm to a sorted linked list, since there is no way of indexing the middle element in the list. This is the drawback in using linked list as a data structure.
i) The number of nodes needed can’t be predicted when the program is written.
ii) The number of nodes declared must remain allocated throughout its execution.
We can assign a memory address to an element of a pointer array by using the address operator, which is the ampersand (&), in an assignment statement such as employee [0] = &projects [2];
A multidimensional array can be useful to organize subgroups of data within an array. In addition to organizing data stored in elements of an array, a multidimensional array can store memory addresses of data in a pointer array and an array of pointers.
Multidimensional arrays are used to store information in a matrix form.
e.g; a flight timetable, schedule cannot be stored as a single dimensional array. One can use a 3-D array for storing height, width and length of each room on each floor of a building.
The symbol “*” tells the computer that you are declaring a pointer. Actually it depends on context.
In a statement like int *ptr; the ‘*’ tells that you are declaring a pointer.
In a statement like int i = *ptr; it tells that you want to assign value pointed to by ptr to variable i.
The symbol “*” is also called as Indirection Operator/ Dereferencing Operator.
Yes, a pointer is a variable and can be used as an element of a structure and as an attribute of a class in some programming languages such as C++, but not Java. However, the contents of a pointer is a memory address of another location of memory, which is usually the memory address of another variable, element of a structure, or attribute of a class.
There are two main parts, variable identifier and data type and the third type is optional which type qualifier like is signed/unsigned.
Memory is reserved using data type in the variable declaration. A programming language implementation has predefined sizes for its data types.
For example:
In C the declaration int i; will reserve 32 bits for variable i.
A pointer declaration reserves memory for the address or the pointer variable, but not for the data that it will point to. The memory for the data pointed by a pointer has to be allocated at runtime.
The memory reserved by the compiler for simple variables and for storing pointer address is allocated on the stack, while the memory allocated for pointer referenced data at runtime is allocated on the heap.
Sign of the number is the first bit of the storage allocated for that number. So you get one bit less for storing the number. For example if you are storing an 8-bit number, without sign, the range is 0-255. If you decide to store sign you get 7 bits for the number plus one bit for the sign. So the range is -128 to +127.
Precision refers the accuracy of the decimal portion of a value. Precision is the number of digits allowed after the decimal point.
NULL can be value for pointer type variables.
VOID is a type identifier which has not size.
NULL and void are not same. Example: void* ptr = NULL;
STACK follows LIFO. Thus the item that is first entered would be the last removed.
In array the items can be entered or removed in any order. Basically each member access is done using index. No strict order is to be followed here to remove a particular element.
Array may be multidimensional or one dimensional but stack should be one diamensional. But both are linear data structure.
pointer1 = pointer1->next;
pointer2 = pointer2->next;
if (pointer2)
pointer2=pointer2->next;
if (pointer1 == pointer2) {
Print (”circular”);
}
}
- According to Access strategies Linked list is a linear one.
- According to Storage Linked List is a Non-linear one.
The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.
A node class is a class that, relies on the base class for services and implementation, provides a wider interface to users than its base class, relies primarily on virtual functions in its public interface depends on all its direct and indirect base class can be understood only in the context of the base class can be used as base for further derivation can be used to create objects. A node class is a class that has added new services or functionality beyond the services inherited from its base class.
Unfortunately, the only way to search a linked list is with a linear search, because the only way a linked list’s members can be accessed is sequentially. Sometimes it is quicker to take the data from a linked list and store it in a different data structure so that searches can be more efficient.
DESCRIPTION TO LINKED LIST
In computer science, a linked data structure is a data structure which consists of a set of data records (nodes) linked together and organized by references (links or pointers).
In linked data structures, the links are usually treated as special data types that can only be dereferenced or compared for equality. Linked data structures are thus contrasted with arrays and other data structures that require performing arithmetic operations on pointers. This distinction holds even when the nodes are actually implemented as elements of a single array, and the references are actually array indices: as long as no arithmetic is done on those indices, the data structure is essentially a linked one.
Linked data structures include linked lists, search trees, expression trees, and many other widely used data structures. They are also key building blocks for many efficient algorithms, such as topological sort and set union-find.
Common Types of Linked Data Structures
Linked Lists
Basic Properties
- Objects, called nodes, are linked in a linear sequence
- A reference to the first node of the list is always kept. This is called the ‘head’ or ‘front’.
A linked list whose nodes contain two fields: an integer value and a link to the next node
Example in java compared to c
This is an example of the node class used to store integers in a Java implementation of a linked list.
Public class IntNode {public int value; public IntNode link; public IntNode (int v) {value = v;} }
Search Trees
Basic Properties
- Objects, called nodes, are stored in an ordered set
- In-order traversal provides an ascending readout of the data in the tree
- Sub trees of the tree are in themselves, trees.
- Advantages and disadvantages
Against Arrays - Compared to arrays, linked data structures allow more flexibility in organizing the data and in allocating space for it.
- With arrays, we must choose a size for our array once and for all, this can be a potential waste of memory.
- A linked data structure is built dynamically and never needs to be bigger than the programmer requires. It also requires no guessing in terms of how much space you must allocate when using a linked data structure. This is a feature that is key in saving wasted memory.
- The nodes of a linked data structure can also be moved individually to different locations without affecting the logical connections between them, unlike arrays. With due care, a process can add or delete nodes to one part of a data structure even while other processes are working on other parts.
- On the other hand, access to any particular node in a linked data structure requires following a chain of references that stored in it.
- If the structure has n nodes, and each node contains at most b links, there will be some nodes that cannot be reached in less than logb n steps. For many structures, some nodes may require worst case up to n−1 steps.
- In contrast, many array data structures allow access to any element with a constant number of operations, independent of the number of entries.
- General Disadvantages
Linked data structures also may also incur in substantial memory allocation overhead (if nodes are allocated individually) and frustrate memory paging and processor caching algorithms (since they are generally having very low locality of reference). - In some cases, linked data structures may also use more memory (for the link fields) than competing array structures. This is because linked data structures are not contiguous. Instances of data can be found all over in memory, unlike arrays.
- In some theoretical models of computation that enforce the constraints of linked structures, such as the pointer machine, many problems require more steps than in the unconstrained random access machine model.
Implementation of linked list in data structures
Implementation of this algorithm is also for singly linked list given below −
#include
#include
struct node {
int data;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//display the list
void printList() {
struct node *ptr = head;
printf(“\n[head] =>”);
//start from the beginning
while(ptr != NULL) {
printf(” %d =>”,ptr->data);
ptr = ptr->next;
}
printf(” [null]\n”);
}
//insert link at the first location
void insert(int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
//link->key = key;
link->data = data;
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
int main() {
insert(10);
insert(21);
insert(34);
insert(1);
insert(42);
insert(58);
printList();
return 0;
}
Output
Output of the program should be −
[head] => 58 => 42 => 1 => 34 => 21 => 10 => [null]#include <stdlib.h>
struct node {
int data;
struct node *next;
}
struct node *head = NULL;
struct node *current = NULL;
//Create Linked List
void insert(int data) {
// Allocate memory for new node;
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data; link->next = NULL;
// If head is empty, create new list
if(head==NULL) {
head = link; return;
}
current = head; // move to the end of the list
while(current->next!=NULL) current = current->next;
// Insert link at the end of the list
current->next = link;
}
void find_data(int item) {
int pos = 0; if(head==NULL) {
printf(“Linked List not declared”);
return;
}
current = head;
while(current->next!=NULL) {
if(current->data == item) {
printf(“%d found at position %d\n”, item, pos);
return;
}
current = current->next; pos++;
}
printf(“%d it does not exist in the list”, item);
}
int main() {
insert(12);
insert(20);
insert(32);
insert(1);
insert(44);
insert(54);
find_data(44);
find_data(40);
return 0;
}
Output of the program should be −
44 found at position 4 40 does not exist in the list#include
struct node {
int data;
struct node *next;
};
struct node *even = NULL;
struct node *odd = NULL;
struct node *list = NULL;
//Create Linked List
void insert(int data) {
// Allocate memory for new node;
struct node *link = (struct node*) malloc(sizeof(struct node));
struct node *current;
link->data = data;
link->next = NULL;
if(data%2 == 0) {
if(even == NULL) {
even = link;
return;
} else {
current = even;
while(current->next != NULL)
current = current->next;
// Insert link at the end of the list
current->next = link;
} } else {
if(odd == NULL) {
odd = link;
return;
} else {
current = odd;
while(current->next!=NULL) current = current->next;
// Insert link at the end of the list
current->next = link;
} } }
void display(struct node *head) {
struct node *ptr = head;
printf(“[head] =>”);
while(ptr != NULL) {
printf(” %d =>”,ptr->data); ptr = ptr->next;
}
printf(” [null]\n”);
}
void combine() {
struct node *link; list = even;
link = list;
while(link->next!= NULL) {
link = link->next;
}
link->next = odd;
}
int main() {
int i;
for(i = 1; i <= 10; i++) insert(i);
printf(“Even : “);
display(even);
printf(“Odd : “);
display(odd);
combine();
printf(“Combined List :\n”);
display(list);
return 0;
}
Output of the program should be −
Even : [head] => 2 => 4 => 6 => 8 => 10 => [null]
Odd : [head] => 1 => 3 => 5 => 7 => 9 => [null]
Combined List : [head] => 2 => 4 => 6 => 8 => 10 => 1 => 3 => 5 => 7 => 9 => [null]
#include
struct node {
int data;
struct node *next;
};
struct node *even = NULL;
struct node *odd = NULL;
struct node *list = NULL;
//Create Linked List
void insert(int data) {
// Allocate memory for new node;
struct node *link = (struct node*) malloc(sizeof(struct node));
struct node *current;
link->data = data;
link->next = NULL;
if(list == NULL) {
list = link;
return;
}
current = list;
while(current->next!=NULL)
current = current->next;
// Insert link at the end of the list
current->next = link;
}
void display(struct node *head) {
struct node *ptr = head;
printf(“[head] =>”);
//start from the beginning
while(ptr != NULL) {
printf(” %d =>”,ptr->data);
ptr = ptr->next;
}
printf(” [null]\n”);
}
void split_list() {
// Allocate memory for new node;
struct node *link;
struct node *current;
while(list != NULL) {
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = list->data;
link->next = NULL;
if(list->data%2 == 0) {
if(even == NULL) {
even = link;
list = list->next;
continue;
} else {
current = even;
while(current->next != NULL)
current = current->next;
// Insert link at the end of the list
current->next = link;
}
list = list->next;
} else {
if(odd == NULL) {
odd = link;
list = list->next;
continue;
} else {
current = odd;
while(current->next!=NULL)
current = current->next;
// Insert link at the end of the list
current->next = link;
}
list = list->next;
}
}
}
int main() {
int i;
for(i = 1; i <= 10; i++)
insert(i);
printf(“Complete list: \n”);
display(list);
split_list();
printf(“\nOdd : “);
display(odd);
printf(“Even : “);
display(even);
return 0;
}
Output
Output of the program should be −
Complete list:
[head] => 1 => 2 => 3 => 4 => 5 => 6 => 7 => 8 => 9 => 10 => [null]
Odd : [head] => 1 => 3 => 5 => 7 => 9 => [null]
Even: [head] => 2 => 4 => 6 => 8 => 10 => [null]Implementation
Implementation of this algorithm is given below −
#include
#include
Struct node {
int data;
Struct node *next;
};
Struct node *head = NULL;
Struct node *current = NULL;
//insert link at the first location
void insert(int data) {
// Allocate memory for new node;
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
link->next = NULL;
// If head is empty, create new list
if(head==NULL) {
head = link;
head->next = link;
return;
}
current = head;
// move to the end of the list
while(current->next != head)
current = current->next;
// Insert link at the end of the list
current->next = link;
// Link the last node back to head
link->next = head;
}
//display the list
void printList() {
struct node *ptr = head;
printf(“\n[head] =>”);
//start from the beginning
while(ptr->next != head) {
printf(” %d =>”,ptr->data);
ptr = ptr->next;
}
printf(” %d =>”,ptr->data);
printf(” [head]\n”);
}
int main() {
insert(15);
insert(25);
insert(30);
insert(1);
insert(48);
insert(58);
printList();
return 0;
}
Output
Output of the program should be −
[head] => 15 => 25 => 30 => 1 => 48 => 58 => [head]Implementation of this algorithm is given below −
#include
#include
struct node {
int data;
struct node *prev;
struct node *next;
};
struct node *head = NULL;
struct node *last = NULL;
struct node *current = NULL;
//Create Linked List
void insert(int data) {
// Allocate memory for new node;
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
link->prev = NULL;
link->next = NULL;
// If head is empty, create new list
if(head==NULL) {
head = link;
return;
}
current = head;
// move to the end of the list
while(current->next!=NULL)
current = current->next;
// Insert link at the end of the list
current->next = link;
last = link;
link->prev = current;
}
//display the list
void printList() {
struct node *ptr = head;
printf(“\n[head] <=>”);
//start from the beginning
while(ptr->next != NULL) {
printf(” %d <=>”,ptr->data);
ptr = ptr->next;
}
printf(” %d <=>”,ptr->data);
printf(” [head]\n”);
}
int main() {
insert(12);
insert(22);
insert(32);
insert(1);
insert(46);
insert(58);
printList();
return 0;
}
Output
Output of the program should be −
[head] <=> 12 <=> 22 <=> 32 <=> 1 <=> 46 <=> 58 <=> [head] Yes there is a set of implicit arguments that contain information necessary for the function to execute and return correctly. One of them is return address which is stored within the function’s data area, at the time of returning to calling program the address is retrieved and the function branches to that location.
Parenthesis is not required because the order of the operators in the postfix /prefix expressions determines the actual order of operations in evaluating the expression.
Stack. Because of its LIFO (Last in First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.
Polish and Reverse Polish notations.
Prefix Notation is as given below
^ – * +ABC – DE + FG
The pop () member method removes the value from the top of a stack, which is then returned by the pop () member method to the statement that calls the pop () member method.
Push () method, Push is the direction that data is being added to the stack. Push () member method places a value onto the top of a stack.
Stack is an ordered collection of elements in which insertions and deletions are restricted to one end. The end from which elements are added and/or removed is referred to as top of the stack. Stacks are also referred as piles, push-down lists and last-in-first-out (LIFO) lists.
The basic operations that can be performed on a stack are
- Push operation.
- Pop operation.
- Peek operation.
- Empty check.
- Fully occupied check.
The different ways of representing expressions are as follows
- Infix Notation.
- Prefix Notation.
- Postfix Notation.
- It is the mathematical way of representing the expression.
- It is easier to see visually which operation is done from first to last.
- Any formula can be expressed without parenthesis.
- It is very convenient for evaluating formulas on computer with stacks.
- Postfix expression doesn’t has the operator precedence.
- Postfix is slightly easier to evaluate.
- It reflects the order in which operations are performed.
- You need to worry about the left and right associativity.
Fully parenthesize the expression starting from left to right. During parenthesizing, the operators having higher precedence are first parenthesized.
Move the operators one by one to their right, such that each operator replaces their corresponding right parenthesis.
The part of the expression, which has been converted into postfix is to be treated as single operand.
Once the expression is converted into postfix form, remove all parenthesis.
- Fully parenthesize the expression starting from left to right. During parenthesizing, the operators having higher precedence are first parenthesized.
- Move the operators one by one to their left, such that each operator replaces their corresponding left parenthesis.
- The part of the expression, which has been converted into prefix is to be treated as single operand.
- Once the expression is converted into prefix form, remove all parenthesis.
The difference between stacks and linked lists is that insertions and deletions may occur anywhere in a linked list, but only at the top of the stack.
An overview of stack in data structure
A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc.
A real-world stack allows operations at one end only. For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.
Stack Representation
The following diagram depicts a stack and its operations −
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which makes it a fixed size stack implementation.
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations −
- Push () − Pushing (storing) an element on the stack.
- Pop () − Removing (accessing) an element from the stack.
When data is pushed onto stack.
To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks −
- Peek () − get the top data element of the stack, without removing it.
- IsFull () − check if the stack is full.
- Is Empty () − check if the stack is empty.
At all times, we maintain a pointer to the last pushed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.
First we should learn about procedures to support stack functions −
Peek ()
Algorithm of peek () function −
begin procedure peek
Return stack[top]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return stack[top];
}
Is full ()
Algorithm of isfull() function
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementation of is full () function in C programming language
Example
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
Is empty ()
Algorithm of is empty () function
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedureImplementation of is empty () function in C programming language is slightly different. We initialize top at -1, as the index in array starts from 0. So we check if the top is below zero or -1 to determine if the stack is empty. Here’s the code −
Example
bool isempty() {
if(top == -1)
return true;
else
return false;
}Push Operation
The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps −
- S 1 − Checks if the stack is full.
- S 2 − If the stack is full, produces an error and exit.
- S 3 − If the stack is not full, increments top to point next empty space.
- S 4 − Adds data element to the stack location, where top is pointing.
- S 5 − Returns success.
If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.
Algorithm for PUSH Operation
The other way to represent a graph is by using an adjacency list. An adjacency list is an array A of separate lists. Each element of the array Ai is a list, which contains all the vertices that are adjacent to vertex i.
For a weighted graph, the weight or cost of the edge is stored along with the vertex in the list using pairs. In an undirected graph, if vertex j is in list Ai then vertex i will be in list Aj.
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure−
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf(“Could not insert data, Stack is full.\n”);
}
}Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop () operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop () actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
- S1 − Checks if the stack is empty.
- S2 − If the stack is empty, produces an error and exit.
- S 3 − If the stack is not empty, accesses the data element at which top is pointing.
- S 4 − Decreases the value of top by 1.
- S 5 − Returns success.
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top – 1
return data
end procedureImplementation of this algorithm in C, is as follows
Example
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top – 1;
return data;
} else {
printf(“Could not retrieve data, Stack is empty.\n”);
}
}The way to write arithmetic expression is known as a notation. An arithmetic expression can be written in three different but equivalent notations, i.e., without changing the essence or output of an expression. These notations are −
- Infix Notation
- Prefix (Polish) Notation
- Postfix (Reverse-Polish) Notation
These notations are named as how they use operator in expression. We shall learn the same here in this chapter.
We write the expression in infix notation, e.g. a – b + c, where operators are used in-between operands. It is easy for us humans to read, write, and speak in infix notation but the same does not go well with computing devices. An algorithm to process infix notation could be difficult and costly in terms of time and space consumption.
In this notation, operator is prefixed to operands, i.e. operator is written ahead of operands. For example, +ab. This is equivalent to its infix notation a + b. Prefix notation is also known as Polish Notation.
This notation style is known as Reversed Polish Notation. In this notation style, the operator is postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is equivalent to its infix notation a + b.
The following table briefly tries to show the difference in all three notations −
| Si.num | Infix Notations | Prefix Notations | Postfix Notations |
| 1 | a + b | + a b | a b + |
| 2 | (a + b) ∗ c | ∗ + a b c | a b + c ∗ |
| 3 | a ∗ (b + c) | ∗ a + b c | a b c + ∗ |
| 4 | a / b + c / d | + / a b / c d | a b / c d / + |
| 5 | (a + b) ∗ (c + d) | ∗ + a b + c d | a b + c d + ∗ |
| 6 | ((a + b) ∗ c) – d | – ∗ + a b c d | a b + c ∗ d – |
It is not a very efficient way to design an algorithm or program to parse infix notations. Instead, these infix notations are first converted into either postfix or prefix notations and then computed.
To parse any arithmetic expression, we need to take care of operator precedence and associativity also.
Precedence
When an operand is in between two different operators, which operator will take the operand first, is decided by the precedence of an operator over others. For example
As multiplication operation has precedence over addition, b * c will be evaluated first. A table of operator precedence is provided later.
Associativity
Associativity describes the rule where operators with the same precedence appear in an expression. For example, in expression a + b − c, both + and – have the same precedence, then which part of the expression will be evaluated first, is determined by associativity of those operators. Here, both + and − are left associative, so the expression will be evaluated as (a + b) − c.
Precedence and associativity determines the order of evaluation of an expression. Following is an operator precedence and associativity table (highest to lowest) −
| Si.No. | Operator | Precedence | Associativity |
| 1 | Exponentiation ^ | Highest | Right Associative |
| 2 | Addition (+)& subtraction(-) | Lowest | Left Associative |
| 3 | Multiplication ( ∗ ) & Division ( / ) | Second Highest | Left Associative |
The above table shows the default behavior of operators. At any point of time in expression evaluation, the order can be altered by using parenthesis. For example −
In a + b*c, the expression part b*c will be evaluated first, with multiplication as precedence over addition. We here use parenthesis for a + b to be evaluated first, like (a + b)*c.
We shall now look at the algorithm on how to evaluate postfix notation −
S 1 − scan the expression from left to right
S 2 − if it is an operand push it to stack
S 3 − if it is an operator pull operand from stack and perform operation
S 4 − store the output of step 3, back to stack
S 5 − scan the expression until all operands are consumed
S 6 − pop the stack and perform operation
Conversion of Infix Expressions to Prefix and Postfix
Here is a more complex expression: (A + B) * C – (D – E) * (F + G).
Converting a Complex Expression to Prefix and Postfix Notations
Converting between these notations
The most straightforward method is to start by inserting all the implicit brackets that show the order of evaluation e.g.:
| Infix | Postfix | Prefix |
| ( (A * B) + (C / D) ) | ( (A B *) (C D /) +) | (+ (* A B) (/ C D) ) |
| ((A * (B + C) ) / D) | ( (A (B C +) *) D /) | (/ (* A (+ B C) ) D) |
| (A * (B + (C / D) ) ) | (A (B (C D /) +) *) | (* A (+ B (/ C D) ) ) |
You can convert directly between these bracketed forms simply by moving the operator within the brackets e.g. (X + Y) or (X Y +) or (+ X Y). Repeat this for all the operators in an expression, and finally remove any superfluous brackets.
You can use a similar trick to convert to and from parse trees – each bracketed triplet of an operator and its two operands (or sub-expressions) corresponds to a node of the tree. The corresponding parse trees are:
/ *
+ / \ / \
/ \ * D A +
/ \ / \ / \
* / A + B /
/ \ / \ / \ / \
A B C D B C C D
((A*B) + (C/D)) ((A*(B+C))/D) (A*(B+ (C/D)))Fully parenthesize the expression starting from left to right. During parenthesizing, the operators having higher precedence are first parenthesized.
Move the operators one by one to their right, such that each operator replaces their corresponding right parenthesis.
The part of the expression, which has been converted into postfix is to be treated as single operand.
Once the expression is converted into postfix form, remove all parenthesis.
Fully parenthesize the expression starting from left to right. During parenthesizing, the operators having higher precedence are first parenthesized.
Move the operators one by one to their left, such that each operator replaces their corresponding left parenthesis.
The part of the expression, which has been converted into prefix is to be treated as single operand.
Once the expression is converted into prefix form, remove all parenthesis.
#define SIZE 100 (Size of Stack)
#include
#include
char s[SIZE];
int top=-1; ( Global declarations )
Push (char elem)
{ (Function for PUSH operation)
s[++top] =elem;
}
char pop()
{ (Function for POP operation)
return(s[top–]);
}
int pr(char elem)
{ (Function for precedence)
Switch (elem)
{
Case ‘#’: return 0;
case ‘)’: return 1;
case ‘+’:
case ‘-‘: return 2;
case ‘*’:
case ‘/’: return 3;
}
}
main()
{ ( Main Program )
char infx[40],prfx[40],ch,elem;
int i=0,k=0;
printf(“\n\nRead the Infix Expression ? “);
scanf(“%s”,infx);
push(‘#’);
strrev(infx);
while( (ch=infx[i++]) != ‘\0‘)
{
if( ch == ‘)’) push(ch);
else
if(isalnum(ch)) prfx[k++]=ch;
else
if( ch == ‘(‘)
{
while( s[top] != ‘)’)
prfx[k++]=pop();
elem=pop(); /* Remove ) */
}
else
{ /* Operator */
while( pr(s[top]) >= pr(ch) )
prfx[k++]=pop();
push(ch);
}
}
while( s[top] != ‘#’) ( Pop from stack till empty)
prfx[k++]=pop();
prfx[k]=’\0‘; (Make prfx as valid string )
strrev(prfx);
strrev(infx);
printf(“\n\nGiven Infix Expression: %s Prefix Expression: %s\n“,infx,prfx);
}#include
Void push (char item[],int *top,char s[][20]) {
*top=*top+1;
strcpy(s[*top],item);
}
void *pop(int *top,char s[][20]) {
char *item;
item=s[*top];
*top=*top-1;
return item;
}
void pre_post(char prefix[],char postfix[]) {
char s[20][20];
int top,i;
char symbol,temp[2];
char *op1,*op2;
top=-1;
strrev(prefix);
for(i=0;i<strlen(prefix);i++) {
symbol=prefix[i];
temp[0]=symbol;
temp[1]=’\0′;
switch (symbol) {
case ‘+’: case ‘-‘: case ‘*’: case ‘/’: case ‘^’:
op1=pop(&top,s);
op2=pop(&top,s);
strcpy(postfix,op1);
strcat(postfix,op2);
strcat(postfix,temp);
push(postfix,&top,s);
break;
default: push(temp,&top,s);
} } }
void main() {
char prefix[20];
char postfix[20];
printf(“\n\n Enter the prefix expression \n\n”);
scanf(“%s”,prefix); pre_post(prefix,postfix);
printf(“\n\n The postfix expression is %s \n\n”,postfix);
}
#include
char stack[40];
int top=-1;
void post(char infix[]);
void push(char);
char pop();
void main() {
char infix[25]; printf("\enter the Infix expression = ");
gets(infix);
post(infix);
getch();
}
void push(char symb) {
if(top>=49) {
printf("\nSTACK OVERFLOW");
getch();
return;
} else {
top=top+1;
stack[top]=symb; } }
char pop() {
char item;
if(top==-1) {
printf("\stack is empty");
getch();
return(0);
} else {
item=stack[top];
top--;
} return(item);
}
int preced(char ch) {
if(ch==47) {
return(5);
} else
if(ch==42) {
return(4);
} else if(ch==43) {
return(3);
} else return(2);
}
void post(char infix[]) {
int l;
int index=0,
pos=0;
char symbol,temp;
char postfix[40];
l=strlen(infix); push('#');
while(index<l) {
symbol=infix[index];
switch(symbol) {
case '(': push(symbol); break; case ')': temp=pop();
while(temp!='(') {
postfix[pos]=temp;
pos++; temp=pop();
}
break;
case '+': case '-': case '*': case '/': case '^':
while(preced(stack[top])>=preced(symbol)) {
temp=pop();
postfix[pos]=temp;
pos++;
}
push(symbol);
break;
default: postfix[pos++]=symbol;
break;
}
index++;
}
while(top>0) {
temp=pop();
postfix[pos++]=temp;
}
postfix[pos++]='\0';
puts(postfix);
return;
}
OUTPUT Enter the infix expression= x+y*c
Postfix expression is = xyz*+ QUEUES IN DATA STRUCTURES.A Queue is a sequential organization of data. A queue is a first in first out type of data structure. An element is inserted at the last position and an element is always taken out from the first position.
The priority queue is a data structure in which the intrinsic ordering of the elements like numeric or alphabetic
Determines the result of its basic operation. It is of two types:
i) Ascending priority queue- Here smallest item can be removed (insertion is arbitrary).
ii) Descending priority queue- Here largest item can be removed and insertion is arbitrary.
i) Fixed amount of storage remains allocated to the data structure even if it contains less element.
ii) No more than fixed amount of storage is allocated causing overflow.
i) A node in a linked list info and next field occupies more storage than a corresponding element in an array.
ii) Additional time spent in managing the available list.
Deque (Double-Ended Queue) is another form of a queue in which insertions and deletions are made at both the front and rear ends of the queue. There are two variations of a deque, namely, input restricted deque and output restricted deque. The input restricted deque allows insertion at one end (it can be either front or rear) only. The output restricted deque allows deletion at one end it can be either front or rear only.
Enqueue is the process that places data at the back of the queue.
Data stored in a queue is actually stored in an array. Two indexes, front and end will be used to identify the start and end of the queue.
When an element is removed front will be incremented by 1. In case it reaches past the last index available it will be reset to 0. Then it will be checked with end. If it is greater than end queue is empty.
When an element is added end will be incremented by 1. In case it reaches past the last index available it will be reset to 0. After incrementing it will be checked with front. If they are equal queue is full.
Mainly the following four basic operations are performed on queue:
- Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
- Dequeue: Removes an item from the queue.
- Front: Get the front item from queue.
- Rear: Get the last item from queue.
QUEUE is a simple data structure, which has FIFO (First in First Out) property in which Items are removed in the same order as they are entered.
QUEUE has two pointer FRONT and REAR, Item can be pushed by REAR End and can be removed by FRONT End.
#include
#define MAX 10
int QUEUE[MAX],front=-1,rear=-1;
/** function : insert_in_Q(),
to push an item into queue.
**/
void insert_in_Q(int queue[],int ele)
{
if(rear==-1)
{
front=rear=0;
queue[rear]=ele;
}
else if(rear==MAX-1)
{
printf(“\nQUEUE is full.\n”);
return;
}
else
{
rear++;
queue[rear]=ele;
}
printf(“\nItem inserted..”);
}
/** function : display_Q(),
to display queue elements
**/
void display_Q(int queue[])
{ int i;
if(rear==-1) { printf(“\nQUEUE is Empty.”); return; }
for(i=front;i<=rear;i++)
{ printf(“%d,”,queue[i]); }
}
/** function : remove_from_Q(),
to remove (pop) an item from queue.
**/
void remove_from_Q(int queue[])
{
int ele;
if(front==-1)
{
printf(“QUEUE is Empty.”);
return;
}
else if(front==rear)
{
ele=queue[front];
front=rear=-1;
}
else
{
ele=queue[front];
front++;
}
printf(“\nItem removed : %d.”,ele);
}
int main()
{
int ele,choice;
while(1)
{
//clrscr();
printf(“\nQUEUE Elements are :”);
display_Q(QUEUE);
printf(“\n\nEnter choice (1:Insert,2:Display,3:Remove,0:Exit):”);
scanf(“%d”,&choice);
switch(choice)
{
case 0:
exit(1);
break;
case 1:
printf(“Enter an element to insert:”);
scanf(“%d”,&ele);
insert_in_Q(QUEUE,ele);
break;
case 2:
display_Q(QUEUE);
break;
case 3:
remove_from_Q(QUEUE);
break;
default:
printf(“\nInvalid choice\n”);
break;
}
} //end of while(1)
return 0;
}begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language
Example
int peek() {
return queue[front];
}
isfull()As we are using single dimension array to implement queue, we just check for the rear pointer to reach at MAXSIZE to determine that the queue is full. In case we maintain the queue in a circular linked-list, the algorithm will differ. Algorithm of isfull() function −
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(rear == MAXSIZE – 1)
return true;
else
return false;
}
isempty()Algorithm of isempty() function −
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence empty.
Here’s the C programming code −
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
- S 1 − Check if the queue is full.
- S 2 − If the queue is full, produce overflow error and exit.
- S 3 − If the queue is not full, increment rear pointer to point the next empty space.
- S 4 − Add data element to the queue location, where the rear is pointing.
- S 5 − return success.
Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen situations.
Algorithm for enqueue operation
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Implementation of enqueue () in C programming language −
Example
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedureAccessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation −
- S 1 − Check if the queue is empty.
- S 2 − If the queue is empty, produce underflow error and exit.
- S3 − If the queue is not empty, access the data where front is pointing.
- S4 − Increment front pointer to point to the next available data element.
- S 5 − Return success.
Algorithm for dequeue operation
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedureExample
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}A priority queue is an abstract data type in computer programming that supports the following three operations:
- Insert With Priority: add an element to the queue with an associated priority
- Get Next: remove the element from the queue that has the highest priority, and return it (also known as “Pop Element(Off)”, or “Get Minimum”)
- Peek at Next (optional): look at the element with highest priority without removing it for an analogy, see the Implementation section below.
Simple implementations
There are a variety of simple, usually inefficient, ways to implement a priority queue. They provide an analogy to help one understand what a priority queue is:
- Sorted list implementation: Like a checkout line at the supermarket, but where important people get to “cut” in front of less important people. (O(log(n)) insertion time (can binary search for insertion position) if implemented using arrays, O(n) insertion time if implemented using linked lists; O(1) get-next time)
- Unsorted list implementation: Keep a list of elements as the queue. To add an element, append it to the end. To get the next element, search through all elements for the one with the highest priority. (O(1) insertion time, O(n) get-next due to search)
These implementations are usually inefficient, though can be good depending on the workload (for example, if one does very few GetNext operations, the unsorted list approach may work well). In practice, priority queues blend these two approaches, so any operation takes roughly O(log(n)) time or less.
Usual implementation
To get better performance, priority queues typically use a heap as their backbone, giving O (log n) performance for inserts and removals. Alternatively, if a self-balancing binary search tree is used, all three operations take O(log n) time; this is a popular solution where one already has access to these data structures, such as through third-party or standard libraries.
Effect of different data structures
The designer of the priority queue should take into account what sort of access pattern the priority queue will be subject to, and what computational resources are most important to the designer. The designer can then use various specialized types of heaps: There are a number of specialized heap data structures that either supply additional operations or outperform the above approaches.
The binary heap uses O (log n) time for both operations, but allows peeking at the element of highest priority without removing it in constant time. Binomial heaps add several more operations, but require O (log n) time for peeking. Fibonacci heaps can insert elements, peek at the maximum priority element, and increase an element’s priority in amortized constant time (deletions are still O(log n)). While relying on a heap is a common way to implement priority queues, for integer data faster implementations exist (this can even apply to datatypes that have finite range, such as floats)
We’re going to implement Queue using array in this article. There is few more operations supported by queue which are following.
- Peek − get the element at front of the queue.
- isFull − check if queue is full.
- isEmpty − check if queue is empty.
Insert / Enqueue Operation
Whenever an element is inserted into queue, priority queue inserts the item according to its order. Here we’re assuming that data with high value has low priority.
void insert(int data){
int i = 0;
if(!isFull()){
// if queue is empty, insert the data
if(itemCount == 0){
intArray[itemCount++] = data;
}else{
// start from the right end of the queue
for(i = itemCount – 1; i >= 0; i– ){
// if data is larger, shift existing item to right end
if(data > intArray[i]){
intArray[i+1] = intArray[i];
}else{
break;
}
}
// insert the data
intArray[i+1] = data;
itemCount++;
}
}
}Remove / Dequeue Operation
Whenever an element is to be removed from queue, queue get the element using item count. Once element is removed. Item count is reduced by one.
int removeData(){
return intArray[–itemCount];
}Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.
Example − a function calling itself.
int function(int val) {
if( val< 1)
Return;
Function (Val – 1);
printf (“%d “,val);
}Example − a function that calls another function which in turn calls it again.
int function1(int val1) {
if (val1 < 1)
return;
function2(val1 – 1);
printf(“%d “,val1);
}
int function2(int val2) {
function1 (val2);
}Properties
A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have to follow
- Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.
- Progressive approach − the recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.
Implementation
Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee.
This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function.
This activation record keeps the information about local variables, formal parameters, return address and all information passed to the caller function.
Analysis of Recursion
One may argue why to use recursion, as the same task can be done with iteration. The first reason is, recursion makes a program more readable and because of latest enhanced CPU systems, recursion is more efficient than iterations.
Time Complexity
In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο (1), hence the (n) number of times a recursive call is made makes the recursive function Ο (n).
Space Complexity
Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation record each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration.
It is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted −
These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.
Rules to follow
The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −
- Only one disk can be moved among the towers at any given time.
- Only the “top” disk can be removed.
- No large disk can sit over a small disk.
Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.
Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 – 1 = 7 steps.
Algorithm
To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.
If we have 2 disks −
- First, we move the smaller (top) disk to aux peg.
- Then, we move the larger (bottom) disk to destination peg.
- And finally, we move the smaller disk from aux to destination peg.
So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.
Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.
The steps to follow are −
S 1 − Move n-1 disks from source to aux
S 2 − Move nth disk from source to dest
S 3 − Move n-1 disks from aux to dest
A recursive algorithm for Tower of Hanoi can be driven as follows −
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk – 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk – 1, aux, dest, source) // Step 3
END IF
END Procedure
STOPFibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.
Fibonacci series satisfies the following conditions −
Fn = Fn-1 + Fn-2Hence, a Fibonacci series can look like this −
F8 = 0 1 1 2 3 5 8 13or, this −
F8 = 1 1 2 3 5 8 13 21For illustration purpose, Fibonacci of F8 is displayed as −
Fibonacci Iterative Algorithm
First we try to draft the iterative algorithm for Fibonacci series.
Procedure Fibonacci(n)
declare f0, f1, fib, loop
set f0 to 0
set f1 to 1
display f0, f1
for loop ← 1 to n
fib ← f0 + f1
f0 ← f1
f1 ← fib
display fib
end for
end procedureFibonacci Recursive Algorithm
Let us learn how to create a recursive algorithm Fibonacci series. The base criteria of recursion.
START
Procedure Fibonacci(n)
declare f0, f1, fib, loop
set f0 to 0
set f1 to 1
display f0, f1
for loop ← 1 to n
fib ← f0 + f1
f0 ← f1
f1 ← fib
display fib
end for
ENDIntroduction to trees, binary tree traversal, and operations on trees in data structures.
The manipulation of Arithmetic expression, Symbol Table construction & Syntax analysis.
Sparse matrix, Index generation.
If the ‘pivotal value’ (or the ‘Height factor’) is greater than 1 or less than –1.
In general: There are 2n-1 nodes in a full binary tree. By the method of elimination:
Full binary trees contain odd number of nodes. So there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13 nodes you can form a complete binary tree but not a full binary tree. So the correct answer is 15.
B+ tree. Because in B+ tree, all the data is stored only in leaf nodes, that makes searching easier. This corresponds to the records that shall be stored in leaf node
A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.
No! Minimal spanning tree assures that the total weight of the tree is kept at its minimum. But it doesn’t mean that the distance between any two nodes involved in the minimal-spanning tree is minimum.
1014 – For example, consider a tree with 3 nodes (n=3), it will have the maximum combination of 5 different (ie, 23 – 3 =? 5) trees
Knowledge of tree traversals is very important in order to completely understand Binary Trees. Though the recursive implementation of tree traversals, can be coded very neatly but recursion is generally not preferred. Excessive recursive function calls may cause memory to run out of stack space.
Iterative tree traversals can be coded easily, using a _ visited _ flag. This has been sufficiently explained at but this requires us to change the structure of the tree, and we would not want that. Here we will attempt to develop iterative traversals, without modifying the structure.
Understanding the below given iterative traversals can be a little tricky so the best way to understand them is to work them out on a piece of paper. Use this sample binary tree and follow the steps of the below given codes.
The in order traversal requires that we print the leftmost node first and the right most node at the end. So basically for each node we need to go as far as down and left as possible and then we need to come back and go right. Steps of algorithm are:
> 1. Start with the node equals root
> 2. Store the node in the stack and visit it’s left child.
> 3. Repeat step 2 while node is not NULL, if it’s NULL then pop it’s parent (i.e. the last node in stack) and print it.
> 4. Now move to node’s right child and repeat step 1
> 5. Repeat whole procedure while node is not NULL and stack is not empty
Inorder(Tree *p)
{
stack < Tree* > S;
do
{
while (p!=NULL)
{
// store a node in the stack and visit it’s left child
S.push(p);
p=p->left;
}
// If there are nodes in the stack to which we can move up
// then pop it
if (!S.empty())
{
p=S.top();
S.pop();
// print the nodes value
cout << p->ele << “-“; // vistit the right child now p=p->right;
}
// while the stack is not empty or there is a valid node
}while(!S.empty()||p!=NULL);
}
Pre order is very similar to in order traversal. The way of accessing all the nodes remains the same except the position where we print the node. Now the node is printed/visited before visiting the children of the nodes. Steps are very similar to in-order
> 1. Start with node equal to root node
> 2. Store the node in the stack, print it and visit it’s left child.
> 3. Repeat step 2 while node is not NULL, if it’s NULL then pop it’s parent (i.e. the last node in stack).
> 4. Now move to node’s right child and repeat step 2
> 5. Repeat whole procedure while node is not NULL and stack is not empty
Preorder(Tree *p)
{
stack < Tree* > S;
do
{
while (p!=NULL)
{
// storea node in stack and print it’s value
S.push(p);
cout << p->ele << “-“; // visit the left child p = p->left;
}
// visit the right child
if (!S.empty())
{
p=S.top();
S.pop();
p = p->right;
}
} while(!S.empty()||p!=NULL);
}Post order traversal is the trickiest one, out of all the three traversals. However post order traversal is important to understand because of the following 2 use cases
Tree deletion: In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node is deleted when both of its left and right sub-trees are deleted. This can be done using post-order traversal only.
The problem with post-order traversal is that in the previous two cases when a node was popped of from the stack, then it was finally removed and was not accessed again. However in case of post-order the node needs to be accessed from the stack twice, and is deleted only in the second access.
First time we find a node, we push it on to the stack, the second time we examine it from the stack to go to it’s right child and then finally after visiting both the right sub-tree and the left-subtree we remove the node from the stack. So a node stays in the stack as long as it’s sub-trees have not been visited.
Since, a node has to be visited (printed in the trivial case) only after it’s left and right child have been visited, we print a node’s value after we have visited the left child followed by the right child. The property that is exploited in this implementation is that the the parent node will always be visited just after visiting it’s right child.
After visiting the left child, when we come to the parent node in the stack if the right child is NULL, then we can straight away print the node, but if it’s not NULL then we have to check whether the previous node which was printed is it’s right child. If it’s the right child then we can visit the current node, otherwise the right child has not been visited and we must proceed with the right child.
Hence in this traversal, we have to use a previous pointer, only then will we able to correctly traverse the node. Otherwise we do not know when the right child has been visited or not.
1. Start with the root node.
2. Store the node in the stack, and visit it’s left child.
3. Repeat step 1 while node is not NULL, if it’s NULL:
* Pick the top most node from the stack.
* If it’s right child is NULL, then print the node and set prev pointer to this node
* If it’s not NULL, check whether the right child is equal to prev pointer, if it is then print the node, else repeat step 1 with the right child
* In this step, if you print the node then current is made equal to NULL and this sub-loop is repeated untill stack is not empty and current is NULL
4. Since the root node remains in the stack till the end, the terminating condition is untill stack is empty
Postorder(Tree *p)
{
stack < Tree* > S;
Tree *prev = NULL;
do
{
while (p!=NULL)
{
S.push(p);
p = p->left;
}
while(p == NULL && !S.empty())
{
p = S.top();
if(p->right == NULL || p->right == prev)
{
cout << p->ele << “-“; S.pop(); prev = p; p = NULL; } else p = p->right;
}
}while (! S.empty());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 (β)
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.
Max Heap Construction Algorithm
We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is similar but we go for min values instead of max values.
We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree.
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.
Note − In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.
Let’s understand Max Heap construction by an animated illustration. We consider the same input sample that we used earlier.
Max Heap Deletion Algorithm
Let us derive an algorithm to delete from max heap. Deletion in Max (or Min) Heap always happens at the root to remove the Maximum (or minimum) value.
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.
OPTIMAL SEARCH BINARY TREE
A search algorithm is optimal if no other search algorithm uses less time or space or expands fewer nodes, both with a guarantee of solution quality. The optimal search algorithm would be one that picks the correct node at each choice.
Optimal Cost Binary Search Trees
Search time of an element in a BST is O(n), whereas in a Balanced-BST search time is O(log n).
Optimal Binary search has enormous applications.
Some of these are like: Huffman’s code, Graph theory, ASCII string search, Natural language processing, State reduction.
A binary search tree is a tree with data (keys) at internal nodes with the following property:
- The key at any internal node is greater than all keys in the left hand subtree and less than all keys in the right hand subtree.
Example: consider a Tree 1 of nodes (where A<B<C<D<E<F<G<H) :
For a given set of keys (and ordering) we can find many possible binary search trees.
- Example: consider a tree 2 of nodes (where A<B<C<D<E<F<G<H) :
- Example consider a Tree 3 of nodes (where A<B<C<D<E<F<G<H) :
We can use the following useful search technique
datatype INTREE = EMPTY
Node of (INTREE * int * INTREE)
fun IsInTree (k,Empty) = false
IsInTree (k,Node(left,entry,right)) =
(k=entry) orelse
if (k<entry) then IsInTree (k,left) else (* k>entry *)
IsInTree (k,right).Data sorting is any process that involves arranging the data into some meaningful order to make it easier to understand, analyze or visualize. Data is typically sorted based on actual values, counts or percentages, in either ascending or descending order, but can also be sorted based on the variable value labels.
- Bubble Sort.
- Insertion Sort.
- Selection Sort.
- Quick Sort.
- Merge Sort.
- Heap Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Insertion sort is a sorting algorithm in which the elements are transferred one at a time to the right position. In other words, an insertion sort helps in building the final sorted list, one item at a time, with the movement of higher-ranked elements.
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.
Quick sort is one of the most famous sorting algorithms based on divide and conquers strategy which results in an O (n log n) complexity. So, the algorithm starts by picking a single item which is called pivot and moving all smaller items before it, while all greater elements in the later portion of the list.
The complexity of merge sort is O (nlogn) and NOT O (logn). Merge sort is a divide and conquer algorithm. Think of it in terms of 3 steps – The divide step computes the midpoint of each of the sub-arrays. Each of this step just takes O (1) time
Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list. Idea: Divide the unsorted list into sublists, each containing element.
Heap sort is one of the sorting algorithms used to arrange a list of elements in order. Heap sort algorithm uses one of the tree concepts called Heap Tree. In this sorting algorithm, we use Max Heap to arrange list of elements in Descending order and Min Heap to arrange list elements in ascending order.
A highly efficient sorting algorithm based on the insertion sort algorithm is known as Shell Sort. The large shifts as that of insertion sort are avoided, if in case, the smaller value is far right and which has to be moved to far left.
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph Graphs are used to represent networks.
- Undirected Graphs. In an undirected graph, the order of the vertices in the pairs in the Edge set doesn’t matter. …
- Directed Graphs. …
- Vertex labeled Graphs. …
- Cyclic Graphs. …
- Edge labeled Graphs. …
- Weighted Graphs. …
- Directed Acyclic Graphs. …
- Disconnected Graphs.
- Nodes: These are the most important components in any graph. Nodes are entities whose relationships are expressed using edges.
- Edges: Edges are the components that are used to represent the relationships between various nodes in a graph.
Directed graph. (Data structure) Definition: A graph whose edges are ordered pairs of vertices. That is, each edge can be followed from one vertex to another vertex. Formal Definition: A graph G is a pair (V, E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {(u, v)
In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph.
Nodes: These are the most important components in any graph. Nodes are entities whose relationships are expressed using edges. If a graph comprises 2 nodes A and B and an undirected edge between them, then it expresses a bi-directional relationship between the nodes and edge.
Types of nodes
- Root node: The root node is the ancestor of all other nodes in a graph. It does not have any ancestor. Each graph consists of exactly one root node. Generally, you must start traversing a graph from the root node.
- Leaf nodes: In a graph, leaf nodes represent the nodes that do not have any successors. These nodes only have ancestor nodes. They can have any number of incoming edges but they will not have any outgoing edges.
An adjacency matrix is a matrix which describes a graph by representing which vertices are adjacent to which other vertices.
If G, is a graph of order n, then its adjacency matrix is a square matrix of order n, where each row and column corresponds to a vertex of G.
The element aij of such a matrix specifies the number of edges from vertex i to vertex j.
An adjacency matrix for a simple graph and a loop-digraph is a logical matrix, that is, one whose elements are all either 0 or 1.
An adjacency matrix for an undirected graph is symmetrical about the main diagonal.
This is because if vertex i is adjacent to vertex j, then j is adjacent to i.
An adjacency matrix for a weighted graph or network contains the weights of the edges.
include using namespace std;
bool A[10][10];
void initialize() {
for(int i = 0;i < 10;++i)
for(int j = 0;j < 10;++j)
A[i][j] = false;
}
int main() {
int x, y, nodes, edges; initialize(); //Since there is no edge initially cin >> nodes;
//Number of nodes cin >> edges;
//Number of edges
for(int i = 0;i < edges;++i) {
cin >> x >> y; A[x][y] = true; //Mark the edges from vertex x to vertex y
}
if(A[3][4] == true) cout << “There is an edge between 3 and 4” << endl;
else cout << “There is no edge between 3 and 4” << endl;
if(A[2][3] == true)
cout << “There is an edge between 2 and 3” << endl;
else cout << “There is no edge between 2 and 3” << endl; return 0;
}
Output There is an edge between 3 and 4. There is no edge between 2 and 3.
Responses