# Introduction to Classic Data Structures - Part 1

A way of organizing data in order to use it efficiently is called a data structure. Read this article for a brief introduction of some classic data structures like linked lists, stacks and their applications.

Data must be organized in a way such that it can be used efficiently. Such a way is called a data structure. Some of the classic data structures are arrays, linked lists, stack ADT, queue ADT, trees, graphs, tables etc,. The general operations on data structures are insertion of an element, deletion of an element, displaying the data structure, sorting the elements etc,.

An array gives an index to every element. For example, an array 'a' of size 'n' has the elements a[0], a[1], … a[n-1]. If an element is to be inserted (deleted) to (from) an array, indexes of all the elements next to it must be changed.

A circular single linked list is a single linked list in which the last element has a pointer to the first element. A circular double linked list is a double linked list in which the first element has pointers to the last element, second element and the last element has pointers to the last before element, first element.

### Technical Terms

Node : Every element in a linked list is called a node.
NEXT : The pointer to the next node in a linked list.
PREV : The pointer to the previous node in a double/circular double linked list.

### Applications

The major application of linked lists is polynomial representation. For example, consider a polynomial ax2+bx+c=0. Considering coefficients and exponents, it can be represented as (a,2) (b,1) (c,0). A linked list containing two blocks for data i.e. one for coefficient and one for exponent can be used to represent polynomials and operations on linked lists like insertion, deletion, display etc,. can be used to manipulate polynomials. In addition, linked lists can also be used in sparse matrix manipulation and in dynamic storage management. Refer these articles for more on linear linked lists, circular single linked lists and circular double linked lists.

## Stacks

Stack is a data structure which follows First In Last Out Principle (FILO). Insertion operation and deletion operation can be done only at one end of a stack. Consider dinner plates put one on one for washing. It is a real life example of a stack. The plate which is put first in the line (bottom) for washing will come out last from the line (top) after washing. A stack and its end at which insertion/deletion are performed:

### Technical Terms

TOP : The pointer to the end of the stack at which insertion/deletion is done.
PUSH : To insert an element (at TOP) into the stack.
POP : To delete an element (at TOP) from the stack.

### Applications

The major application of stacks is to evaluate expressions. Generally, expressions are of 3 types. They are:
Prefix Expression (Polish Notation) : Operator is at the left of Operands. '+ab' is an example.
Infix Expression (General Notation) : Operator is at the middle of Operands. 'a+b' is an example.
Postfix Expression (Reverse Polish Notation) : Operator is at the right of Operands. 'ab+' is an example.
Stacks can be used to convert an infix expression into postfix expression and then evaluate it. Here is the C program to convert an infix expression into postfix expression and evaluate it using stack.

Program
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#define MAX 99
typedef struct stack
{
int data[MAX];
int top;
}stack;
void init(stack *s)
{
s->top=-1;
}
int empty(stack *s)
{
if(s->top==-1)
return 1;
else
return 0;
}
int full(stack *s)
{
if(s->top==MAX-1)
return 1;
else
return 0;
}
void push(stack *s,int x)
{
s->top=s->top+1;
s->data[s->top]=x;
}
int pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return x;
}
int top(stack *p)
{
return p->data[p->top];
}
int precedence(char x)
{
if(x=='(')
return 0;
else if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/'||x=='%')
return 2;
else
return 3;
}
void infix_to_postfix(char infix[],char postfix[])
{
stack s;
char x;
int i,j;
char token;
init(&s);
j=0;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token))
postfix[j++]=token;
else
if(token == '(')
push(&s,'(');
else
if(token == ')')
while((x=pop(&s))!='(')
postfix[j++]=x;
else
{
while(precedence(token)<=precedence(top(&s))&&!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}
}
while(!empty(&s))
{
x=pop(&s);
postfix[j++]=x;
}
postfix[j]='\0';
}
int evaluate_expression(char x,int op1,int op2)
{
if(x=='+')
return op1+op2;
else if(x=='-')
return op1-op2;
else if(x=='*')
return op1*op2;
else if(x=='/')
return op1/op2;
else if(x=='%')
return op1%op2;
else
return 0;
}
void evaluate_postfix(char postfix[])
{
stack s;
char x;
int i,val,op1,op2;
init(&s);
for(i=0;postfix[i]!='\0';i++)
{
x=postfix[i];
if(isalpha(x))
{
printf("\n Enter the value of %c : ",x);
scanf("%d",&val);
push(&s,val);
}
else
{
op2=pop(&s);
op1=pop(&s);
val=evaluate_expression(x,op1,op2);
push(&s,val);
}
}
val=pop(&s);
printf("\n Postfix Evaluation : %d ",val);
}
void main(void)
{
char infix_expression[30],postfix_expression[30];
clrscr();
printf("\n Infix Expression : ");
gets(infix_expression);
infix_to_postfix(infix_expression,postfix_expression);
printf("\n Postfix Expression : %s \n",postfix_expression);
evaluate_postfix(postfix_expression);
getch();
}

Output
Infix Expression : a+b-c*d/e
Postfix Expression : ab+cd*e/-
Enter the value of a : 1
Enter the value of b : 2
Enter the value of c : 3
Enter the value of d : 4
Enter the value of e : 5
Enter the value of f : 6
Postfix Evaluation : 1

Also, stacks are used for evaluation of factorials. Stacks can be used to solve Towers of Hanoi problem. Stacks are useful in quick sort, one of the best sorting techniques. Refer this article for more on stacks.

For information on the other classic data structures like queues, trees etc., refer the article Introduction to Classic Data Structures - Part 2.