UNIT – I

Introduction to data structures

Abstract data type(ADT)
Stacks
Queues
Circular queues
Implementation with Arrays
Stack applications:
- infix to post fix conversion
- postfix expression evaluation
Applications of queues.
 What is Data Structure?
• A data structure is a systematic way of storing,
organizing and accessing data.
• Data Structure is the method of representing logical
relationships between individual data elements
related to the solution of a given problem.
• Data structure is a representation of data and the
operations allowed on that data.
• A data structure in fact creates a new data type
- i.e. using predefined types or previously user
defined types.
- Such new types are then used to reference variables

type within a program

 Types of Data Structure

Basic Data Structures

Linear Data Structures Non-Linear Data Structures

Arrays Linked Lists Stacks Queues Trees Graphs Hash Tables

•Linear: Elements form a sequence or a liner list.

•Non-Linear: The data values are not arranged in
order
• No single data structure works well for all
purposes, and so it is important to know the
strengths and limitations of each data structure
 Abstract Data Type and Data Structure
• Definition:-
– Abstract Data Types (ADTs) stores data and allow
various operations on the data to access and
change it.
– A useful tool for specifying the logical
properties of a data type.
– An ADT is a collection of data and associated
operations for manipulating that data

• Data Structures
– Physical implementation of an ADT
– data structures used in implementations are
provided in a language (primitive or built-in)
or are built from the language constructs (user-
defined)
– Each operation associated with the ADT is
implemented by one or more subroutines in the
implementation
 The Core Operations of ADT

• Every Collection ADT should provide a way to:

– add an item
– remove an item
– find, retrieve or access an item

• Many, many more possibilities

– is the collection empty
– make the collection empty
– give me a sub set of the collection
 Pseudo-code
• A mixture of natural language and high level
programming concepts that describes the main ideas
behind a generic implementation of a data structure
(or) algorithm.

Eg: Algorithm arrayMax(A,n)

Input : An array ‘A’ storing ‘n’ integers
Output : The maximum element in ‘A’
currentMax  A[0]
for i  1 to n – 1 do
if currentMax < A[i] then currentMax  A[i]
return currentMax

• It is more structured than usual prose but less

formal than programming language
 What pseudo-code contains ?
• Expressions :-
- use standard mathematical symbols to describe numeric and boolean
expressions
- use  for assignment (‘=‘ in C)
- use = for equality relationship (“==“ in C)
• Method Declarations
- Algorithm name(param1, param2)
• Programming Constructs:-
- decision structures if …. Then….[else..]
- while loops: while ….. Do
- repeat loops: repeat ….. Until….
- for loop : for……. Do
- Array indexing A[i], A[i,j]
• Methods :-
- calls : methodname(args)
- returns: return value
 Debugging
• Definition: Bug – A mistake in your program that can
be one of the following
– Compile-time error
• Syntax error – program will not compile with
syntax errors (fairly easy to fix)
– Run-time error (when program is executing)
• Typos – program not entered correctly, though
syntax is correct (usually relatively easy to fix)
• Logical error – the logic of the program/algorithm
is inconsistent with the problem (much harder to
find/fix)
• Key Idea:
– You must understand what your program is supposed
to do in order to debug it
– Before writing the code, create an example that can
be easily verified by hand
• Poor Man’s Debugger:
– Print statements of program variables (printf) –
allow you to see the contents of the variables as
the program executes
• Using a debugger it is possible to do the following:
– Step through the program instruction by instruction
(trace the program) F7
• Stepping over functions F8
• Stepping into functions F7
• Stepping out of functions Shift-F8
(good if you accidentally stepped into a function)
– As you step through the program, you can look at the
contents of variables and track their changes.
• If you expect a variable to change to a specific
value and it does not – you have found your bug!

• Sometimes stepping through a program is too time

consuming. In this case, set breakpoints and run
(go) until you reach the next breakpoint
– In TC – breakpoints are set by putting cursor on
the line where you want to stop and selecting
break point from menu (or cntrl+ F8). You should
see a red line over code. To remove a breakpoint,
repeat the process and the red line should go
away.
• To start debugging press F7 and to continue to
the next breakpoint, use cntrl+F9

• While there are many other functions available in

the debugger, these few key concepts are a good
start

• Convert the nested for loop example into a simple

C program
• Debug this simple program tracing the values of
– i
– j
– nums[i][j], as they are displayed

• if there are many errors (compile-time or run-time),

comment out large portions of the code and test
incrementally
 Stack
• Stack is a Data structure in which all additions
and deletions are restricted to one end, called
top.
• Allows access to only the last item inserted
• Stacks are known as Last In First Out (LIFO) DS.
• Placing a data item on the top is called
“pushing”, while removing an item from the top
is
called “popping” it
• push and pop are the primary stack operations
 Stack operations
