What is a Stack?

A Stack is a linear data structure that follows the LIFO (Last-In-First-

Out) principle. Stack has one end, whereas the Queue has two ends
(front and rear). It contains only one pointer top pointer pointing to the
topmost element of the stack. Whenever an element is added in the stack,
it is added on the top of the stack, and the element can be deleted only
from the stack. In other words, a stack can be defined as a container
in which insertion and deletion can be done from the one end
known as the top of the stack.

Some key points related to stack

o It is called as stack because it behaves like a real-world stack, piles of
books, etc.
o A Stack is an abstract data type with a pre-defined capacity, which means
that it can store the elements of a limited size.
o It is a data structure that follows some order to insert and delete the
elements, and that order can be LIFO or FILO.

Working of Stack
Stack works on the LIFO pattern. As we can observe in the below figure
there are five memory blocks in the stack; therefore, the size of the stack
is 5.

Suppose we want to store the elements in a stack and let's assume that
stack is empty. We have taken the stack of size 5 as shown below in
which we are pushing the elements one by one until the stack becomes
full.
Since our stack is full as the size of the stack is 5. In the above cases, we
can observe that it goes from the top to the bottom when we were
entering the new element in the stack. The stack gets filled up from the
bottom to the top.

When we perform the delete operation on the stack, there is only one way
for entry and exit as the other end is closed. It follows the LIFO pattern,
which means that the value entered first will be removed last. In the
above case, the value 5 is entered first, so it will be removed only after
the deletion of all the other elements.

Standard Stack Operations

The following are some common operations implemented on the
stack:

o push(): When we insert an element in a stack then the operation is known

as a push. If the stack is full then the overflow condition occurs.
o pop(): When we delete an element from the stack, the operation is known
as a pop. If the stack is empty means that no element exists in the stack,
this state is known as an underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.

PUSH operation
The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the
stack is empty.
o When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new
position of the top.
 o The elements will be inserted until we reach the max size of the stack.

POP operation
The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is
empty.
o If we try to delete the element from the empty stack, then
the underflow condition occurs.
o If the stack is not empty, we first access the element which is pointed by
the top
o Once the pop operation is performed, the top is decremented by 1,
i.e., top=top-1.
Applications of Stack
The following are the applications of the stack:

o Balancing of symbols: Stack is used for balancing a symbol. For

example, we have the following program:

1. int main()
2. {
3. cout<<"Hello";
4. cout<<"javaTpoint";
5. }

As we know, each program has an opening and closing braces; when the
opening braces come, we push the braces in a stack, and when the
closing braces appear, we pop the opening braces from the stack.
Therefore, the net value comes out to be zero. If any symbol is left in the
stack, it means that some syntax occurs in a program.

o String reversal: Stack is also used for reversing a string. For example,
we want to reverse a "javaTpoint" string, so we can achieve this with the
help of a stack.
First, we push all the characters of the string in a stack until we reach the
null character.
 After pushing all the characters, we start taking out the character one by
one until we reach the bottom of the stack.
o UNDO/REDO: It can also be used for performing UNDO/REDO operations.
For example, we have an editor in which we write 'a', then 'b', and then 'c';
therefore, the text written in an editor is abc. So, there are three states, a,
ab, and abc, which are stored in a stack. There would be two stacks in
which one stack shows UNDO state, and the other shows REDO state.
If we want to perform UNDO operation, and want to achieve 'ab' state,
then we implement pop operation.
o Recursion: The recursion means that the function is calling itself again.
To maintain the previous states, the compiler creates a system stack in
which all the previous records of the function are maintained.
o DFS(Depth First Search): This search is implemented on a Graph, and
Graph uses the stack data structure.
o Backtracking: Suppose we have to create a path to solve a maze
problem. If we are moving in a particular path, and we realize that we
come on the wrong way. In order to come at the beginning of the path to
create a new path, we have to use the stack data structure.
o Expression conversion: Stack can also be used for expression
conversion. This is one of the most important applications of stack. The list
of the expression conversion is given below:
o Infix to prefix
o Infix to postfix
o Prefix to infix
o Prefix to postfix
Postfix to infix

