Cover every piece of content that could be asked in an exam
Have a solid structure for your notes that makes sense ,Evidence you will need for your exam, Examples that help your understanding of an idea.
In linear data structure, elements will have a linear relationship with the adjacent
elements.
Example: Stack, Queue, Linked list
STACK:
Stack is an ordered collection of heterogeneous elements, where insertion and deletion
are performed only at one end(top of the stack).
Insertion of elements in stack is called PUSH
Deletion of elements in stack is called POP
Stack follows LIFO(Last In First Out) strategy. (i.e) The element which is pushed last
will be popped out first
Stack act as a Static Data structure if it is implemented using arrays
Stack act as a Dynamic Data structure if it is implemented using Linked list
Initially top = -1, which implies that stack is empty
Stack[4]
Stack[3]
Stack[2]
Stack[1]
Stack[0]
Representation of stack of size 5 as an array
OPERATIONS OF STACK
i) Push operation:
Push operation is used to insert the element at top of the stack.
Before performing push operation, it is necessary to check the stackfull condition,
because if a stack is full, push operation cannot be performed.
If Stack is not full, (i.e) there is some space available in stack, then, top pointer is
incremented by one and then the element will be pushed at the top of the stack.
Algorithm:
Push(element)
if (top = = size – 1)
Write “Stack is full. Can’t perform push”
else
top = top + 1
stack [ top ] = element
end if
Consider the size of stack is 3. Initially top = -1.
1
,CST35 / Data Structures UNIT - II
Consider, We need to push the element 10 into the stack
o When we check the stack, we find that stack is not full. So we increment top by 1.
Hence top = 0. We store the element 10 in stack[0]
Stack[2]
Stack[1]
top Stack[0] 10
We need to push the element 15 into the stack
o When we check the stack, we find that stack is not full. So we increment top by 1.
Hence top = 1. We store the element 15 in stack[1]
Stack[2]
top Stack[1] 15
Stack[0] 10
We need to push the element 20 into the stack
o When we check the stack, we find that stack is not full. So we increment top by 1.
Hence top = 2. We store the element 20 in stack[2]
top Stack[2] 20
Stack[1] 15
Stack[0] 10
We need to push the element 25 into the stack. When we check the stack, we find that
stack is full.(i.e) top = = size – 1 becomes true. So we can’t push the element 25 unless
some of the elements from the stack is popped.
POP operation:
Pop operation deletes the element at top of the stack.
Before performing pop operation, it is necessary to check the stack empty condition,
because if a stack is empty, pop operation cannot be performed.
If Stack is not empty, (i.e) there is some values are available in stack, then, element at top
of stack is popped out and top pointer is decremented by 1.
Algorithm:
Pop( )
if (top = = – 1)
Write “Stack is empty. Can’t perform pop”
else
element = stack[top]
top = top -1
return(element)
end if
2
,CST35 / Data Structures UNIT - II
If pop operation is to be done, element at top of stack 20 is popped and top is
decremented by 1
Stack[2]
top Stack[1] 15
Stack[0] 10
If pop operation is to be done, element at top of stack 15 is popped and top is
decremented by 1
Stack[2]
Stack[1]
top Stack[0] 10
If pop operation is to be done, element at top of stack 10 is popped and top is
decremented by 1
Stack[2]
Stack[1]
Stack[0]
top -1
Since top is -1, stack is empty. Hence further pop operation cannot be done.
Display:
Display operation displays the element in the stack
If there is no elements in stack, element can’t be displayed
If there are elements in stacks, it displays the elements from the top position of the stack
till the zeroth position
display( )
if top = = -1
Write “ stack is empty. No elements to display”
else
for i = top to 0
Write stack [ i ]
end for
end if
APPLICATIONS OF STACK:
Book in a table
Shipment in cargo
Plate on a tray
Towers of hanoi
Conversion of infix expression to postfix expression
Evaluation of arithmetic expression
o An arithmetic expression consists of operands and operators
o Notations: Infix => operand operator operand
o prefix => operator operand operand
o Postfix => operand operand operator
3
, CST35 / Data Structures UNIT - II
CONVERSION OF INFIX EXPRESSION TO POSTFIX EXPRESSION:
Algorithm for converting infix to postfix:
While(tokens are available) // token may be a alphabet or number or operator or ‘(‘ or ‘)’
ch = read(token)
if(ch = = ‘ ( ‘ )
push(ch)
break
end if
if(ch = = ‘ ) ‘ )
pop all operators until ‘(‘ is encountered
break
end if
if ( ch = = operand)
output(ch) (or) Write the operand in postfix expression
else
if ( priority(ch) <= priority( stack[top])
element = pop( )
output(element)
push(ch)
else
push(ch)
end while
write postfix expression
Example 1
Convert the infix expression (a * b) to postfix
Operator stack Input token Postfix expression
Empty
(
(
a a
(
* * a
(
* b ab
(
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller pragatimanimarane. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.49. You're not tied to anything after your purchase.