Push : adds a new element
Push(X,S)  add the element X to the TOP of stack

Pop : removes element

Pop(S)  removes the TOP element and returns its
value
Peek : returns top element
Peek(S)  return the top element without removing

IsEmpty : reports whether the stack is empty

IsEmpty(S)  report whether the stack S is empty

IsFull : reports whether the stack is full

IsFull(S)  report whether the stack S is full

Display : displays the stack elements

Display(S)  displays all stack elements
#define MAX 5 typedef struct
void display(stack s) {
{ int top;
int i; int sele[MAX];
if(!isEmpty(s)) }stack;
{ int isEmpty(stack s)
printf("\n Stack elements are :"); {
for(i = 0; i <= s.top; i ++) if(s.top == -1)
printf("%5d",s.sele[i]); return 1;
} else
else printf("\n Stack is empty"); return 0;
} }
int pop(stack *sp) int isFull(stack s)
{ {
if(!isEmpty(*sp)) if(s.top == MAX-1)
return sp->sele[sp -> top--]; return 1;
else printf("\nStack Underflow"); else
return sp ->top; return 0;
} }
void push(stack *sp,int ele)
{
if(!isFull(*sp))
sp->sele[++sp -> top] = ele;
else printf("\n Stack Overflow");
#include "stkADTin.h"
int menu()
{
int ch; clrscr();
printf("\n Stack Operations :");
printf("\n\t 1 -> push \n\t 2 -> pop \n\t 3 -> display \n\t 4 ->exit");
printf("\n Enter your choice :"); scanf("%d",&ch);
return ch;
}
void main()
{
int ch,ele; stack s; s.top = -1;
do { ch = menu();
switch(ch) {
case 1: printf("\n Enter element :"); scanf("%d",&ele);
push(&s,ele); break;
case 2:ele = pop(&s);
if(ele != -1) printf("\n the deleted element is %d",ele); break;
case 3: display(s); break;
case 4: break;
default : printf("\n Invalid choice. try again ");
}
getch();
}while(ch!=4);
 Stack Applications
• Reversing Data: Very useful for finding
palindromes.
• Converting Decimal to Binary
• Backtracking: Stacks can be used to backtrack to
achieve certain goals
• Evaluating arithmetic expressions
- Infix to Postfix Conversion
- Postfix Evaulation
• BracketChecker (balancer)
- A syntax checker (compiler) that understands
a language containing any strings with balanced
brackets ‘{‘ ‘[‘ ‘(‘ and ‘)’, ‘]’, ‘}’
• Page-visited history in a Web browser
• Undo sequence in a text editor
• Saving local variables when one function calls
another, and this one calls another, and so on.
• Recursive Functions
 Representing Arithmetic Expressions
(Infix, Prefix, Postfix)

• Example: arithmetic expression a + b consists

of operands a, b and operator +.
– Infix notation is format where operator is
specified in between the two operands. a + b
– Prefix notation is format where operator is
specified before the two operands. + a b
– Postfix notation is format where operator is
specified after the two operands. Postfix
notation is also called RPN or Reverse
Polish Notation. a b +
 Arithmetic Expressions

Prefix Notation Infix Notation Postfix

Notation

+A * B C A + B * C A B C * +

* + A B C (A+B) * C A B + C *

+ – A B C A – B + C A B – C +

– A + B C A – (B+C) A B C + –
 Infix to Postfix Conversion
Assume 1-digit integer operands, the binary operators + - * / only, and the
string to be converted is properly formed

Rules for converting the infix string:

Starting from the left hand end, inspect each character of the string

1. if it’s an operand – append it to the postfix string

2. if it’s a ‘(‘ – push it on the stack

3. if it’s an operator –
if the stack is empty, push it on the stack
else pop operators of
greater or equal precedence and append them to the postfix string, stopping when
a ‘(‘ is reached, an operator of lower precedence is reached, or the stack is empty;
then push the operator on the stack
4. if it’s a ‘)’ – pop operators off the stack, appending them to the postfix string, until
a ‘(‘ is encountered and pop the ‘(‘ off the stack
5. when the end of the infix string is reached – pop any remaining operators off the
stack and append them to the postfix string
Infix to Postfix Conversion (continued)
An Example: 7-(2*3+5)*(8-4/2)  723*5+842/-*-
Remaining Infix String char Stack Postfix String Rule Used
7-(2*3+5)*(8-4/2) empty null
-(2*3+5)*(8-4/2) empty 7 1
(2*3+5)*(8-4/2) - 7 3
2*3+5)*(8-4/2) -( 7 2
*3+5)*(8-4/2) -( 72 1
3+5)*(8-4/2) -(* 72 3
+5)*(8-4/2) -(* 723 3
5)*(8-4/2) -(+ 723* 3
)*(8-4/2) -(+ 723*5 1
*(8-4/2) - 723*5+ 4
(8-4/2) -* 723*5+ 3
8-4/2) -*( 723*5+ 2
-4/2) -*( 723*5+8 1
4/2) -*(- 723*5+8 3
/2) -*(- 723*5+84 1
2) -*(-/ 723*5+84 3
) -*(-/ 723*5+842 1
null empty 723*5+842/-*- 4&5
#include "stkadtch.h" int isOperator(char ch)
void findPostfix(char ine[],char pose[]) {
{ if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
char ch; int i,j = 0; return 1;
stack s; s.top = -1; return 0;
for(i = 0; ine[i] != '\0'; i++){ }
ch = ine[i];
if(ch == '(') push(&s,ch); int prec(char ch){
else if(ch == ')') { switch(ch){
while(peek(s) != '(') case '*' :
pose[j++] = pop(&s); case '/' : return 3;
pop(&s); } case '-' :
else if(isOperator(ch)){ case '+' : return 2;
if(isEmpty(s)) push(&s,ch); case '(' : return 1; }
else{ }
while(prec(ch) < prec(peek(s)))
pose[j++] = pop(&s); void main(){
push(&s,ch); }} char inexpr[20],postexpr[20]="";
else pose[j++] = ch; } printf("\n Enter Infix Expression :");
while(!isEmpty(s)) gets(inexpr);
pose[j++] = pop(&s); findPostfix(inexpr,postexpr);
pose[j] = '\0'; printf("\n postfix expression is:%s",postexpr);
} getch();
}
Postfix Expression Evaluation
Assume 1-digit integer operands, the binary operators + - * / only,
and the string to be evaluated is properly formed
Rules for processing the postfix string:
Starting from the left hand end, inspect each character of the string
1. if it’s an operand – push it on the stack
2. if it’s an operator – remove the top 2 operands from the stack,
perform the indicated operation, and push the result on the stack

An Example: 3*(4+5)/2  345+*2/  13

Remaining Postfix String int Stack (top) Rule Used
345+*2/ empty
45+*2/ 3 1
5+*2/ 3 4 1
+*2/ 3 4 5 1
*2/ 3 9 2
2/ 27 2
/ 27 2 1
null 13 2
value of expression at top of stack
#include "stkadtin.h" void main()
int isOperator(char ch) {
{ char postfix[20],ch
if(ch == '+' || ch == '-' || ch == '*' || int i,oprd1,oprd2,res;
ch == '/') stack s; s.top = -1;
return 1; printf("\n Enter postfix expression :");
return 0; gets(postfix);
} i = 0;
int calc(int a,int b,char op) while(postfix[i] != '\0')
{ {
switch(op) ch = postfix[i++];
{ if(isOperator(ch))
case '*' : return a * b; {
case '/' : return a/b; oprd1 = pop(&s);
case '+' : return a + b; oprd2 = pop(&s);
case '-' : return a - b; res = calc(oprd1,oprd2,ch);
} push(&s,res);
return 0; }
} else push(&s,ch -'0');
}
res = pop(&s);
printf("\n Result :%d",res);
getch();
}
 Queues
• Queue is a data structure in which items may be
deleted at one end (front) and into which items
may be inserted at the other end (rear).
• This mechanism is called First-In-First-Out
(FIFO).
• Placing an item in a queue is called “insertion
or enqueue”, which is done at the end of the
queue called “rear”.
• Removing an item from a queue is called
“deletion or dequeue”, which is done at the
other end of the queue called “front”.
delete

Rear Front
insert
 Queue operations
enqueue : adds a new element
enqueue(Q,x) add the element X to the REAR of
queue

dequeue : removes element

dequeue(Q)  removes the FRONT element and returns
its value
IsEmpty : reports whether the queue is empty
IsEmpty(Q)  report whether the queue Q is empty

IsFull : reports whether the queue is full

IsFull(Q)  report whether the queue Q is full

Display : displays the queue elements

Display(Q)  displays all queue elements
 Implementation of Queues
• The array to implement the queue would need two
variables (indices) called front and rear to point
to the first and the last elements of the queue.
• Initially:
– q->rear = -1;
– q->front = 0;
• For each enqueue operation rear is incremented by
one, and for each dequeue operation , front is
incremented by one.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

10 50 13 5 -8 14

Front Rear
#include "stdio.h"
#include "conio.h" int dequeue(queue *qp)
#define MAX 5 {
typedef struct if(!isEmpty(*qp))
{ return qp->qele[qp -> front++];
int front; else
int rear; printf("\nqueue Underflow");
int qele[MAX]; return 0;
}queue; }
int isEmpty(queue q){ void enqueue(queue *qp,int ele)
if(q.rear < q.front) return 1; {
else return 0; } if(!isFull(*qp))
int isFull(queue q){ qp->qele[++qp -> rear] = ele;
if(q.rear == MAX-1) return 1; else
else return 0; } printf("\n queue Overflow");
void display(queue q){
int i; }
if(!isEmpty(q)){
printf("\n queue elements are :");
for(i = q.front; i <= q.rear; i ++)
printf("%5d",q.qele[i]);
}
else
printf("\n queue is empty"); }
 int menu(){
int ch; clrscr();
printf("\n queue Operations :");
#include "qADTin.h" printf("\n\t 1 -> enqueue \n\t 2 -> dequeue
void main(){
int ch,ele; \n\t 3 -> display \n\t 4 ->exit");
char che; printf("\n Enter your choice :");
queue q; q.front = 0; q.rear = -1; scanf("%d",&ch); return ch;}
do {
ch = menu();
switch(ch){
case 1: printf("\n Enter element :");
scanf("%d",&ele);
enqueue(&q,ele); break;
case 2:ele = dequeue(&q);
if(ele)
printf("\n the deleted element is %d",ele);
break;
case 3: display(q); break;
case 4: break;
default : printf("\n Invalid choice. try again ");
}
}while(ch!=4);
}
 Applications of Queues

• Access to shared resources (e.g., printer)

• Multiprogramming

• Waiting on hold for tech support

 Circular Queue
• In queue, It is possible to reach the absurd
situation where the queue is empty, yet no new
element can be inserted.

• Solution is to view the array that holds the queue

as a circle rather than straight line.

• That is imagine the first element of the

array(postion 0) as immediately following the last
element.

• This implies that even if the last element is

occupied, a new value can be inserted behind it in
the first element of the array as long as the
first element is empty

• Both the front and the rear pointers wrap around

the beginning of the array.
 Circular Implementation

0 1 2 3 4 5 6 7
Initially q -> rear = MAX - 1
and q -> front = MAX - 1;

When an element is
7 Inserted rear incremented by
0 rear = (rear + 1) % MAX;
When an element is deleted
front is incremented by
front = (front + 1) % MAX;
6 1
The queue is empty when
fornt = rear;

The queue is full when

(rear + 1)%MAX = front;
5 2

4 3
#define MAX 5 void display(queue q){
typedef struct int i;
{ if(!isEmpty(q)) {
int front; printf("\n queue elements are :");
int rear; for(i = q.front+1; i <= q.rear; (++i) %MAX)
int qele[MAX]; printf("%5d",q.qele[i]);
}queue; }
int isEmpty(queue q) else printf("\n queue is empty");
{
if(q.rear == q.front) }
return 1; int dequeue(queue *qp){
else if(!isEmpty(*qp)) {
return 0; qp -> front = (qp -> front + 1) % MAX ;
} return qp->qele[qp -> front]; }
int isFull(queue q) else printf("\nqueue Underflow");
{ return 0;
if((q.rear+1)%MAX == q.front ) }
return 1; void enqueue(queue *qp,int ele){
else if(!isFull(*qp)) {
return 0; qp -> rear = (qp -> rear + 1) % MAX;
} qp->qele[qp -> rear] = ele; }
else printf("\n queue Overflow");

}
 Assignment – 1
1. Write a C program to convert a given infix expression into postfix expression
using pointers.
2. Declare a circular queue of integers such that F points to the front and R points
to the rear. Write functions
(a) To insert an element into queue
(b) To delete an element from queue.
3. Explain how is queue represented as an abstract data type. Write a C program
to implements it.
4. What is a Data Structure? Explain in detail.
5. Explain infix, prefix & postfix expressions with examples.
6. Show how to implement a queue of integers in C by using an array int
q[QUEUESIZE] , where q[0] is used to indicate the front of the queue , q[1]
is used to indicate its rear and where q[2] through q[QUEUESIZE -1] contain
elements on the queue. Show how to initialize such an array to represent the
empty queue and write routines remove, insert and empty for such an
implementation.
7. What do you mean by stack? Explain with example.
8. Write a C program to evaluate Postfix Expression.
9. Write about circular queues and its implementation.
10. What are the applications of stack. Explain in detail.
 References

• Data Structures Using C and C++: Yedidyah Langsam, Moshe J.

Augenstein, Aaron M. Tenenbaum
• Data Structures: A Pseudocode Apporoach with C. Gilberg, Richard
F., Forouzan, Behrouz A.. PWS Publishing Company: 1998
• Data Structures Through C: Yashavant Kanetkar..2nd Edition -
BPB Publications.