o Memory management: The stack manages the memory. The memory is

assigned in the contiguous memory blocks. The memory is known as stack
memory as all the variables are assigned in a function call stack memory.
The memory size assigned to the program is known to the compiler. When
the function is created, all its variables are assigned in the stack memory.
When the function completed its execution, all the variables assigned in
the stack are released.

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the
operations regarding the stack are performed using arrays. Lets see how
each operation can be implemented on the stack using array data
structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push
operation. Push operation involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory
location.
2. Add element at the position of incremented top. This is referred to as
adding new element at the top of the stack.

Stack is overflown when we try to insert an element into a completely

filled stack therefore, our main function must always avoid stack overflow
condition.

Algorithm:

1. begin
2. if top = n then stack full
3. top = top + 1
4. stack (top) : = item;
5. end

Time Complexity : o(1)

Deletion of an element from a stack (Pop operation)

Deletion of an element from the top of the stack is called pop operation.
The value of the variable top will be incremented by 1 whenever an item
is deleted from the stack. The top most element of the stack is stored in
an another variable and then the top is decremented by 1. the operation
returns the deleted value that was stored in another variable as the result.

The underflow condition occurs when we try to delete an element from an

already empty stack.

Algorithm :

1. begin
2. if top = 0 then stack empty;
 3. item := stack(top);
4. top = top - 1;
5. end;

Time Complexity : o(1)

Linked list implementation of stack

Instead of using array, we can also use linked list to implement stack.
Linked list allocates the memory dynamically. However, time complexity
in both the scenario is same for all the operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-

contiguously in the memory. Each node contains a pointer to its
immediate successor node in the stack. Stack is said to be overflown if the
space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field.
Lets discuss the way in which, each operation is performed in linked list
implementation of stack.

Adding a node to the stack (Push operation)

Adding a node to the stack is referred to as push operation. Pushing an
element to a stack in linked list implementation is different from that of an
array implementation. In order to push an element onto the stack, the
following steps are involved.

1. Create a node first and allocate memory to it.

2. If the list is empty then the item is to be pushed as the start node of the
list. This includes assigning value to the data part of the node and assign
null to the address part of the node.
3. If there are some nodes in the list already, then we have to add the new
element in the beginning of the list (to not violate the property of the
stack). For this purpose, assign the address of the starting element to the
address field of the new node and make the new node, the starting node
of the list.

Time Complexity : o(1)

Deleting a node from the stack (POP
operation)
Deleting a node from the top of stack is referred to
as pop operation. Deleting a node from the linked list
implementation of stack is different from that in the array
implementation. In order to pop an element from the stack, we need
to follow the following steps :

1. Check for the underflow condition: The underflow condition

occurs when we try to pop from an already empty stack. The stack
will be empty if the head pointer of the list points to null.
2. Adjust the head pointer accordingly: In stack, the elements are
popped only from one end, therefore, the value stored in the head
pointer must be deleted and the node must be freed. The next node
of the head node now becomes the head node.

Time Complexity : o(n)

Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of
the linked list organized in the form of stack. For this purpose, we
need to follow the following steps.

1. Copy the head pointer into a temporary pointer.

2. Move the temporary pointer through all the nodes of the list and
print the value field attached to every node.

Time Complexity : o(n)

Array Stack

It is a data structure that consists of a It is an abstract data type that consists of

collection of elements that are identified by a collection of elements that implements
their indexes, where the first index is the LIFO (Last In First Out) principle.
available at index 0.

It is a collection of elements of the same It is a collection of elements of different

data type. data types.

It provides random-access, i.e., read and As it implements LIFO so it has limited-

write operations would be performed to any access. We can access the only top
element at any position through their element of the stack using push and pop
indexes. operations.

It is rich in methods or operations like The limited operations can be performed

