Search for notes by fellow students, in your own course and all over the country.

Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.

My Basket

You have nothing in your shopping cart yet.

Title: STACK(DSA)
Description: Basic to advance coverage of Stack concept in DSA and practice questions.

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above


Shashank Yadav (KIET-Ghaziabad)

7
...

 There are two basic operations associated with stacks:
1
...
Pop- to delete an element from a stack
5
4
3
2
1

MAX

S

5
4
3
2
1

←TOP

MAX

12
S
Push(12)
i
...


←TOP
12
S
Pop()
iii
...

1
...
Linked-list representation

7
...
TOP is a variable which stores the position of top
element of stack
...
1
...

PUSH(S, MAX, TOP, ITEM)
Where S is a stack of MAX indexes, TOP is a variable which stores the position of top
element of stack S, ITEM is an element to be inserted
...
If (TOP== MAX) then
a
...
Return
2
...
S[TOP]= ITEM
4
...
1
...

POP (S, MAX, TOP)
Where S is a stack of MAX indexes, TOP is a variable which stores the position of top
element of stack S
...
If (TOP== 0) then
// check underflow condition
a
...
Return
2
...
TOP=TOP-1
4
...
1
...

#include ...
h>
#define MAX 100
struct stack
{
int data[MAX];
int top;
};
void Push(struct stack*, int);
int Pop(struct stack*);
void main()
{
struct stack s;
int choice, item;
19 | P a g e

Shashank Yadav (KIET-Ghaziabad)

clrscr();
s
...
Push\n2
...
Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter one number to push ");
scanf("%d",&item);
Push(&s,item);
break;
case 2: item= Pop(&s);
printf("\n Popped element is %d",item);
}
}while(choice!=3);
}
void Push(struct stack *s, int item)
{
if(s->top==MAX-1)
printf("\nStack is Full");
else
{
s->top++;
s->data[s->top]=item;
printf("\n%d element has been pushed",item);
}
}
int Pop(struct stack *s)
{
int item;
if(s->top==-1)
{
printf("\nStack is empty");
return(0);
}
else
{
item=s->data[s->top];
s->top=s->top-1;
return(item);
}
}
20 | P a g e

Shashank Yadav (KIET-Ghaziabad)

7
...
2
...
E
...
A+B, C*D, A+(B*C)
...

 Polish notation, named after the Polish mathematician Jan Lukasiewicz, refers the
notation in which the operator symbol is placed before its two operands
...
g
...
This is called prefix notation
...

 Reverse Polish Notation refers to the notation in which the operator symbol is placed
after its two operands
...
g
...
This is called postfix notation
...
2
...

1
...

2
...

If an element is an operator Θ
a
...
B= Pop another element from stack
c
...
Push C into stack
4
...
2
...

21 | P a g e

STACK
5
5, 6
5, 6, 2
5, 8
40
40, 12
40, 12, 4
40, 3
37

Shashank Yadav (KIET-Ghaziabad)

7
...
4 Transforming Infix Expressions into Postfix Expressions
...
This algorithm finds the
equivalent postfix expression P
1
...

2
...
If an operand is encountered, add it to P
...
If a left parenthesis is encountered, push it onto STACK
...
If an operator Θ is encountered, then:
a
...
Add Θ to STACK
...
If a right parenthesis is encountered, then:
a
...

b
...

7
...

7
...
5 Consider the following arithmetic infix expression
Q: A + (B * C - (D / E ^ F) * G) * H
Convert this infix into postfix
...

