Stack

A Stack is linear data structure. A stack is a list of elements in which an element may be
inserted or deleted only at one end, called the top of the stack. Stack principle is LIFO (last
in, first out). Which element inserted last on to the stack that element deleted first from the
stack.

As the items can be added or removed only from the top i.e. the last item to be added to a
stack is the first item to be removed.

Applications:
– Program execution stack (handle function call)
– Evaluating postfix expressions
– Undo/Redo operations
– Conversion from infix to postfix expressions
– To solve some problems
• Reversing any strings
• To check palindromes
• Tower of Hanoi

Operations on stack:

The two basic operations associated with stacks are:

1. Push
2. Pop

While performing push and pop operations the following test must be conducted on the stack.

a) Stack is empty or not

b) b) stack is full or not

Assistant Professor-Nivedita Pandey, BIT Durg Page 1

1. Push: Push operation is used to add new elements in to the stack. At the time of addition
first check the stack is full or not. If the stack is full it generates an error message "stack
overflow".

2. Pop: Pop operation is used to delete elements from the stack. At the time of deletion first
check the stack is empty or not. If the stack is empty it generates an error message "stack
underflow".

All insertions and deletions take place at the same end, so the last element added to the stack
will be the first element removed from the stack. When a stack is created, the stack base
remains fixed while the stack top changes as elements are added and removed.

The most accessible element is the top and the least accessible element is the bottom of the
stack.

Representation of Stack (or) Implementation of stack:

The stack should be represented in two ways:

1. Stack using array

2. Stack using linked list

1. Stack using array:

Let us consider a stack with 6 elements capacity. This is called as the size of the stack. The
number of elements to be added should not exceed the maximum size of the stack. If we
attempt to add new element beyond the maximum size, we will encounter a stack overflow
condition. Similarly, you cannot remove elements beyond the base of the stack. If such is the
case, we will reach a stack underflow condition.

1. push():When an element is added to a stack, the operation is performed by push(). Below

Figure shows the creation of a stack and addition of elements using push().

Initially top=-1, we can insert an element in to the stack, increment the top value i.e
top=top+1. We can insert an element in to the stack first check the condition is stack is full
or not. i.e top>=size-1. Otherwise add the element in to the stack.

Assistant Professor-Nivedita Pandey, BIT Durg Page 2

Algorithm for PUSH Operation

[Link](): When an element is taken off from the stack, the operation is performed by pop().
Below figure shows a stack initially with three elements and shows the deletion of elements
using pop().

We can insert an element from the stack, decrement the top value i.e top=top-1. We can
delete an element from the stack first check the condition is stack is empty or not. i.e
top==-1. Otherwise remove the element from the stack.

Algorithm for POP Operation

Assistant Professor-Nivedita Pandey, BIT Durg Page 3

2. Stack using Linked List: We can represent a stack as a linked list. In a stack push and pop
operations are performed at one end called top. We can perform similar operations at one end
of list using top pointer. The linked stack looks as shown in figure.

Converting and evaluating Algebraic expressions

An algebraic expression is a legal combination of operators and operands. Operand is the
quantity on which a mathematical operation is performed. Operand may be a variable like x,
y, z or a constant like 5, 4, 6 etc. Operator is a symbol which signifies a mathematical or
logical operation between the operands. Examples of familiar operators include +, -, *, /, ^
etc.
An algebraic expression can be represented using three different notations. They are infix,
postfix and prefix notations:

Infix: It is the form of an arithmetic expression in which we fix (place) the arithmetic
operator in between the two operands.
Example: A + B

Prefix: It is the form of an arithmetic notation in which we fix (place) the arithmetic
operator before (pre) its two operands. The prefix notation is called as polish notation.
Example: + A B

Postfix: It is the form of an arithmetic expression in which we fix (place) the arithmetic
operator after (post) its two operands. The postfix notation is called as suffix notation and is
also referred to reverse polish notation.
Example: A B +

Assistant Professor-Nivedita Pandey, BIT Durg Page 4

Example:

Infix Prefix Postfix