sorting, traversing, reverse, push, pop, etc. on a stack like push, pop, peek, etc.

It is a data type. It is an abstract data type.

It is used when we know all the data to be It is good to use when there are dynamic
processed and require constant changes at processes. It is useful when we do not
any element. know how much data would be required.

Let's look at the differences between the Stack and Array in a

tabular form.

APPLICATION OF STACK: PREFIX AND POSTFIX

EXPRESSIONS-

Convert Infix to Postfix notation

An infix and postfix are the expressions. An expression consists of
constants, variables, and symbols. Symbols can be operators or
parenthesis. All these components must be arranged according to a set of
rules so that all these expressions can be evaluated using the set of rules.

Examples of expressions are:

5+6

A-B

(P * 5)
What is infix notation?
When the operator is written in between the operands, then it is known
as infix notation. Operand does not have to be always a constant or a
variable; it can also be an expression itself.

For example,

(p + q) * (r + s)

In the above expression, both the expressions of the multiplication

operator are the operands, i.e., (p + q), and (r + s) are the operands.

Syntax of infix notation is given below:

<operand> <operator> <operand>

Operators Symbols

Parenthesis ( ), {}, [ ]

Exponents ^

Multiplication and Division *, /

Addition and Subtraction +,-

The first preference is given to the parenthesis; then next preference is

given to the exponents. In the case of multiple exponent operators, then
the operation will be applied from right to left.

For example:

2^2^3 = 2 ^ 8

= 256

Postfix Expression
The postfix expression is an expression in which the operator is written
after the operands. For example, the postfix expression of infix notation
( 2+3) can be written as 23+.

Some key points regarding the postfix expression are:

o In postfix expression, operations are performed in the order in which they

have written from left to right.
 o It does not any require any parenthesis.
o We do not need to apply operator precedence rules and associativity
rules.

Algorithm to evaluate the postfix expression

o Scan the expression from left to right until we encounter any operator.
o Perform the operation
o Replace the expression with its computed value.
o Repeat the steps from 1 to 3 until no more operators exist.

o Let's understand the above algorithm through an example.

o Infix expression: 2 + 3 * 4

o We will start scanning from the left most of the expression. The
multiplication operator is an operator that appears first while
scanning from left to right. Now, the expression would be:

o Expression = 2 + 34*

o = 2 + 12

o Again, we will scan from left to right, and the expression would be:

o Expression = 2 12 +

o = 14

o example.
o Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Input Expression Stack Postfix Expression

K K

+ +

L + KL

- - K L+

M - K L+ M

* -* K L+ M
N -* KL+MN

+ + K L + M
K L + M N* -

