Data Structures UNIT II

UNIT II : Stacks- Operations on stack, Insert, Delete, update, Arithmetic

Expressions: Evaluation of a postfix expression, transforming infix

expression into postfix, Recursion – Fibonacci series- Queues-

Representation of Queues-operations on queues, Insert, Delete, and Update

STACK

DEFINITION

 A STACK is a list of elements in which an element may be inserted or

deleted at one end called the TOP of the stack.

 TOP is the pointer that points the top element in the stack.

 The elements are removed from a stack in the reverse order of that in

which they were inserted into stack.

Stack Representation
The following diagram depicts a stack and its operations −

 A stack can be implemented by means of Array, Structure, Pointer, and Linked

List.

 Stack can either be a fixed size one or it may have a sense of dynamic resizing.
Which is the first element to delete?
Stack operations

A stack is used for the following two primary operations −

 push() − Pushing (storing) an element on the stack.

 pop() − Removing (accessing) an element from the stack.

Stack operations

 When data is PUSHed onto stack, To use a stack efficiently, we need to check the
status of stack as well. For the same purpose, the following functionality is added to
stacks −

 peek() − get the top data element of the stack, without removing it.

 isFull() − check if stack is full.

 isEmpty() − check if stack is empty.

 The pointer that represents the top of the stack, hence named top.

 The top pointer provides top value of the stack without actually removing it.
Status of Stack
Push Operation

The process of putting a new data element onto stack is known as a Push

Operation. Push operation involves a series of steps −

Step 1 − Checks if the stack is full.

Step 2 − If the stack is full, produces an error and exit.

Step 3 − If the stack is not full, increments top to point next empty space.

Step 4 − Adds data element to the stack location, where top is pointing.

Step 5 − Returns success.

Algorithm for PUSH Operation

A simple algorithm for Push operation can be derived as follows −

begin procedure push: stack, data

if top = Max // isfull() Print stack is full

return

endif

top ← top + 1

stack[top] ← data

end procedure
Algorithm for PUSH Operation
Implementation of this algorithm in C, is very easy. See the following code −Example
void push(int data)
{
if(!isFull())
{
top = top + 1;
stack[top] = data;
}
else
{
printf(”Could not insert data, Stack is full.\n”);
}
}
Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In
an array implementation of pop() operation, the data element is not actually removed,
instead top is decremented to a lower position in the stack to point to the next value. But in
linked-list implementation, pop() actually removes data element and de _allocates memory
space.
A Pop operation may involve the following steps −
Step 1 − Checks if the stack is empty.
Step 2 − If the stack is empty, produces an error and exit.
Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
Step 4 − Decreases the value of top by 1.
Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack
if stack is empty // isEmpty()
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
Algorithm for Pop Operation
Program for Pop Operation

Implementation of this algorithm in C, is as follows −

int pop(int data)

