DS Week 7 Lecture Stacks by Dr Gaurav

Subject: Data Structure
Using C++ (CSET243)
Week 7 Lecture
Stack and Its Applications

What, Why and How?
by
Dr Gaurav Kumar
Asst. Prof, Bennett University
Quick Recap of Previous Weeks’ Learnings
• Understood the Linked List and Operations

Stack Data Structure
It is called as stack because it behaves like a real-world stack, piles of
books, etc. It is a linear data structure.
Understanding the Stack
• Stack is an abstract data type with a pre-defined
capacity.
• One side open another side closed
• Works on LIFO (Last in First Out) or FILO (First
in Last Out) order to Insert or Delete the element.
• Top is a variable which contains the position of the
top-most element in the stack.
• Stack can be defined as a container in which insertion
(push) and deletion (pop) can be done from the one
end known as the top of the stack.

Stack Creation: Using Array
int stack[n], n = 100, top = -1;

Operations on Stack
push() − (Insertion) Insert element on the stack.
pop() − (Deletion) Removing an element from the stack.

Stack Overflow
Push Operation Algorithm:

Step-1: If TOP = Max-1
Print “Overflow”
Overflow error
Goto Step 4
Step-2: Set TOP= TOP + 1
Step-3: Set Stack[TOP]= ELEMENT
Step-4: END
Stack Overflow
int stack[n], n = 100, val=10, top = -1;
Push Operation Algorithm: void push(int val, int n)

{
Step-1: If TOP = Max-1
if(top >= n-1)
Print “Overflow”
cout<<"Stack Overflow"<<endl;
Goto Step 4
else {
Step-2: Set TOP= TOP + 1
top++;
Step-3: Set Stack[TOP]= ELEMENT
stack[top] = val;
Step-4: END
}
Stack Underflow
Pop Operation Algorithm:

Step-1: If top = -1 or top= NULL
Print “Underflow”
Underflow error Goto Step 3
Step-2: Set Val= Stack[TOP]
Step-3: Set top= top – 1
Step-4: End
Stack Underflow
int stack[n], n = 100, val=10, top = -1;
Pop Operation Algorithm: void pop()

{
Step-1: If top = -1 or top= NULL
if(top <= -1)
Print “Underflow”
cout<<"Stack Underflow"<<endl;
Goto Step 3
else
Step-2: Set Val= Stack[TOP] {
Step-3: Set top= top – 1 cout<<"The popped element is "<< stack[top] <<endl;
Step-4: End top--;
}
}
Operations on Stack
isEmpty(): It determines whether the stack is empty or not.
isFull(): It determines whether the stack is full or not.'
isEmpty () Operation Algorithm: isFull () Operation Algorithm:

Step-1: If top = -1 or top= NULL Step-1: If top = Max-1
Print “Underflow” Print “Overflow”
Step-2 : Stop Step 2: Stop

Operations on Stack
peek() − Accessing the top data element of the stack,
without removing it.
Algorithm:
Step-1: If TOP = NULL
PRINT “Stack is Empty”
Goto Step 3
Step-2: Return Stack[TOP]
Step-3: END
Operations on Stack
• count(): It returns the total number of elements available in a stack.
• change(): It changes the element at the given position.
• display() or Traverse(): It prints all the elements available in the stack.

Stack Operation: Traversal
void traverse() {
if(top>= 0) {
cout<<"Stack elements are:";
for(int i = top; i>= 0; i--)
cout<<stack[i]<<" ";
cout<<endl;
}
else
cout<<"Stack is empty";
}
Applications of Stack
1) Balancing of symbols
During compilation of program, when the opening braces
come, it push the braces in a stack, and when the closing
int main() braces appear, it pop the opening braces from the stack.
{ Therefore, the net value comes out to be zero.
cout<<"Hello";
cout<<"Students"; If any symbol is left in the stack, it means that some Syntax
} Errors occurs in a program.

2) String reversal
• First, we push all the characters of the string in a stack

until we reach the null character.
• After pushing all the characters, we start taking out the

