CS163: Data Structures and
Algorithms
Dr. Prabhu Prasad B M
CSE, IIITDWD
Data Structures
● Data structure refers to a scheme for organizing data,
− it is an arrangement of data in computer's memory in such
a way that it could make the data quickly available to the
processor for required calculations
●
Data Structures
● Data structure refers to a scheme for organizing data,
− it is an arrangement of data in computer's memory in such
a way that it could make the data quickly available to the
processor for required calculations
● A data structure is a way of storing data in a computer so that
it can be used efficiently and it will allow the most efficient
algorithm to be used
●
Data Structures
● Data structure refers to a scheme for organizing data,
− it is an arrangement of data in computer's memory in such
a way that it could make the data quickly available to the
processor for required calculations
● A data structure is a way of storing data in a computer so that
it can be used efficiently and it will allow the most efficient
algorithm to be used
● As data structure is a scheme for data organization so the
functional definition of a data structure should be
independent of its implementation
− known as ADT (Abstract Data Type)
Data Structures
● ADT (Abstract Data Type)
− is a logical description of how the data is viewed and the
operations that are allowed without regard to how they will
be implemented
−
Data Structures
● ADT (Abstract Data Type)
− is a logical description of how the data is viewed and the
operations that are allowed without regard to how they will
be implemented
− concerned only with what data is representing and not
with how it will eventually be constructed
−
Data Structures
● Classification of Data Structures
−
Data Structures
● Compound Data structure:
− can be constructed with the help of any one of the
primitive data structure and it is having a specific
functionality
− can be classified as
● Linear
● Non-linear
Data Structures
● Linear Data structure:
− can be constructed as a continuous arrangement of data
elements in the memory using array data type
−
Data Structures
● Linear Data structure:
− can be constructed as a continuous arrangement of data
elements in the memory using array data type
− the relationship of adjacency is maintained between the
data elements
− Examples:Array, Stack, Queue, and Linked Lists
Data Structures
● Non-linear Data Structure:
− can be constructed as a collection of randomly distributed
set of data item joined together by using a special pointer
− Example:Tree, Decision tree, Graph and Forest
Data Structures
● Operations applied on linear and non-liner data structure:
− Add an element
− Delete an element
− Traverse
− Sort the list of elements
− Search for a data element
●
Stack
● A stack is an Abstract Data Type (ADT), commonly used in
most programming languages.
● It is named stack as it behaves like a real-world stack, for
example – a deck of cards or a pile of plates, etc.
●
Stack
● A stack is an Abstract Data Type (ADT), commonly used in
most programming languages.
● It is named stack as it behaves like a real-world stack, for
example – a deck of cards or a pile of plates, etc.
●
Stack
● A stack is an Abstract Data Type (ADT), commonly used in
most programming languages.
● It is named stack as it behaves like a real-world stack, for
example – a deck of cards or a pile of plates, etc.
− A real-world stack allows operations at one end only
●
●
Stack
● Aka LIFO or FILO data structure
− Last In First Out
− First In Last Out
●
Stack
● Aka LIFO or FILO data structure
− Last In First Out
− First In Last Out
● The element which is placed (inserted or added) last, is
accessed first
− Insertion operation – PUSH
− Removal operation - POP
− get the top data element of the stack - PEEK
−
Stack
● Aka LIFO or FILO data structure
− Last In First Out
− First In Last Out
● The element which is placed (inserted or added) last, is
accessed first
− Insertion operation – PUSH
− Removal operation - POP
− get the top data element of the stack - PEEK
● can be implemented by means of Array, Structure, Pointer, and
Linked List
Stack
● Aka LIFO or FILO data structure
− Last In First Out
− First In Last Out
●
Stack
● Basic operations
− push() − Pushing (storing) an element on the stack.
− pop() − Removing (accessing) an element from the stack
− peek() − get the top data element of the stack, without
removing it
− isFull() − check if stack is full
− isEmpty() − check if stack is empty
Stack
● At all times, a pointer is maintained to the last PUSHed data
on the stack
● As this pointer always represents the top of the stack, hence
named top
● The top pointer provides top value of the stack without
actually removing it
Stack
● peek()
− algorithm
− begin procedure peek
● return stack[top]
− end procedure
Stack
● peek()
− algorithm
− begin procedure peek
● return stack[top]
− end procedure
− Implementation
● int peek()
● {
● return stack[top];
● }
Stack
● isfull()
− algorithm
− begin procedure isfull
● if top equals to MAXSIZE-1
● return true
● else
−return false
● endif
− end procedure
Stack
● isfull()
− implementation
− bool isfull()
− {
● if(top == MAXSIZE-1)
− return true;
● else
− return false;
− }
Stack
● isempty()
− algorithm
− begin procedure isempty
● if top less than 0
− return true
● else
− return false
● endif
− end procedure
Stack
● isempty()
− implementation
− bool isempty()
− {
● if(top == -1)
− return true;
● else
− return false;
− }
Stack
● push()
− Steps involved
● Step 1 − Checks if the stack is full.
● Step 2 − If the stack is full, produces an error and exit.
● Step 3 − If the stack is not full, increments top to point
next empty space.
● Step 4 − Adds data element to the stack location, where
top is pointing.
● Step 5 − Returns success.
Stack
● push()
− Steps involved
● Step 1 − Checks if the stack is full.
● Step 2 − If the stack is full, produces an error and exit.
● Step 3 − If the stack is not full, increments top to point next empty space.
● Step 4 − Adds data element to the stack location, where top is pointing.
● Step 5 − Returns success.
Stack
● push()
− algorithm
− begin procedure push: stack, data
● if stack is full
−return null
● endif
− top ← top + 1
● stack[top] ← data
− end procedure
Stack
● push()
− implementation
− void push(int data) {
● if(!isFull()) {
−
top = top + 1;
− stack[top] = data;
− }
● else {
− printf("Could not insert data, Stack is full.\n");
− }
● }
Stack
● pop()
− Steps involved
● Step 1 − Checks if the stack is empty.
● Step 2 − If the stack is empty, produces an error and
exit.
● Step 3 − If the stack is not empty, accesses the data
element at which top is pointing.
● Step 4 − Decreases the value of top by 1.
● Step 5 − Returns success.
Stack
● pop()
− Steps involved
● Step 1 − Checks if the stack is empty.
● Step 2 − If the stack is empty, produces an error and exit.
● Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
● Step 4 − Decreases the value of top by 1.
● Step 5 − Returns success.
Stack
● pop()
− algorithm
− begin procedure pop: stack
● if stack is empty
− return null
● endif
● data ← stack[top]
● top ← top - 1
● return data
− end procedure
Stack
● pop()
− Implementation
− int pop(int data)
− {
● if(!isempty()) {
data = stack[top];
−
− top = top - 1;
− return data;
● }else
● {
− printf("Could not retrieve data, Stack is empty");
● }
− }
Stack - applications
● Evaluation of Arithmetic expressions
● Parenthesis Checking
● Function call
● String Reversal
● Memory Management
Stack - applications
● Evaluation of Arithmetic expressions
− Infix, prefix, postfix conversions
●