Symbol
A
+
(
B
*
C
(
D
/
E


F
)

Stack
(
(+
(+(
(+(
(+(*
(+(*
(+((+(-(
(+(-(
(+(-(/
(+(-(/
(+(-(/^
(+(-(/^
(+(-

22 | P a g e

Expression P
A
A
A
AB
AB
ABC
A B C*
A B C*
ABC *D
ABC *D
ABC *DE
ABC *DE
ABC *DEF
ABC *DEF^/

Shashank Yadav (KIET-Ghaziabad)

*
G
)
*
H
)

(+(- *
(+(-*
(+
(+ *
(+ *

ABC *DEF^/
ABC *DEF^/G
ABC *DEF^/G*ABC *DEF^/G*ABC *DEF^/G*-H
ABC *DEF^/G*-H*+

7
...
6 Infix to Prefix Transformation:
Algorithm:
1
...

2
...

3
...

4
...

5
...

6
...
Check if priority of operator in stack is greater than priority of incoming operator
then Pop from STACK and place it in prefix expression
...

b
...

7
...

8
...

7
...
7 Convert the infix expression (a+b)*(c-d) into equivalent prefix form
...

((a+b)*(c-d))
Now reverse the string ) ) d – c ( * ) b + a ( (
Symbol

Stack

)
)
d
c
(
*
)
b
23 | P a g e

)
))
))
)))))
)*
)*)
)*)

Expression P

d
d
dc
dcdcdcdc–b

Shashank Yadav (KIET-Ghaziabad)

+
a
(
(

dc–b
dc–ba
dc–b a+
dc–b a+*

)*)+
)*)+
)*

Reverse the string

*+ab–cd

7
...
8 Postfix to Infix Transformation:
Algorithm:
1
...

2
...

3
...
Then
pop second operand OP2 and concatenate “(” before OP2
...

7
...
9 Convert the postfix expression a b + c d - * into equivalent infix expression
...
2
...
Reverse the prefix expression
...
Read this reversed prefix expression from left to right one element at a time and repeat
step 3 and 4
...
If element is operand, then Push it onto the STACK
...
If element is operator then Pop the first operand OP1 concatenate “(” before OP1
...
Thus an infix expression
(OP1 Θ OP2) gets formed
...

7
...
11 Convert the prefix expression * + a b – c d into equivalent infix expression
...
3 Recursion:
 Recursion is an important concept in computer science
...

 If one algorithm calls itself, such algorithm is called recursive algorithm
...

 Each time the procedure does call itself (directly or indirectly), it must be closer
to the base criteria
...
3
...

Implicit stack is a special kind of stack used by runtime memory environment
...

This type of stack is used implicitly by the compiler
...

E
...
Recursive program for Factorial of a number uses this stack
...
3
...

FACTORIAL(N)
Where N is a positive integer number
...
If N== 1 then return (1)
2
...
h>
#include ...
g
...
3
...

 This concept was introduced by David H
...
Warren
...

 Previous factorial function is not example of tail recursion, because Multiplication is
pending operation after recursion
...

#include ...
h>
int Factorial(int n, int f)
{
if (n==1)
return(f);
else
return(Factorial(n-1, n*f));
}
void main( )
{
int n;
clrscr( );
printf(“Enter one number for finding out factorial ”);
scanf(“%d”,&n);
printf(“Factorial of %d is %d”, n, Factorial(n, 1));
getch( );
}
7
...
2 Algorithm for generating Nth term for Fibonacci series
...
We want Nth term of Fibonacci series
...
If (N==1) return(0)
2
...
Return(FIBO(N-2) + FIBO(N-1))
7
...
3 Removal of Recursion:
 Removal of recursion from a function means making it iterative by making use of control
statements
...

#include ...
h>
int Factorial(int n)
{
int i, fact=1;
for(i=2;i<=n;i++)
fact= fact*i;
return(fact);
}
void main( )
27 | P a g e

Shashank Yadav (KIET-Ghaziabad)

{
int n;
clrscr( );
printf(“Enter one number for finding out factorial ”);
scanf(“%d”,&n);
printf(“Factorial of %d is %d”, n, Factorial(n));
getch( );
}

7
...
The object of the game is to move the disks from peg A to peg C
using peg B as an auxiliary
...
Only one disk may be moved at a time
...

2
...

A

B

Initial setup of Towers of Hanoi with N=3

Solution of Tower of Hanoi with N=3
...

2
...

4
...

6
...


Move top disk from peg A to peg C
...

Move top disk from peg C to peg B
...

Move top disk from peg B to peg A
...

Move top disk from peg A to peg C
...

A

B

C

B

C

(1) A→ C

(a) Initial
A

B

A

C

(4) A→ C

A

B

A

B

C

(2) A→ B
C

(5) B→ A

A

B

C

(6) B→ C

A

B

C

(3) C→ B
A

B

C

(7) A→ C

Algorithm:
TOWER (N, BEG, AUX, END)
This procedure gives a recursive solution to the Towers of Hanoi problem for N disks
...
If N==1 then
a
...
Return
2
...
Write BEG END
...
TOWER(N-1, AUX, BEG, END)
5
Title: STACK(DSA)
Description: Basic to advance coverage of Stack concept in DSA and practice questions.