UNIT 3

What is Stack?

● Stack is an ordered list of the same type of elements.

● It is a linear list where all insertions and deletions are permitted only at one end of the list.
● Stack is a LIFO (Last In First Out) structure.
● In a stack, when an element is added, it goes to the top of the stack.
Definition
“Stack is a collection of similar data items in which both insertion and deletion operations
are performed based on LIFO principle”.

There are two basic operations performed in a Stack:

1. Push()
2. Pop()

1. Push() function is used to add or insert new elements into the stack.

2. Pop() function is used to delete or remove an element from the stack.

● When a stack is completely full, it is said to be Overflow state and if stack is completely
empty, it is said to be Underflow state.
● Stack allows operations at one end only. Stack behaves like a real life stack, for example, in
a real life, we can remove a plate or dish from the top of the stack only or while playing a
deck of cards, we can place or remove a card from top of the stack only.
Similarly, here also, we can only access the top element of a stack.
● According to its LIFO structure, the element which is inserted last, is accessed first.

Implementation of Stack

The above diagram represents a stack insertion operation. In a stack, inserting and deleting
of elements are performed at a single position which is known as, Top.

Insertion operation can be performed using Push() function. New element is added at top of
the stack and removed from top of the stack, as shown in the diagram below:

An element is removed from top of the stack. Delete operation is based on LIFO principle.
This operation is performed using a Pop() function. It means that the insertion and deletion
operations are performed at one end i.e at Top.

Following table shows the Position of Top which indicates the status of stack:

Position of Top Status of Stack

-1 Stack is empty.
0 Only one element in a stack.
N-1 Stack is full.
N Stack is overflow. (Overflow state)

Stack using Array

Stack can be implemented using one-dimensional array. One-dimensional array is used to

hold elements of a stack. Implementing a stack using array can store fixed number of data
values. In a stack, initially top is set to -1. Top is used to keep track of the index of the top
most element.

Stack can be defined using array as follows:

typedef struct stack

{
int element [MAX];
int top;
}stack;

In the above code snippet, MAX is a constant and can store defined number of elements.
When the value of top becomes MAX – 1 after a series of insertion, it means that stack is
full.
 ❖ 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 overflow when we try to insert an element into a completely filled stack
therefore, our main function must always avoid stack overflow condition.

PUSH Operation
1.Check Stack Overflow?
If TOP=MAX-1
Print “Stack Overflow”
Exit
2.Read Item
3.Set TOP =TOP+1
4.SET STACK[TOP]=Item
5.Exit

Pop : Removing an element from the stack

1.Stack Underflow?

If TOP=-1 then

Print Stack Underflow

Exit

2.Repeat steps 3 to 5 until TOP>=0

3.set Item=STACK[TOP]

4.Set TOP=TOP-1
5.Write deleted Item

6.Exit

Applications of Stack
1.Recursion
2.Expression evaluations and conversions
3.Parsing
4.Browsers
5.Editors
6.Tree Traversals

Following are the applications of stack:

1. Expression Evaluation
2. Expression Conversion
i. Infix to Postfix
ii. Infix to Prefix
iii. Postfix to Infix
iv. Prefix to Infix
3. Backtracking
4. Memory Management

Expression Representation
There are three popular methods used for representation of an expression:
1. Conversion of Infix to Postfix
Algorithm for Infix to Postfix

Step 1: Consider the next element in the input.

Step 2: If it is operand, display it.

Step 3: If it is opening parenthesis, insert it on stack.

Step 4: If it is an operator, then

If stack is empty, insert operator on stack.
If the top of stack is opening parenthesis, insert the operator on stack
If it has higher priority than the top of stack, insert the operator on stack.
Else, delete the operator from the stack and display it, repeat Step 4.
Step 5: If it is a closing parenthesis, delete the operator from stack and display them until
an opening parenthesis is encountered. Delete and discard the opening parenthesis.

Step 6: If there is more input, go to Step 1.

Step 7: If there is no more input, delete the remaining operators to output.

Example: Suppose we are converting 3*3/(4-1)+6*2 expression into postfix form.

Following table shows the evaluation of Infix to Postfix:
2. Infix to Prefix

Algorithm for Infix to Prefix Conversion:

Step 1: Insert “)” onto stack, and add “(” to end of the A .

Step 2: Scan A from right to left and repeat Step 3 to 6 for each element of A until the stack is
empty .

Step 3: If an operand is encountered, add it to B .

Step 4: If a right parenthesis is encountered, insert it onto stack .

Step 5: If an operator is encountered then,

a. Delete from stack and add to B (each operator on the top of stack) which has
same or higher precedence than the operator.
b. Add operator to stack.

Step 6: If left parenthesis is encountered then ,

a. Delete from the stack and add to B (each operator on top of stack until a left
parenthesis is encountered).
b. Remove the left parenthesis.

Step 7: Exit
So, the Infix Expression is (e+f-g)* (h-e)/(s-h+o)
Q:What is recursion? What are disadvantages of recursion?
Recursion is the ability of the procedure either to call itself or calling to some other
procedure which may result in call to the original procedure. Two important
condition/requirements are:
1. There must be a decision criteria that stops the further call to the procedure called
base criteria.
2. Each time procedure calls itself, either directly or indirectly, it must be near to the
solution.
Disadvantages of recursion

What is Queue?
● Queue is a linear data structure where the first element is inserted from
one end called REAR and deleted from the other end called as FRONT.

● Front points to the beginning of the queue and Rear points to the end of
the queue.

● Queue follows the FIFO (First - In - First Out) structure.

● According to its FIFO structure, element inserted first will also be removed
first.

● In a queue, one end is always used to insert data (enqueue) and the other
is used to delete data (dequeue), because queue is open at both its ends.

● The enqueue() and dequeue() are two important functions used in a queue.

Operations on Queue
Following are the basic operations performed on a Queue.

Operations Description
enqueue() This function defines the operation for adding an element into queue.
dequeue() This function defines the operation for removing an element from queue.
init() This function is used for initializing the queue.
Front Front is used to get the front data item from a queue.
Rear Rear is used to get the last item from a queue.

Queue Implementation

● Array is the easiest way to implement a queue. Queue can be also

implemented using Linked List or Stack.
● In the above diagram, Front and Rear of the queue point at the first index
of the array. (Array index starts from 0).

● While adding an element into the queue, the Rear keeps on moving ahead
and always points to the position where the next element will be inserted.
Front remains at the first index.
Types of queue
1.Circular Queue
2.Priority Queue
3.DEQUEUE(Double Ended Queue)
Insert / Enqueue Operation
Whenever an element is inserted into queue, priority queue inserts the item
according to its order. Here we're assuming that data with high value has low priority.

Remove / Dequeue Operation

Whenever an element is to be removed from queue, queue get the element using
item count. Once element is removed. Item count is reduced by one.

Infix to Postfix
1. A*B+C
2. (A+B)*(C/D)
3. A*(B*C+D*E)+F
4. (A+B)*C+(D-E)/F+G