Notesale: Turn your study into money

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.

Buy These NotesPreview