( +( K L + M N *-

O +( KL+MN*-O

^ +(^ K L + M N* - O

P +(^ K L + M N* - O P

) + K L + M N* - O P ^

* +* K L + M N* - O P ^

W +* K L + M N* - O P ^ W

/ +/ K L + M N* - O P ^ W *

U +/ K L + M N* - O P ^W*U

/ +/ K L + M N* - O P ^W*U/

V +/ KL + MN*-OP^W*U/V

* +* KL+MN*-OP^W*U/V/

T +* KL+MN*-OP^W*U/V/T

+ + KL+MN*-OP^W*U/V/T*
KL+MN*-OP^W*U/V/T*+

Q + KL+MN*-OP^W*U/V/T*Q

KL+MN*-OP^W*U/V/T*+Q+

o The final postfix expression of infix expression(K + L - M*N + (O^P)

* W/U/V * T + Q) is KL+MN*-OP^W*U/V/T*+Q+.
Convert infix to prefix notationWhat is Prefix
notation?
A prefix notation is another form of expression but it does not require
other information such as precedence and associativity, whereas an infix
notation requires information of precedence and associativity. It is also
known as polish notation. In prefix notation, an operator comes before
the operands. The syntax of prefix notation is given below:

<operator> <operand> <operand>

For example, if the infix expression is 5+1, then the prefix expression
corresponding to this infix expression is +51.

If the infix expression is:

a*b+c

*ab+c

+*abc (Prefix expression)

Conversion of Infix to Prefix using Stack

K + L - M * N + (O^P) * W/U/V * T + Q

If we are converting the expression from infix to prefix, we need first to

reverse the expression.

The Reverse expression would be:

Q + T * V/U/W * ) P^O(+ N*M - L + K

To obtain the prefix expression, we have created a table that consists of

three columns, i.e., input expression, stack, and prefix expression. When
we encounter any symbol, we simply add it into the prefix expression. If
we encounter the operator, we will push it into the stack.

Input expression Stack Prefix expression

Q Q
+ + Q

T + QT

* +* QT

V +* QTV

/ +*/ QTV

U +*/ QTVU

/ +*// QTVU

W +*// QTVUW

* +*//* QTVUW

) +*//*) QTVUW

P +*//*) QTVUWP

^ +*//*)^ QTVUWP

O +*//*)^ QTVUWPO

( +*//* QTVUWPO^

+ ++ QTVUWPO^*//*

N ++ QTVUWPO^*//*N

* ++* QTVUWPO^*//*N

M ++* QTVUWPO^*//*NM

- ++- QTVUWPO^*//*NM*

L ++- QTVUWPO^*//*NM*L
+ ++-+ QTVUWPO^*//*NM*L

K ++-+ QTVUWPO^*//*NM*LK

QTVUWPO^*//*NM*LK+-++

The above expression, i.e., QTVUWPO^*//*NM*LK+-++, is not a final

expression. We need to reverse this expression to obtain the prefix
expression.
Difference between Recursion and
Iteration
A program is called recursive when an entity calls itself. A program is call
iterative when there is a loop (or repetition).

Property Recursion Iteration

A set of instructions repeatedly

Definition Function calls itself. executed.

Application For functions. For loops.

Through base case, When the termination condition

where there will be no for the iterator ceases to be
Termination function call. satisfied.

Used when code size

needs to be small, and Used when time complexity
time complexity is not an needs to be balanced against
Usage issue. an expanded code size.

Code Size Smaller code size Larger Code Size.

Very high(generally Relatively lower time

Time exponential) time complexity(generally
Complexity complexity. polynomial-logarithmic).

What is Recursion?
The process in which a function calls itself directly or indirectly is called
recursion and the corresponding function is called a recursive function. Using
a recursive algorithm, certain problems can be solved quite easily. Examples
of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder
Tree Traversals, DFS of Graph, etc. A recursive function solves a particular
problem by calling a copy of itself and solving smaller subproblems of the
original problems. Many more recursive calls can be generated as and when
required. It is essential to know that we should provide a certain case in
order to terminate this recursion process. So we can say that every time the
function calls itself with a simpler version of the original problem.
Need of Recursion
Recursion is an amazing technique with the help of which we can reduce the
length of our code and make it easier to read and write. It has certain
advantages over the iteration technique which will be discussed later. A task
that can be defined with its similar subtask, recursion is one of the best
solutions for it. For example; The Factorial of a number.
Properties of Recursion:
 Performing the same operations multiple times with different inputs.
 In every step, we try smaller inputs to make the problem smaller.
 Base condition is needed to stop the recursion otherwise infinite
loop will occur.
A Mathematical Interpretation
Let us consider a problem that a programmer has to determine the sum of
first n natural numbers, there are several ways of doing that but the simplest
approach is simply to add the numbers starting from 1 to n. So the function
simply looks like this,
approach(1) – Simply adding one by one
f(n) = 1 + 2 + 3 +……..+ n
but there is another mathematical approach of representing this,
approach(2) – Recursive adding
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
There is a simple difference between the approach (1) and approach(2) and
that is in approach(2) the function “ f( ) ” itself is being called inside the
function, so this phenomenon is named recursion, and the function
containing recursion is called recursive function, at the end, this is a great
tool in the hand of the programmers to code some problems in a lot easier
and efficient way.
What is the base condition in recursion?
In the recursive program, the solution to the base case is provided and the
solution to the bigger problem is expressed in terms of smaller problems.

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
In the above example, the base case for n < = 1 is defined and the larger
value of a number can be solved by converting to a smaller one till the base
case is reached.
What is the difference between direct and indirect recursion?
A function fun is called direct recursive if it calls the same function fun. A
function fun is called indirect recursive if it calls another function say fun_new
and fun_new calls fun directly or indirectly. The difference between direct
and indirect recursion has been illustrated in Table 1.
// An example of direct recursion
void directRecFun()
{
// Some code....

directRecFun();

// Some code...
}

// An example of indirect recursion

void indirectRecFun1()
{
// Some code...

indirectRecFun2();

// Some code...
}
void indirectRecFun2()
{
// Some code...

indirectRecFun1();

// Some code...
}
What is the difference between tailed and non-tailed recursion?
A recursive function is tail recursive when a recursive call is the last thing
executed by the function. Please refer tail recursion article for details.

How memory is allocated to different function calls in recursion?

When any function is called from main(), the memory is allocated to it on the
stack. A recursive function calls itself, the memory for a called function is
allocated on top of memory allocated to the calling function and a different
copy of local variables is created for each function call. When the base case
is reached, the function returns its value to the function by whom it is called
and memory is de-allocated and the process continues.
What are the disadvantages of recursive programming over iterative
programming?
Note that both recursive and iterative programs have the same problem-
solving powers, i.e., every recursive program can be written iteratively and
vice versa is also true. The recursive program has greater space
requirements than the iterative program as all functions will remain in the
stack until the base case is reached. It also has greater time requirements
because of function calls and returns overhead.
Moreover, due to the smaller length of code, the codes are difficult to
understand and hence extra care has to be practiced while writing the code.
The computer may run out of memory if the recursive calls are not properly
checked.
What are the advantages of recursive programming over iterative
programming?
Recursion provides a clean and simple way to write code. Some problems
are inherently recursive like tree traversals, Tower of Hanoi, etc. For such
problems, it is preferred to write recursive code. We can write such codes
also iteratively with the help of a stack data structure. For example
refer Inorder Tree Traversal without Recursion , Iterative Tower of Hanoi .

Fibonacci Series
Fibonacci series generates the subsequent number by adding two
previous numbers. Fibonacci series starts from two numbers − F0 & F1.
The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.
Fibonacci series satisfies the following conditions −
Fn = Fn-1 + Fn-2
Hence, a Fibonacci series can look like this −
F8 = 0 1 1 2 3 5 8 13
or, this −
F8 = 1 1 2 3 5 8 13 21
For illustration purpose, Fibonacci of F8 is displayed as −
Fibonacci Iterative Algorithm
First we try to draft the iterative algorithm for Fibonacci series.
Procedure Fibonacci(n)
declare f0, f1, fib, loop

set f0 to 0
set f1 to 1

display f0, f1

for loop ← 1 to n

fib ← f0 + f1
f 0 ← f1
f1 ← fib

display fib
end for

end procedure

Fibonacci Recursive Algorithm

Let us learn how to create a recursive algorithm Fibonacci series. The
base criteria of recursion.
START
Procedure Fibonacci(n)
 declare f0, f1, fib, loop

set f0 to 0
set f1 to 1

display f0, f1

for loop ← 1 to n

fib ← f0 + f1
f 0 ← f1
f1 ← fib

display fib
end for

END

Tower of Hanoi
1. It is a classic problem where you try to move all the disks from one peg
to another peg using only three pegs.

2. Initially, all of the disks are stacked on top of each other with larger
disks under the smaller disks.

3. You may move the disks to any of three pegs as you attempt to
relocate all of the disks, but you cannot place the larger disks over smaller
disks and only one disk can be transferred at a time.

This problem can be easily solved by Divide & Conquer algorithm