1 A+B +AB AB+
2 A+B-C - +ABC AB+C-
3 (A+B)*(C-D) AB+CD-* *+AB-CD
4 A$B*C-D+E/F/(G+H) + - * $ ABCD / / EF AB $ C * D – EF / GH
+ GH +/+
5 ( (A+B) * C - (D - E)) $ $ - * + ABC – DE + AB + C * DE - - FG +
(F+G) FG $
6 A – B / ( C * D $ E) - A / B * C $ DE ABCDE $ * / -

Conversion from infix to postfix:

Algorithm

We consider five binary operations: +, -, *, / and $ or ↑ (exponentiation). For these binary

operations, the following in the order of precedence (highest to lowest):

Assistant Professor-Nivedita Pandey, BIT Durg Page 5

Assistant Professor-Nivedita Pandey, BIT Durg Page 6
Example 2:

Evaluation of postfix expression:

The postfix expression is evaluated easily by the use of a stack.

1. When a number is seen, it is pushed onto the stack;

2. When an operator is seen, the operator is applied to the two numbers that are popped from the stack
and the result is pushed onto the stack.
3. When an expression is given in postfix notation, there is no need to know any precedence rules; this
is our obvious advantage.

Assistant Professor-Nivedita Pandey, BIT Durg Page 7

Recursion
A function is recursive if a statement in the body of the function calls itself. Recursion is the
process of defining something in terms of itself. For a computer language to be recursive, a
function must be able to call itself.

For example, let us consider the function FACTORIAL() shown below, which computers the
factorial of an integer

A non-recursive or iterative version for finding the factorial is as follows:

The operation of the non-recursive version is clear as it uses a loop starting at 1 and ending at
the target value and progressively multiplies each number by the moving product.

When a function calls itself, new local variables and parameters are allocated storage on the
stack and the function code is executed with these new variables from the start. A recursive
call does not make a new copy of the function. Only the arguments and variables are new. As
each recursive call returns, the old local variables and parameters are removed from the stack
and execution resumes at the point of the function call inside the function.

When writing recursive functions, you must have a exit condition somewhere to force the
function to return without the recursive call being executed. If you do not have an exit
condition, the recursive function will recurse forever until you run out of stack space and
indicate error about lack of memory, or stack overflow.

Differences between recursion and iteration:

 Both involve repetition.

 Both involve a termination test.
 Both can occur infinitely.

Assistant Professor-Nivedita Pandey, BIT Durg Page 8

Factorial of a given number:

The operation of recursive factorial function is as follows: Start out with some natural
number N (in our example, 5). The recursive definition is:

n = 0, 0! = 1 Base Case
n > 0, n ! = n * (n - 1)! Recursive Case

Recursion Factorials:

5! =5 * 4! = 5 *___ = ____ factr(5) = 5 * factr(4) = _

4! = 4 *3! = 4 *___ = ___ factr(4) = 4 * factr(3) = __
3! = 3 * 2! = 3 * ___ = ___ factr(3) = 3 * factr(2) = __
2! = 2 * 1! = 2 * ___ = ___ factr(2) = 2 * factr(1) = __
1! = 1 * 0! = 1 * __ = __ factr(1) = 1 * factr(0) = __
0! = 1 factr(0) = __

5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 =120

We define 0! to equal 1, and we define factorial N (where N > 0), to be N * factorial (N-1).
All recursive functions must have an exit condition that is a state when it does not recurse
upon itself. Our exit condition in this example is when N = 0.

Assistant Professor-Nivedita Pandey, BIT Durg Page 9

Assistant Professor-Nivedita Pandey, BIT Durg Page 10
Fibonacci sequence Problem:

A Fibonacci sequence starts with the integers 0 and 1. Successive elements in this sequence
are obtained by summing the preceding two elements in the sequence. For example, third
number in the sequence is 0 + 1 = 1, fourth number is 1 + 1= 2, fifth number is 1 + 2 = 3 and
so on. The sequence of Fibonacci integers is given below:

0 1 1 2 3 5 8 13 21 . . . . . . . . .

Algorithm:

Assistant Professor-Nivedita Pandey, BIT Durg Page 11

Towers of Hanoi:

Assistant Professor-Nivedita Pandey, BIT Durg Page 12

Algorithm:

Input:4

Assistant Professor-Nivedita Pandey, BIT Durg Page 13