character one by one until we reach the bottom of the
stack.
2) UNDO/REDO
• We have an editor in which we write 'a', then 'b', and
then 'c'; therefore, the text written in an editor is abc.
• There are three states, a, ab, and abc, which are stored in
a stack.
• To perform Undo and Redo operations, we need 2

stacks, one stack shows UNDO state, and the other
shows REDO state.
2) UNDO/REDO • There are three states, a, ab, and abc, If we want to perform UNDO
operation, and want to achieve 'ab' state, then we implement pop
operation.
• Push all operations to Undo stack.
c • When undo is called, pop operations from Undo stack and push it
b to Redo stack.
a
2) UNDO/REDO • There are three states, a, ab, and abc, If we want to perform UNDO
operation, and want to achieve 'ab' state, then we implement pop
operation.
• Push all operations to Undo stack.
• When undo is called, pop operations from Undo stack and push it
b to Redo stack.
a c
• When redo is called, pop operations from Redo stack and push it
to Undo stack.
When function call happens, previous variables gets stored in the Stack
3) Recursion
• The recursion means that the function is

calling itself again.
• To maintain the previous states, the compiler Returning value from base case to Caller function
creates a system stack in which all the

previous records of the function are
maintained.
4) DFS(Depth First Search)
This search is implemented on a Graph, and Graph uses the stack data
structure.
5) Backtracking
• Exploring a route from home to Bennett

University.
• If we are moving in a particular path, and we

realize that we come on the wrong way.
• In order to come at the beginning of the path to

explore another path, we use the stack data
structure.
6) Memory management • When the function is created, all its variables are assigned in the
stack memory. When the function completed its execution, all
the variables assigned in the stack are released.
• The memory is assigned in the contiguous memory blocks. The

memory is known as stack memory as all the variables are
assigned in a function call stack memory.
• The memory size assigned to the program is known to the

compiler.
7) Expression Conversion Ex- 2 + 4
Stack is also used for expression conversion. This is one of the most
important applications of stack.
Ex- 2 + 4 → 24+
(Infix Notation) (Postfix Notation)
Next Week Readings
• Polish Notation
• Infix-Postfix Conversion
• Postfix Evaluation
Any Queries?
Office MCub311
Discussion Time: 3-5 PM
Mob: +91-8586968801

DS Week 7 Lecture Stacks by Dr Gaurav

Uploaded by

Copyright:

Available Formats

DS Week 7 Lecture Stacks by Dr Gaurav

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS Week 7 Lecture Stacks by Dr Gaurav

Uploaded by

Copyright:

Available Formats

Subject: Data Structure

Using C++ (CSET243)

Stack and Its Applications

• Understood the Linked List and Operations

• One side open another side closed

• Works on LIFO (Last in First Out) or FILO (First

in Last Out) order to Insert or Delete the element.

• Top is a variable which contains the position of the

top-most element in the stack.

• Stack can be defined as a container in which insertion

(push) and deletion (pop) can be done from the one

end known as the top of the stack.

int stack[n], n = 100, top = -1;

pop() − (Deletion) Removing an element from the stack.

Push Operation Algorithm:

Push Operation Algorithm: void push(int val, int n)

Pop Operation Algorithm:

int stack[n], n = 100, val=10, top = -1;

Pop Operation Algorithm: void pop()

isFull(): It determines whether the stack is full or not.'

isEmpty () Operation Algorithm: isFull () Operation Algorithm:

Print “Underflow” Print “Overflow”

Step-2 : Stop Step 2: Stop

• count(): It returns the total number of elements available in a stack.

• change(): It changes the element at the given position.

• display() or Traverse(): It prints all the elements available in the stack.

} Errors occurs in a program.

• First, we push all the characters of the string in a stack

• After pushing all the characters, we start taking out the

• To perform Undo and Redo operations, we need 2

• Push all operations to Undo stack.

• Push all operations to Undo stack.

• The recursion means that the function is

creates a system stack in which all the

• Exploring a route from home to Bennett

• If we are moving in a particular path, and we

• In order to come at the beginning of the path to

• The memory is assigned in the contiguous memory blocks. The

• The memory size assigned to the program is known to the

You might also like