# DataStructures Tutorials

## DataStructures Tutorials Overview

Welcome to DataStructures Tutorials. The objective of these tutorials is to gain understanding of DataStructures. In these tutorials, we will cover topics such as Stacks, Sorting, Queues, Trees etc.

In addition to DataStructures Tutorials we will cover common interview questions and issues of DataStructures.

### Index

**DataStructures**

In computer science, a DataStructures is a particular way and organizing data in a computer so that it can be use efficiently.

A data structure is an arrangement of data in a computer memory or even disk storage.

An example of several common data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables.

Different kinds of DataStructures are suited to different kinds of applications and some are highly specialized to specific basis.

For example, 3-trees are particular well suited for implementation of databases, while compiler implementation usually use hash tables to look up identifiers.

DataStructures are used in almost every program or software system.

Specific DataStructures are essential ingredients of many efficient algorithms and make possible the management of huge amounts of data, such as large databases and internet indexing services.

The following are the two types of the DataStructures

Linear DataStructures.

Non-linear DataStructures.

## Linear DataStructures

The linear DataStructures holds /stores the data elements in the form of a linear list (i.e. in sequential)

Arrays, stacks, queues and linked lists are called linear DataStructures.

## Non-linear DataStructures

The non-linear DataStructures holds/stores the data elements in the form hierarchy by establishing some relationship between the data elements.

Trees and graphs are the nonlinear DataStructures.

## INFIX TO POST FIX CONVERSIONS

In general, simple architecture expression can be represented in three ways: infix, prefix and postfix.

- Consider the expression A+B. Here A and B are operands and + is binary
- The three notations can be shown as :

A+B infix

+AB prefix(or polish)

AB+ postfix(pr suffix or reverse polish)

- In infix notation, the operator symbol is between the two operands.
- In prefix, the operator symbol is placed before is its two operands.
- In postfix, the operator symbol is placed before is its two operands.
- In postfix, the operator symbol is placed after its two operands(i.e the operator follows both operands)

The infix operands – precedence is as follows

- parenthesis
- multiplication * , Division
- Addition +, Subtraction –

**Algorithm** : In to post (Q,P)

Suppose ‘Q’ is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression p.

- push” (“ onto STACK, and add”)” to the end of Q
- Scan a from left to right repeat steps 3 to 6 for each element of Q until the STACK is empty.
- If an operand is encountered , add it to p
- If a left parenthesis is encountered, push it into STACK.
- If an operator x is encountered, then :
- Repeatedly pop from STACK and add to p each operator con the top of STACK, which has the same precedence as or higher precedence then X.
- Add x to stack [End of if structure]
- If a rights parenthesis is encountered, then :
- Repeatedly pop from STACK and add to p each operator ( on the top STACK) until a left parenthesis is encountered.
- Remove the left parenthesis. [ Do not add the left parenthesis to p]

[End of IF structure]

[End if steo2 loop]

- Exit

**Example**** :**

**Q: **A+(B*C-(D/E*F)*G)*H)

Symbol Scanned | STACK | postfix(p) |

- A
| C | A |

- +
| C+ | A |

- C
| C+C | A |

- B
| C+C | AB |

- *
| C+C* | AB |

- C
| C+C* | ABC |

- -
| C+C- | ABC* |

- (
| C+C-C | ABC*D |

- 0
| C+C-C | ABC*D |

- /
| C+C-C/ | ABC*D |

- E
| C+C-C/ | ABC*DE |

- *
| C+C-C | ABC*DE/ |

- F
| C+C-C* | ABC*DE/F |

- )
| C+C- | ABC*DE/F* |

- *
| C+C- | ABC*DE/F* |

- G
| C+C-* | ABC*DE/F*G |

- )
| C+C. | ABC*DE/F*G*- |

- *
| C+* | ABC*DE/F*G*- |

- H
| C+* | ABC*DE/F*G*-H |

- )
| EMPTY | ABC*DE/F*G*-H*+ |

#### Program:

### Program to convert infix to postfix expressions

# include<stdio.h>

#include<conio.h>

#include<ctype.h>

#include<stdib.h>

char infix[20];

char pastfix[20];

char stack[20];

int TOP=-1;

void Get Expr()

{

int len;

printf(“Enter an infix expression \n”);

gets(infix);

len=strlen(infix);

infix[len]=’)’;

TOP=TOP+1;

stack[TOP]=’c’;

}

void conver ()

{

int i,j;

for (i=0;j=0;Top!=-1;i++)

{

if(is alpha(infix[i]))

{

Post fix[j]=infix[i];

j=j+1;

}

else

{

switch(infix[i])

{

case’c’: Top=Top+1;

stack[Top]=’c’;

break;

Case ‘+’ :

Case ‘-‘:

While(stack[Top]=’+’||stack[Top]==’I’

stack[top]==’*’ || stack[Top]==’/’)

{

Post fix[j]=Stock[Top];

j=j+1;

Top=Top-1;

}

Top=Top+1;

stack[Top]=infix[i];

break;

case ‘*’

case’/’ :

while(stock[Top]==’*’ || Stack[Top]==’/’_

{

postfix[j]=stack[Top];

j=j+1;

Top=Top-1;

}

Top=Top+1;

stack[Top]=infix[i];

break;

case’)’:

while(cstack[Top]!=’(‘ ) && (stock[TOP] == ‘+’|| stack[Top] == ‘-‘ || stack[Top]==’*’ || stack[Top]==’/’))

{

Pastfix[j]=stack[Top];

j=j+1;

Top=Top-1;

}

Top=TOP-1;

}/* switch end */

} /* else end */

}/* for end */

post fix[j]=’\o’;

printf(“Expression in postfix is %s \n”, postfix);

}

void main()

{

clrscr();

Get expr();

convert ();

getch();

}

**Output****:** Enter an expression A+(B*C - CDIE*F)