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.

Linked Lists


Every element comprises of some data and pointer(s) to next(previous) elements. Linked lists are better than arrays. A major reason is that insertion, deletion etc,. operations are easy. In arrays, to insert/delete an element, indexes of all the elements next to it must be changed. But in linked lists, to insert/delete an element, only one or two pointers must be changed. Also, size of arrays is fixed i.e. the maximum possible size must be known. There is no such limit for linked lists. Linked lists are mainly of 4 types. They are single linked lists, double linked lists (linear linked lists) and circular single linked lists, circular double linked lists (circular linked lists). A single linked list is a linked list in which every element contains some data and a pointer to the next element. A double linked list is a linked list in which every element contains some data and pointers to the previous and next elements.
Linear Linked Lists
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.
Circular Linked Lists

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:
Stack Abstract Data Type

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.


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: