STACK

STACK→
A stack is list of elements in which an element may be inserted or deleted only at one end,
called the top of stack i.e the last element insert will be deleted first and this technique is
known as last in first out (LIFO).
EX: STACK of dishes, stack of folded towels, stack of coins.
Special terminology is used for two basic operations associated with stack.
“PUSH” is the term used to insert an element into a stack.
‘POP” is the term used to delete an element from a stack.

B B B

A A A A A

[A] [B] [C] [D] [E] [F]

Abstract data type (ADTs)→

A Stack ADT (Abstract Data Type) is a collection of elements in which insertion and deletion
operations are performed at only one end, called the top of the stack.

It follows the LIFO principle — Last In, First Out.

Operation on stack→
The Stack ADT defines the following standard operations:
1. new()→ creates new stack
2. Push(S,O)→ insert object O onto top of stack S.
3. Pop(S)→ remove the top object of stack if stack is empty, an error occur.
4. Top(S)→ returns the top object of stack, without removing it.
5. Size(S)→ returns the number of objects in stack S.
6. Isempty(S): Boolean-indicate if stack is empty.
Stack as an ADT focuses on what operations are performed, not how they are implemented.
Implementation can be done using arrays or linked lists, but the ADT defines only the behavior
and interface of the stack.
P a g e 1 | 14
 STACK
QUESTION→
1. State the principle of stack with basic operation.[2 MARK]
2. Define stack what are the basic operation perform on it.[4 marks]
Array representation of stack→
Stack may be represented in the computer in various ways by means of a one-way list or linear
array. Each of our stacks will be maintained by a linear array STACK, a pointer variable TOP,
which contains the location of top element of stack, and a variable MAXSTK which gives the
maximum number of elements that can be held by the stack. The condition TOP=0 or
TOP=NULL will indicate that stack is empty.
Figure below shows an array representation of stack
Since TOP=3, the stack has three elements, XXX, YYY and ZZZ and since MAXSTK=6, there is
room for 3 more items in the stack

XXX YYY ZZZ

1 2 3 4 5 6
\

MAXSTK
TOP=3

In pushing operation, check first whether there is room in the stack for new item, if not than we
have the condition Known as overflow. Analogously in executing the procedure POP, check
whether there is an element in the stack to be deleted, if not then we have condition known as
underflow.
In push operation the value of top is increased by 1. i.e TOP=TOP+1.
In POP operation the value of top is decreased by 1i.e TOP=TOP-1
ALGORTHM:-
PUSH( STACK, TOP, MAXSTK, ITEM)
1. If TOP=MAXSTK then
Print :OVERFLOW and return
2. Set TOP:=TOP+1 [increased Top by 1]
P a g e 2 | 14
 STACK
3. Set STACK[TOP]:= ITEM [Inserts ITEM in a new TOP position]
4. Return
POP( STACK, TOP, ITEM)
This procedure deletes the top element of stack and assign it to variable ITEM
1. [ stack has an item to be removed]
IF TOP=0 then
Print: UNDERFLOW and Return
2. Set ITEM:= STACK[TOP] [assigns TOP element to ITEM]
3. Set TOP:=TOP-1 [Decreases TOP by 1]
4. Return
QUESTION→
1. Define the term overflow and underflow with respect to stack. [2 mark]
2. Write a procedure to push an element on stack, Also give meaning of stack overflow
term. [4 mark].
3. Write a menu driven ‘C’ program for implementation stack. Using array.[6 mark]
Application of stack→
1. Polish notation.
2. Recursion
3. Expression conversion and evaluation
4. Parsing
5. Function call
Expression Representation→
a) Infix x+y operator between operands.
b) Prefix +xy operator before operands.
c) Postfix xy+ operator after operands.
Example
Infix –x+y*z
Prefix +x*yz
Postfix xyz*+
a) Evalution of an infix expression (polish notation) expression→
Infix expressions are evaluated left to right but operator precedence must be taken into
account. To evalute x+y*z, y and z will be multiplied first and then it will be added to x.
b) Evaluate of a prefix (polish notation) expression

P a g e 3 | 14
 STACK
+5*32 find an operator from right to left and perform the operation.
+5*32 [(+) first operator]
Therefore 3*2 are multiplied, expression becomes +56.
First operator is + and therefore 5 and 6 are added expression become 11
c) Evaluation of postfix(reverse polish ) expression
5 3 2 *+
1. Find the first operator from left to right and perform the operation.
2. First operator is * and therefore 3 and 2 are multiplied expression becomes 56+.
3. Next operator is + and therefore 5 and 6 are added. Expression becomes 11.
d) Evalution of a postfix expression using a stack →
Given expression

GIVEN EXPRESSON:- 6,5,3,+,9,*+ stack

First token is operand, push 6 on stack

Initially stack is empty

5,3,+,9,*+ stack

First token is operand, push 6 on stack 6

3,+,9,*+ stack

Next token is and operator push 5 on stack 5

P a g e 4 | 14
 STACK
+,9,*+ stack
3

Next token is and operator push 3 on stack 5

9,*+ stack

Next token is and operator pop two operands 3 and 5 add then 8

and push the result on the stack 6

*+ stack
9

Push 9 on stack 8

+ stack

Next token is an operator , pop two operands 9 and 8, multiply 72

Them and push the result on stack 6

stack

Next token is an operator , pop two operands 72 and 6, add

Them and push the result on stack 78

Final result
P a g e 5 | 14
6
 STACK
QUESTION →
1. Evaluate the following postfix expression and show stack after every step in tabular
form
Given A=5, B=6, C=2, D=12, E=4 and expression is ABC+*DE. [4 mark]
2. Explain any two application of stack [4 mark]
3. Evaluate following postfix expression. A:- 6,2,3,+,5,3,8,2,+,+,*,2,^,3,+.[6 mark]
4. Consider the following arithmetic expression P written in postfix notation. Translate it
in infix notation and evaluate.[6 mark]
P: 12,7,3,-,/,2,1,5,+,*,+
A postfix expression can be converted to infix from by scanning it from left to right. We used
brackets[] to denote a partial translation.
Step 1: 12,[7-3],/,2,1,5,+,*,+
Step 2: [12/(7-3)],2,1,5.+,*,+
Step 3: [12/(7-3)],2,[1+5],*,+
Step 4: [12/(7-3)],(2*(1+5)),+
Step 5: 12/(7-3)+(2*(1+5))
Value of expression = 12/(7-3)+(2*(1+5))
= 12/4+2*6
=3+12
=15 (page 6.47)
Evalution of prefix expression→
[scanned from right to left]
Evaluated the following prefix expression using stack for A=16, B=2, C=3, D=10 and E=4 show
step by step the content of stack.
Prefix expression = -+/A^BC*DE*AC
INPUT := -+/A^BC*DE*AC STACK

P a g e 6 | 14
 STACK
INPUT := -+/A^BC*DE*A STACK

PUSH
3

INPUT := -+/A^BC*DE* STACK

16 PUSH

INPUT := -+/A^BC*DE STACK

EVALUTE
48

INPUT := -+/A^BC*D STACK

PUSH
4

48

INPUT := -+/A^BC* STACK

PUSH
10

48
P a g e 7 | 14
 STACK
INPUT := -+/A^BC STACK

EVALUTE
40

48

INPUT := -+/A^B STACK

3 PUSH

40

48

INPUT := -+/A^ STACK

2
PUSH
3

40

48

INPUT := -+/A STACK

EVALUATE 8

40

48

INPUT := -+/ STACK

16
PUSH
8

40

48

P a g e 8 | 14
 STACK
INPUT := -+ STACK

EVALUATE 2

40

48

INPUT := - STACK

EVALUATE
42

48

INPUT := NULL STACK

EVALUATE
-6

Value of expression=-6

QUESTION→
1. Explain any two application of stack. [4 mark]

Consider the following infix expression Q:

Q((A+B)*D)^(E-F)
Use algorithm to translate Q into its equivalent postfix expression P. [6 mark]

P a g e 9 | 14
 STACK
Solution:= first push a left parenthesis onto stack and then add a right parenthesis to the end of
Q to obtain
Q:((A+B)*D)^(E-F))

SYMBOL STACK EXPRESSION