if(!isempty()) {

data = stack[top];

top = top - 1;

return data;

} else {printf(“Could not retrieve data, Stack is empty.\n”;);

Update Operation

Modifying the content from the stack, is known as a Update Operation.

An Update operation may involve the following steps −

Step 1 − Checks if the stack is empty.

Step 2 − If the stack is empty, produces an error and exit.

Step 3 − If the stack is not empty, Modify the ith data element from the  top of the

stack.

Step 4 − Returns success

Update Operation

Modifying the content from the stack, is known as a Update Operation.

An Update operation may involve the following steps −

Step 1 − Checks if the stack is empty.

Step 2 − If the stack is empty, produces an error and exit.

Step 3 − If the stack is not empty, Modify the ith data element from the  top of the

stack.

Step 4 − Returns success

A simple algorithm for Update operation can be derived as follows −
begin procedure Update: stack
if stack is empty // isEmpty()
return
endif
stack[top- i + 1] ← data // Change ith element from the top of the stack
end procedure
Arithmetic expression

The way to write arithmetic expression is known as a notation. An arithmetic

expression can be written in three different but equivalent notations, i.e., without

changing the essence or output of an expression. These notations are −

  Infix Notation

  Prefix (Polish) Notation

  Postfix (Reverse-Polish) Notation

These notations are named as how they use operator in expression.

Infix Notation

 We write expression in infix notation, e.g. a - b + c, where operators are used in-

between operands.

 It is easy for us humans to read, write, and speak in infix notation but the same

does not go well with computing devices.

 An algorithm to process infix notation could be difficult and costly in terms of

time and spaceconsumption.

Prefix Notation

 In this notation, operator is prefixed to operands,

 i.e. operator is written ahead of operands.

 For example, +ab. This is equivalent to its infix notation a + b.

 Prefixnotation is also known as Polish Notation.

Postfix Notation

 In this notation style, the operator is postfixed to the operands.

 i.e., the operator is written after the operands.

 For example, ab+. This is equivalent to its infix notation a + b.

 This notation style is known as Reversed Polish Notation.

The following table briefly tries to show the difference in all three notations −
Sr.No. Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+

2 (a + b) ∗ c ∗+abc ab+c∗

3 a ∗ (b + c) ∗a+bc abc+∗

4 a/b+c/d +/ab/cd ab/cd/+

5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

Evaluation of a postfix expression

A postfix expression is a collection of operators and operands in which the operator is placed

after the operands. That means, in a postfix expression the operator follows the operands.

Postfix Expression has following general structure...

Operand1 Operand2 Operator

Example
Postfix Expression Evaluation using Stack Data Structure

A postfix expression can be evaluated using the Stack data structure. To evaluate a postfix expression

using Stack data structure we can use the following steps...

1.Read all the symbols one by one from left to right in the given Postfix Expression

2.If the reading symbol is operand, then push it on to the Stack.

3.If the reading symbol is operator (+ , - , * , / etc.,), then perform TWO pop operations and store the two

popped oparands in two different variables (operand1 and operand2). Then perform reading symbol

operation using operand1 and operand2 and push result back on to the Stack.

4.Finally, perform a pop operation and display the popped value as final result.
Algorithm postfixEvaluation(postfix)

1. Initialize an empty stack.

2. Scan postfix expression from left to right.

3. If the scanned character is an operand, then push it to the stack.

4. If the scanned character is an operator, then pop operands from the stack. Perform

the operation and push the result back to the stack.

5. Repeat step 2 till all characters of postfix are read.

6. In the end, the stack will contain only 1 value, that is the answer to the postfix

expression.
Algorithm postfixEvaluation(postfix)

Input: Postfix expression to evaluate. push res into the stack

Output: Answer after evaluating postfix form.
else if ch is an operand, then
Begin
add ch into the stack
for each character ch in the postfix expression, do

if ch is an operator ⨀ , then
done

a := pop first element from stack return element of stack top

b := pop second element from the stack End

res := b ⨀ a
Postfix Expression Evaluation using Stack Data Structure

Example

Consider the following Expression...

Postfix Expression Evaluation using Stack Data Structure

Example

Consider the following Expression...

Example Consider the following Expression...2 * 5 * (3 + 6 ) / 5 - 2
Example Consider the following Expression...5 * (3 * 2 + 8)
Convertion of infix expression into a postfix expression

Given an infix expression, convert it to the postfix

 Input: A*(B*C+D*E)+F
expression. Assume that the infix expression is a string of
 Output: ABC*DE*+*F+

tokens without any whitespace.

 Input:
For example,
(A+B)*C+(D-E)/F+G
 Input: A*B+C  Output: AB+C*DE-F/+G+

 Output: AB*C+

 Input: (A+B)*(C/D)

 Output: AB+CD/*
Convertion of infix expression into a postfix expression

 Operator precedence - This refers to the priority given to each operator in an expression.
 Associativity - If two operators have the same precedence, associativity is used to determine
the order of evaluation.
 Rules for the conversion from infix to postfix expression

 Initially we have a infix expression given to us to convert to postfix notation.

 The infix notation is parsed from left to right, and then converted to postfix.

 Assume initially the postfix expression is empty, and we will fill the postfix

expression out with the following steps:

 If we have an opening parenthesis "(", we push it into the stack.

 If we have an operand, we append it to our postfix expression.

 If we have a closing parenthesis ")" we keep popping out elements from the top of the stack and append them to
our postfix expression until we encounter an opening parenthesis. We pop out the left parenthesis without
appending it.

 If we encounter an operator:-

 4.1. If the operator has higher precedence than the one on top of the stack , push it in to the stack.

 4.2. If the operator has lower or equal precedence than the one on top of the stack, we keep popping out the one on
top of the stack and appending it to the postfix expression. And we push the new one in to the stack.

 When the last token of infix expression has been scanned, we pop the remaining elements from stack and append
them to our postfix expression.*
Input:

A*(B*C+D*E)+F

Output:

ABC*DE*+*F+
Recursion

 Recursion is a a function calls itself.

 Recursion is a programming pattern that is useful in situations when a task can be

naturally split into several tasks of the same kind, but simpler.
Recursion

Properties

A recursive function can go infinite like a loop. To avoid infinite running of recursive

function, there are two properties that a recursive function must have −

Base criteria − There must be at least one base criteria or condition, such that, when

this condition is met the function stops calling itself recursively.

Progressive approach − The recursive calls should progress in such a way that each

time a recursive call is made it comes closer to the base criteria.

Recursion

Implementation

Many programming languages implement recursion by means of stacks. Generally,

whenever a function (caller) calls another function (callee) or itself as callee, the caller

function transfers execution control to the callee. This transfer process may also

involve some data to be passed from the caller to the callee.

Recursion
Recursion - 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 −
Recursion - 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 −
Recursion - Fibonacci Series