Introduction to
Data Structures
Introduction to Data Structures
Overview
• Abstract data types and data structures
• Linear data structures
• Arrays
• Stacks
© CDAC 2021 Introduction to Data Structures
Data Type
• Realization of some abstract notion.
• To the system: The way in which a particular memory chunk is
interpreted.
• To the user: Data type is identified by its behaviour; the actual storage
of data does not alter the behaviour.
• Example
• Data type int in Java realizes abstract notion of integers and provides
operators like +, -, *, / .
Introduction to Data Structures
Data Structures
• Conceptually similar to a data type.
• Typically, more general purpose and used to organise specific data.
• Defines set of operators and representation.
• Combines more than one simple data items or data structures.
• Relative positions of the data items are of interest.
• Example:
• Array, matrix, list…
Introduction to Data Structures
Data Structures
• User of a data structure(DS) is interested only in the operators
provided.
• Implementation details are hidden from the application program.
• Higher level of abstraction for the programmer.
• Can be used like a data type in the application.
Introduction to Data Structures
‘Structure’ of a Typical DS
• DS means relative positioning of data items and their access
mechanism.
• The positioning can be implicit (as in the case of arrays) or explicit, i.e.
each item holds references to its neighbours.
• This gives two parts per node of a DS
• Data (can be any data type, independent of the DS)
• Linkages to neighbouring nodes (specific to the DS)
Node Data Link
Introduction to Data Structures
‘Structure’ of a Typical DS
• The access mechanism defines the type of DS
• Totally ordered (linear)
• Partially ordered (eg: trees)
• Non-linear (eg: graphs)
• Actual representation can be different as long as access mechanism is
same.
Introduction to Data Structures
Linear DS
• Data items (or nodes) arranged in linear fashion.
• Every node has a unique next element and a unique previous
element.
• All elements can be traversed in a single pass
• Example
• Array, Linked list, Stack, Queue.
. . . …………
Introduction to Data Structures
Array
• Ordered collection of objects of same type.
• Contiguous storage allocation: enables random access.
• Linkages to neighbours are implicit - through position in the memory.
• Size is fixed while constructing.
• Insertion of item requires shifting of existing items.
• Available in Java.
Introduction to Data Structures
Stack
• An opaque pipe closed at one end.
• Only one element at a time is available, no other information is
accessible.
• Addition and deletion of elements only at the open end.
• Last in first out (LIFO) behaviour.
Introduction to Data Structures
Stack Example
Method invocation and return
Frame
of D( )
A( ) B( ) C()
{ { { Frame
B( ) ; C( ); D( ) ; of C( )
: : : Frame
: : : of B( )
} } } Frame
of A( )
Introduction to Data Structures
Stack Operations
• clear() – clear/empty the stack
• isEmpty() – check if it is empty
• isFull() – check if it is full?
• push(el) – Put the element el on the top of the stack.
Note: you can’t put it anywhere else!
• pop() - remove the topmost element from the stack.
Note: can’t remove any other element!
• top() - Return the topmost element without removing
it.
Introduction to Data Structures
Stack Operations
• push(item) - item becomes the new top element
10 top
push (3) (3)
push (10) (10, 3) 3
• pop() - top element removed. An error if stack is empty.
i = pop () (3)
Value of i becomes 10
3 top
Introduction to Data Structures
Stack Implementation
• Stack using array
• Data items stored as an array
• Position of ‘top’ maintained by an index
5
1 top
12
Introduction to Data Structures
Stack Implementation
public class StackArray {
private int top; // will point to the topmost element of the stack
private Object[] storage;
public StackArray(int n){
int size = n;
storage = new Object[size];
top = -1;
}
Introduction to Data Structures
Stack Implementation
public void clear(){top = -1;}
public boolean isFull(){
return (top >= storage.length-1);
}
public boolean isEmpty(){
return (top == -1);
}
public void push(Object el){
if (!isFull())
{top++; storage[top] = el;}
}
Introduction to Data Structures
Stack Implementation
public Object pop(){
if(!isEmpty()){
Object tmp = storage[top]; top--;
return tmp;
}
else
throw new Exception(“pop on empty stack”);
}
public Object topEl(){
if(!isEmpty()){return storage[top];}
else return null;
}
}
Introduction to Data Structures
Stacks in java.util
• Available as extension of class Vector: java.util.Stack
• Object push(Object e): returns the object which is pushed.
• Object peek(): similar to topEl();
• peek() and push() return the object on the top, not its copy.
• Pop() removes the object at top, and returns that object as value;
• Intermediate elements still accessible from the Vector interface;
violation of integrity of stack.
Introduction to Data Structures
Stacks in java.util
boolean empty()
Object pop()
int Search(Object el): returns position of el in
the stack. Not a stack operation: we will
ignore.
Stack(): constructor; creates an empty stack.
Introduction to Data Structures
Stack Application
• Many cases of LIFO(last-in first-out) applications in computer science,
particularly programming language implementation, algorithms and
operating systems.
• We will discuss the bracket matching problem as a case study.
Introduction to Data Structures
Bracket Matching Problem
•[([))] - ?
•[]()([]) - ?
•[{}([])] - ?
Conditions:
• Every open bracket should be closed by the appropriate
close bracket.
• No extra close brackets.
• The last bracket opened should be closed first.
Introduction to Data Structures
Pseudo Code
valid = true // assume string is valid so far
Stack s = new Stack(); s.clear();
while (valid & (input not over )){
read next symbol (symb) ;
if (symb is ‘(‘ or ‘[‘ or ‘{‘ ){
s.push(symb);
}
else if (symb is ‘)’ or ‘]’ or ‘}’ ){
if (s.isEmpty()) valid = false // too many closing brackets
i = s.pop()
if (i does not match with symb) valid = false
}
}
Introduction to Data Structures
Pseudo Code
if (! s.isEmpty ( ) )
valid = false ; // too many open brackets
if (valid) system.out.println("String is valid");
else system.out.println("String is not valid");
Introduction to Data Structures
Summary
• Data Structures: useful abstractions for a programmer
• Arrays, Stacks and Queues: simple linear data structures
• We will discuss “better” representations for these, and introduce
more sophisticated DS in subsequent sessions.
Introduction to Data Structures