( (( -----
( ((( ------
A ((( A
+ (((+ A
B (((+ AB
) (( AB+
* ((* AB+
D ((* AB+D
) ( AB+D*
^ (^ AB+D*
( (^( AB+D*
E (^( AB+D*E
- (^(- AB+D*E
F (^(- AB+D*EF
) (^ AB+D*EF-
) EMPTY AB+D*EF-^
Postfix expression: AB+D*EF-^
Convert following expression Q into postfix from Q:- (A+B)*C-D/E*(F/G). show stack
representation push “(” onto stack and add “)” to end of Q. [6 mark]

Symbol Stack expression

( (( ---------
A (( A
+ ((+ A
B ((+ AB
) ( AB+
* (* AB+
C (* AB+C
- (- AB+C *
D (- AB+C *D
/ (-/ AB+C *D
E (-/ AB+C *DE
* (-* AB+C *DE /
( (-*( AB+C *DE /
F (-*( AB+C *DE /F
/ (-*(/ AB+C *DE /F
G (-*(/ AB+C *DE /FG
P a g e 10 | 14
 STACK
) (-* AB+C *DE /FG /
) EMPTY AB+C *DE /FG /*-

POSTFIX EXPRESSION :- ABC*+DE/FG/*-

QUESTION→
1) (A+B)*D+E/(F+A*D)+C [ANS→ AB+D*EFAD*+/+C+]
2) A*(B+C)/D-G [ANS→ ABC+*D/G-]
Evolution of infix to prefix →
Rules:-
1. Reverse the given infix expression
2. Change ( to ) and ) to (.
3. Evaluate infix to postfix expression using algorithm
4. Reverse the expression
Question :- (A+B^C)*D+E^5
Solution:- 5^E+D*)C^B+A(
5^E+D*(C^B+A)

SYMBOL SCANNES STACK EXPRESION

5 ------ 5
^ ^ 5
E ^ 5E
+ + 5E
D + 5E^D
* +* 5E^D
( +*( 5E^D
C +*( 5E^DC
^ +*(^ 5E^DC
B +*(^ 5E^DCB
+ +*( 5E^DCB^
A +*( 5E^DCB^A
) +* 5E^DCB^A
--------- EMPTY 5E^DCB^A*+

REVERSE FINAL EXPRESSION: +*A^BCD^E5

PERFIX EXPRESSION IS:- +*A^BCD^E5

P a g e 11 | 14
 STACK

QUESTION→
(1) Consider the following arithmetic expression written in postfix notation:
P: 12,7,3,-,1,2,+,5,+,+
1. Translate P into its equivalent infix expression
2. Evaluate the infix expression[6 mark]
Solution:
12, [7-3], [1+2],5,+,*,+
12, [7-3], [(1+2)+5],*,+
[12(7-3)]*[(1+2)+5]+
12+(7-3)*(1+2+5)
(2) Convert the following arithmetic expression P written in postfix notation into infix
P: 5,6,2,+,*,12,4,/,-
Also evaluate P for final value
=5,(6+2),*,(12/4),-
=[5*(6+2)]-(12/4)
=*(6+2)-(12/4)
Operator moved between the two operation of group
Evaluate : result 37

Recursion→
Recursion is defined as to call the procedure by itself.
Suppose P is a procedure containing either a call statement to itself or a call statement to a
second procedure that may eventually result in a call statement back to original procedure P.
Then P is called recursive procedure.
So that the program will not continue to run indefinitely, a recursive procedure must have the
following two properties.
1. There must be certain criteria called base criteria, for which the procedure does not call
itself.
2. Each time the procedure does called itself (directly or indirectly) it must be closer to
base criteria.
Factorial function (example)→
4!=4*3!
3*2!

P a g e 12 | 14
 STACK
2*1!
1*0!=1
N!=?
= n*(n-1)!
=(n-1) * (n-2)!
=(n-2)*(n-3)!
0!=1
(factorial function)
1. If n=0 then n!=1
2. If n>0 then n!=n(n-1)!
Observe this definition of n! is recursive, since it refers to itself when it uses (n-1)! However (a)
the value of n! is explicitly given when n=0 (thus 0 is base value)

Algorithm: FACTORIAL (Recursive Method)

This algorithm calculates N! using recursion.

Algorithm FACTORIAL (FACT, N):

1. If N=0, then
→ Set FACT:=1 and Return.
2. Call FACTORIAL(FACT, N−1)
3. Set FACT:=N×FACT
4. Return.

Fibonacci Sequence

The celebrated Fibonacci sequence (usually denoted by F0, F1, F2,…) is as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…

That is,

• F0=0 and F1=1

• Each succeeding term is the sum of the two preceding terms.

Examples:

P a g e 13 | 14
 STACK
F9=34+55=89 F10=55+89=144

Formal Definition (Definition 6.2: Fibonacci Sequence)

Fn= {n if n=0 or n=1

{Fn−2+Fn−1 if n>1

• (a) The base values are F0=0 and F1=1.

• (b) For n>1, the value of Fn is defined in terms of smaller values of n.

This is a recursive definition, since it refers to itself.

Procedure 6.10: FIBONACCI(FIB, N)

This procedure calculates Fn and returns the value in the first parameter FIB.

Algorithm: FIBONACCI (FIB, N)

1. If N=0 or N=1, then

o Set FIB:= N, and Return.
2. Call FIBONACCI(FIBA, N – 2).
3. Call FIBONACCI(FIBB, N – 1).
4. Set FIB := FIBA + FIBB.
5. Return.

Question →
1. what is recursion? Write a “C” program for multiplication of natural number using
recursion. [4 mark]

P a g e 14 | 14