UNIT-II

Stacks:
Stacks, Stacks using Arrays
Stacks using dynamic arrays
Evaluation of Expressions – Evaluating Postfix Expression,
Evaluation of Expressions -Infix to Postfix
Queues:
Queues ADT
Queues operations
Circular Queues
Queues Applications
WHAT IS 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.
• Operations on stack:The two basic operations associated with stacks
are:
1.Push
2.Pop
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
message is "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
message "stack underflow".
•All insertions and deletions elements take place at the same end(called
top of stack), so the last element added to the stack will be the first element
removed from 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 Arrays
• 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.
 Stack using array can represent with push() and pop(),peek() and Display()
operations
 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.
• Other wise add the element in to the stack.
void push() Algorithm: Procedure for push():
{
int x;
if(top >= n-1) Step 1: START
{ Step 2: if top>=size-1 then
printf("\n\nStack Overflow..");
} Write “ Stack is Overflow”
else Step 3: Otherwise
{ 3.1: read data value ‘x’
printf("\n\nEnter data: ");
scanf("%d", &x); 3.2: top=top+1;
top = top + 1;
stack[top] =x; 3.3: stack[top]=x;
printf("\n\nData Pushed into the Step 4: END
stack");
}
}
Pop():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 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.
• We can delete an element from the stack, decrement the top value i.e top=top-1.

void pop() Algorithm: procedure pop():

{ Step 1: START
if(top == -1)
Step 2: if top == -1 then
{
printf(“Stack is Underflow”); Write “Stack is
} Underflow”
else Step 3: otherwise
{ 3.1: print “deleted
printf(“Delete data element”
%d”,stack[top]);
top=top-1;
3.2: top=top-1;
}
} Step 4: END
Peek():Visiting each element of the stack (Peek operation)
• Peek operation involves returning the element which is present at the top of the
stack without deleting it.
• Underflow condition can occur if we try to return the top element in an already
empty stack.
void peek() Algorithm: procedure peek():
{ Step 1: START
if(top == -1)
{
Step 2: if top == -1 then
printf(“Stack is Underflow”); Write “Stack is
} Underflow”
else Step 3: otherwise
{ 3.1: ITEM=stack[top];
printf(“Topmost element
%d”,stack[top]);
3.2: print “topmost
} element(ITEM) of stack”
}
Step 4: END
Display():
• This operation performed display the elements in the stack.
• We display the element in the stack check the condition is stack is empty or not i.e
top = = -1.
• Otherwise display the list of elements in the stack.
void display() Algorithm: procedure Display( ):
{
if(top = = -1) Step 1: START
{ Step 2: if top = = -1 then
printf(“Stack is Underflow”); Write “Stack is
} Underflow”
else Step 3: otherwise
{ 3.1: print “Display
printf(“Display elements elements are”
are:); 3.2: for top to 0
for(i=top;i>=0;i--) Print ‘stack[i]’
printf(“%d”,stack[i]); Step 4: END
}
}
C Program for STACK Using Arrays
#include<stdio.h>
#include<stdlib.h>
int stack[100],choice,n,top,x,i;
void push(void);
void peek(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.PEEK\n\t 3.POP\n\t 4.DISPLAY\n\t 5.EXIT");
while(choice!=6)
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice) case 4:
{ {
case 1: display();
{ break;
push(); }
break; case 5:
} {
case 2: printf("\n\t EXIT POINT ");
{ break;
peek(); }
break; default:
}
{
printf ("\n\t Please Enter a Valid
case 3:
Choice(1/2/3/4):");
{
}
pop();
break; }
} }
return 0;
}
• }
 void peek()
void push() {
{ if(top==-1)
if(top==n-1) {
printf("\n\t Stack is under flow");
{ }
printf("\n\tSTACK is over flow"); else
{
}
printf("\n\t The top of the stack(peek) elements is:
else %d",stack[top]);
{ }}
void pop()
printf(" Enter a value to be {
pushed:"); if(top==-1)
scanf("%d",&x); {
printf("\n\t Stack is under flow");
top++;
}
stack[top]=x; else
} {
printf("\n\t The popped elements is: %d",stack[top]);
} top--;
}}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK:\n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice:");
}
else
{
printf("\n The STACK is empty");
}
}
Applications of Stack
• Function calls and recursion: When a function is called, the current state of the program is pushed
onto the stack. When the function returns, the state is popped from the stack to resume the previous
function’s execution.
• Undo/Redo operations: The undo-redo feature in various applications uses stacks to keep track of
the previous actions. Each time an action is performed, it is pushed onto the stack. To undo the action,
the top element of the stack is popped, and the reverse operation is performed.
• Expression evaluation: Stack data structure is used to evaluate expressions in infix, postfix, and
prefix notations. Operators and operands are pushed onto the stack, and operations are performed
based on the stack’s top elements.
• Ex: Infix to prefix, Infix to postfix, Prefix to infix, prefix to postfix, postfix to infix
• Browser history: Web browsers use stacks to keep track of the web pages you visit. Each time you
visit a new page, the URL is pushed onto the stack, and when you hit the back button, the previous
URL is popped from the stack.
• Balanced Parentheses: Stack data structure is used to check if parentheses are balanced or not. An
opening parenthesis is pushed onto the stack, and a closing parenthesis is popped from the stack. If
the stack is empty at the end of the expression, the parentheses are balanced.
• Backtracking Algorithms: The backtracking algorithm uses stacks to keep track of the states of the
problem-solving process. The current state is pushed onto the stack, and when the algorithm
backtracks, the previous state is popped from the stack.
Application of Stack in real life:
• CD/DVD stand.
• Stack of books in a book shop.
• Call center systems.
• Undo and Redo mechanism in text editors.
• The history of a web browser is stored in the form of a stack.
• Call logs, E-mails, and Google photos in any gallery are also stored
in form of a stack.
• YouTube downloads and Notifications are also shown in LIFO
format(the latest appears first ).
• Allocation of memory by an operating system while executing a
process.
Advantages of Stack:
• Easy implementation: Stack data structure is easy to implement using arrays or
linked lists, and its operations are simple to understand and implement.
• Efficient memory utilization: Stack uses a contiguous block of memory, making it
more efficient in memory utilization as compared to other data structures.
• Fast access time: Stack data structure provides fast access time for adding and
removing elements as the elements are added and removed from the top of the stack.
• Helps in function calls: Stack data structure is used to store function calls and their
states, which helps in the efficient implementation of recursive function calls.
• Supports backtracking: Stack data structure supports backtracking algorithms,
which are used in problem-solving to explore all possible solutions by storing the
previous states.
• Used in Compiler Design: Stack data structure is used in compiler design for
parsing and syntax analysis of programming languages.
• Enables undo/redo operations: Stack data structure is used to enable undo and redo
operations in various applications like text editors, graphic design tools, and software
development environments.
Disadvantages of Stack:
• Limited capacity: Stack data structure has a limited capacity as it can only hold a fixed
number of elements. If the stack becomes full, adding new elements may result in stack
overflow, leading to the loss of data.
• No random access: Stack data structure does not allow for random access to its elements,
and it only allows for adding and removing elements from the top of the stack. To access
an element in the middle of the stack, all the elements above it must be removed.
• Memory management: Stack data structure uses a contiguous block of memory, which
can result in memory fragmentation if elements are added and removed frequently.
• Not suitable for certain applications: Stack data structure is not suitable for applications
that require accessing elements in the middle of the stack, like searching or sorting
algorithms.
• Stack overflow and underflow: Stack data structure can result in stack overflow if too
many elements are pushed onto the stack, and it can result in stack underflow if too many
elements are popped from the stack.
• Recursive function calls limitations: While stack data structure supports recursive
function calls, too many recursive function calls can lead to stack overflow, resulting in
the termination of the program.
Stacks using Linked List(Dynamic arrays):
• Stack Using linked list means that we are going to store the
information in the form of nodes.
• The stack rule says that insertion and deletion should take place at the
same end, i.e., Last In First Out(LIFO).
• Stack supports various operations like push, pop, peek, display. It can
be implemented using single linked list.
• The benefit of implementing a stack using a linked list in C over
arrays is that it allows to grow of the stack as per the requirements,
i.e., memory can be allocated dynamically.
Operations performed on Stack using linked list:
• push(): It inserts an element to the top of the stack. It takes O(1) time, as each
node is inserted at the head/top of the linked list.
• pop(): It removes an element from the top of the stack. It takes O(1) time, as the
top always points to the newly inserted node.
• peek(): It returns the top element of the stack.
• display(): It returns the size of the stack, i.e., the total number of items in a stack.
• A stack is represented using nodes of a linked list. Each node consists of two
parts: data and next(storing the address of the next node).
• The data part of each node contains the assigned value, and the next points to
the node containing the next item in the stack.
• The top refers to the topmost node in the stack. Both
the push() and pop() operations are carried out at the front/top of the linked list
and hence take O(1) time.
Node Structure: Structure to create a node with data and the link/next pointer
struct Node
{
int data;
struct Node *link;
};
Node* top=Null;
How to push() elements in the stack using linked list:
• Create a new node using dynamic memory allocation and assign value to the node.
struct Node *newNode=(struct Node*) malloc(sizeof(struct Node));
newNode -> data=10;
• Check if stack is empty or not, i.e, (top == NULL).
• If it is empty, then set the next pointer of the node to NULL.
newNode->next=Null;
• If it is not empty, the newly created node should be linked to the current top element of the stack, i.e.,

newNode->next=top;
• Algorithm for push()
• If the top is equal to NULL
newNode -> next=NULL
Else
newNode -> next=top

Example of Push() Operation:

int count = 0;// Push() operation on a stack

void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp; }
count++;
printf("Node is Inserted\n\n");
}
How to pop() elements from the stack using linked
list in C
• Check if stack is empty or not, i.e, (TOP == NULL).
• If it is empty, then print Stack Underflow.
• Print “stack is underflow”
• If it is not empty, then create a temporary node and set it to top. Now, create
another variable and copy the data of top element to this variable.
struct Node *temp=top;
int temp_data= top ->data
• Now, make top point to the next node.
top=top ->next
• Delete the temporary node and return the value stored in temp_data.
free(temp)
return temp_data
Algorithm for pop()

if top == NULL
Stack Underflow"
else
create temporary node,
*temp = top
create temporary variable,
temp_data = top->data
top = top->next
free(temp)
return
temp_data
 Example of Pop() Operation: //Structure to create a node with data and the next pointer
int pop()
{
if (top == NULL)
{
printf("\nEMPTY STACK");
}
else
{
struct Node *temp = top;
int temp_data = top->data; //to store data of top node
top = top->next;
free(temp); //deleting the node
return temp_data; }}
 Program to implement Stack using Linked List(Stack using Dynamic Array)
// Structure to create a node with data and the next pointer

void main()
#include<stdio.h> {
#include<stdlib.h> int choice, value;
printf("\n:: Stack using Linked List ::\n");
struct Node while(1!=5)
{ {
printf("\n****** MENU ******\n");
int data; printf("1. Push\n2.peek\n3. Pop\n4. Display\n");
struct Node *next; printf("Enter your choice: ");
scanf("%d",&choice);
}*top = NULL; switch(choice)
void push(int); {
void peek(); case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
void pop(); push(value); break;
void display(); case 2: peek(); break;
case 3: pop(); break;
case 4: display(); break;
default: printf("\nWrong selection!!! Please try again!!!\n");
break(); } }}
void push(int value) void peek()
{ {
struct Node *newNode; if(top == NULL)
newNode= (struct {
Node*)malloc(sizeof(struct Node)); printf("\nStack isEmpty!!!\n");
newNode->data = value; }
if(top == NULL) else
newNode->next = NULL; {
else printf("\ntop of element=%d",top-
newNode->next = top; >data);
top = newNode; }}
printf("\nInsertion is Success!!!\n");}
void pop() void display()
{ {
if(top == NULL)
if(top == NULL)
printf("\nStack is Empty!!!\n");
printf("\nStack is Empty!!!\n"); else
else
{
{ struct Node *temp = top;
struct Node *temp = top; while(temp->next != NULL)
printf("\nDeleted element: %d", {
temp->data); printf("%d--->",temp->data);
temp = temp -> next;
top = temp->next;
}
free(temp); printf("%d--->NULL",temp->data);
} }
} }
• Advantages Of Linked List:
• Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink
at runtime by allocating and deallocating memory. So there is no need to give the initial
size of the linked list.
• No memory wastage: In the Linked list, efficient memory utilization can be achieved since
the size of the linked list increase or decrease at run time so there is no memory wastage
and there is no need to pre-allocate the memory.
• Implementation: Linear data structures like stacks and queues are often easily
implemented using a linked list.
• Insertion and Deletion Operations: Insertion and deletion operations are quite easier in
the linked list. There is no need to shift elements after the insertion or deletion of an
element only the address present in the next pointer needs to be updated.
• Flexible: This is because the elements in Linked List are not stored in contiguous memory
locations unlike the array.
• Efficient for large data: When working with large datasets linked lists play a crucial role
as it can grow and shrink dynamically.
• Scalability: Contains the ability to add or remove elements at any position.
• Disadvantages Of Linked List:
• Memory usage: More memory is required in the linked list as compared to an array. Because in a linked
list, a pointer is also required to store the address of the next element and it requires extra memory for
itself.
• Traversal: In a Linked list traversal is more time-consuming as compared to an array. Direct access to an
element is not possible in a linked list as in an array by index. For example, for accessing a node at
position n, one has to traverse all the nodes before it.
• Reverse Traversing: In a singly linked list reverse traversing is not possible, but in the case of a
doubly-linked list, it can be possible as it contains a pointer to the previously connected nodes with each
node. For performing this extra memory is required for the back pointer hence, there is a wastage of
memory.
• Random Access: Random access is not possible in a linked list due to its dynamic memory allocation.
• Lower efficiency at times: For certain operations, such as searching for an element or iterating through
the list, can be slower in a linked list.
• Complex implementation: The linked list implementation is more complex when compared to array. It
requires a complex programming understanding.
• Difficult to share data: This is because it is not possible to directly access the memory address of an
element in a linked list.
• Not suited for small dataset: Cannot provide any significant benefits on small dataset compare to that of
an array.
 Evaluation of Expression- Infix to Postfix Conversion, Evaluation of Postfix Expression:
Algebraic expressions: An algebraic expression is a legal combination of operands and operators.
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:
1.Infix: It is the form of an arithmetic expression in which we fix (place) the arithmetic operator in between
the two operands.
The syntax of Infix notation is: < operand > < operator > <operand>
Example: A + B
2.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.
The syntax of Prefix notation is: < operator > < operand > <operand>
Example: + A B
3.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.
The syntax of Postfix notation is: < operand > <operand>< operator >
Example: A B +
 Evaluation of Expression:
• The operator with higher precedence is evaluated first and the operator with the least precedence is evaluated
last. An expression is evaluated based on the precedence and associativity of the operators in that expression.
• There are different levels of operator precedence and an operator may belong to one of these levels.
Conversion from infix to postfix:
Procedure Algorithm for Conversion of Infix to Postfix using Stack as
follows:
• Scan all the symbols one by one from left to right in the given Infix
Expression.
• If the reading symbol is an operand, then immediately append it to the
Postfix Expression.
• If the reading symbol is left parenthesis ‘( ‘, then Push it onto the Stack.
• If the reading symbol is right parenthesis ‘)’, then Pop all the contents of the
stack until the respective left parenthesis is popped and append each popped
symbol to Postfix Expression.
• If the reading symbol is an operator (+, –, *, /), then Push it onto the Stack.
However, first, pop the operators which are already on the stack that have
higher or equal precedence than the current operator and append them to
the postfix. If an open parenthesis is there on top of the stack then push the
operator into the stack.
• If the input is over, pop all the remaining symbols from the stack and
append them to the postfix.
• We consider five binary operations: +, -, *, / and $ or ↑ (exponentiation). For
these binary operations, the following in the order of precedence (highest to
lowest):
C Program to Convert Infix expression into Postfix expression using Stack
#include<stdio.h>
#include<ctype.h>// The ctype. h header file declares functions used in character
classification.
char stack[100];
int top = -1;
void push(char x)
{
stack[++top] = x;
}
char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}
int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
if(x == '^' || x == '$')
return 3;
return 0;
}
int main()
{
char exp[100];
char *e, x;
printf("Enter the Infix expression : ");
scanf("%s",exp);
printf("\n");
e = exp;
while(*e != '\0’)
{
if(isalnum(*e))
printf("%c ",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c ", x);
} else
{
while(priority(stack[top]) >= priority(*e))
printf("%c ",pop());
push(*e);
}
e++;
}
while(top != -1)
{
printf("%c ",pop());
}
return 0;
}
Output Test Case 1:
Enter the Infix expression : ((4+8)(6-5))/((3-2)(2+2))
48+65-32-22+/
Output Test Case 2:
Enter the infix expression: A+B*C/A+(B+C)
ABC*A/ +BC++
Output Test Case 3:
Enter the Infix expression : z$a/b*(c+d-f/g)
za$b/cd+fg/-*
• Conversion from infix to prefix:
The conversion from infix notation to prefix notation involves reversing the order of the Expression.
Given an infix arithmetic expression convert into an equivalent prefix expression:
• Expression will be given in the form of string , where alphabetic characters i.e a-z or A-Z denotes operands
and operators are ( + , – , * , / ) . Expression can also have brackets i.e ‘(’ and ‘)’.

• Sample example :
• Input: infix expression: a * ( b + c + d) Output: prefix expression: *a+b+cd
• Input: infix expression: b*c Output: prefix expression: *bc
Here, is the infix to prefix examples Rules:
 Consider the infix expression: (3 + 4 * 2) / (1 – 5)
 Convert all opening brackets to closing brackets and vice versa
 Reverse the infix expression: )5 – 1(/ )2 * 4 + 3(
How to Design Infix to Prefix Algorithm:
1. Create an empty stack and an empty output string.
2. Reverse the infix expression: Reverse the order of all elements in the infix expression, including
operands and operators.
3. Iterate through the reversed infix expression from left to right.
4. If the current character is an operand (number or variable), append it to the output string.
5. If the current character is a closing bracket ‘)’, push it onto the stack.
6. If the current character is an operator compare its precedence with the precedence of the
operator at the top of the stack.
7. If the current operator/incoming operator has higher precedence than the operator at the top of
the stack or the stack is empty, push the current operator onto the stack.
8. If the current operator has equal precedence than the operator at the top of the stack, Then push
the current operator onto the stack.
9. If the current operator has lower precedence than the operator at the top of the stack, pop the
operators from the stack and append them to the output string until an operator with
lower/equal precedence is encountered or the stack becomes empty. Then push the current
operator onto the stack.
10. If the current character is an opening bracket ‘(‘, pop the operators from the stack and append
them to the output string until the corresponding closing bracket ‘)’ is encountered. Discard the
closing bracket.
11. Repeat steps 4 to 10 until all characters in the reversed infix expression have been processed.
12. Pop the remaining operators from the stack and append them to the output string.
13. Reverse the output string to obtain the prefix expression.
Function
infix = InfixtoPrefix( stack, infix)
reverse(infix)
loop
if i = 0 istooperand
infix[i] infix.length
→ prefix+= infix[
i]
else if infix[i] is '(' → stack.push(infix
[i])
else if infix[i] is ')' → pop and print th
eotvalues
found of stack till the symbol ')' is n
else
^) → if infix[i] is an operator(+, -, *, /,
if
on the
the stack
top ofisthe
empty then push infix[i]
stack.
Else →
If precedence(infix[i] > precedence(sta
ck.top))
→
k Push infix[i] on the top of the stac
else
p) && if(infix[i]
infix[i] ==
== precedence(stack.to
'^')
→stackPop tilland
the print the top
condition is values of the
true
→
else Push infix[i] into the stack
p)) if(infix[i] == precedence(stack.to
→ Push infix[i] on to the stack
Else if(infix[i] < precedence(stack.top))
→ Pop the stack values and print them till the stack is not empty and infix[i] < precedence(stack.to
p)
→ Push infix[i] on to the stack
End loop
Pop and print the remaining elements of the stack
Prefix = reverse(prefix)
return
• Conversion of Infix to Prefix using Stack:
• Example: Infix expression: 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.
• Example1: (A+B^C)*D+E^5
• Example2: (A+B)*C-D+F
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.
• Final prefix expression is: ++-+KL*MN*//*^OPWUVTQ

• Evaluation of postfix expression:

•Algorithm to evaluate postfix expression 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.
Conversion of Prefix to Postfix Expression:
• Algorithm/Rules for prefix to postfix expression
using stack data structure:
1. Scan the prefix expression from right to left, i.e., reverse.
2. If the incoming symbol is an operand then push it into the
stack.
3. If the incoming symbol is an operator then pop two operands
from the stack. Once the operands are popped out from the
stack, we add the incoming symbol after the operands.
e.g: expression = operand1 + operand2 +
operator
4. When the operator is added after the operands, then the
expression is pushed back into the stack.
5. Once the whole expression is scanned, pop and print the
postfix expression from the stack.
• Pseudocode for prefix to postfix conversion
Function PrefixToPostfix(string prefix)
1.Stack s
2.Loop: i = prefix.length-1 to 0
if prefix[i] is operand -> s.push(prefix[i])
else if prefix[i] is operator-> op1 = s.top()
s.pop()
op2 = s.top()
s.pop()
exp = op1 + op2 + prefix[i]
s.push(exp)
End Loop
3.Return s.top
Example prefix expression is: * - A / B C - / A K L (Scan from Right to Lift Order)
Symbols to be Action/Process Stack Description
scanned
L Push L into the stack L
K Push K into the stack L, K
A Push A into the stack L, K, A
/ Pop A from the stack L, A K / Pop two operands from the stack, i.e., A
Pop K from the stack and K. Add '/' operator after K operand,
Push A K / into the stack i.e., AK/. Push AK/ into the stack.
- Pop A K / and L from the stack. A K / L - Pop two operands from the stack, i.e.,
Push (A K / L -) into the stack AK/ and L. Add '-' operator after 'L'
operand.
C Push C into the stack AK/L-, C
B Push B into the stack AK/L-, C, B
/ Pop B and C from the stack. AK/L-, BC/ Pop two operands from the stack, i.e., B
Push BC/ into the stack. and C. Add '/' operator after C operator,
i.e., BC/. Push BC/ into the stack.
A Push A into the stack AK/L-, BC/,
A
- Pop BC/ and A from the stack. AK/L-, Pop two operands from the stack, i.e., A
Push ABC/- into the stack. ABC/- and BC/. Add '-' operator after '/'.
* Pop ABC/- and AK/L- from the ABC/-AK/L-* Pop two operands from the stack, i.e.,
stack. Push ABC/AK/L-* into the ABC/-, and AK/L- . Add '*' operator after
• Example: Conversion Prefix expression into Postfix expression
• Prefix: *+AB-CD
• Prefix: *-A/BC/-/AKL
Conversion of Postfix to Prefix expression:
There are two ways of converting a postfix into a prefix expression:
Conversion of Postfix to Prefix expression manually.
Conversion of Postfix to Prefix expression using stack.
• Conversion of Postfix to Prefix expression manually
The following are the steps required to convert postfix into prefix expression:
• Scan the postfix expression from left to right.
• Select the first two operands from the expression followed by one operator.
• Convert it into the prefix format.
• Substitute the prefix sub expression by one temporary variable
• Repeat this process until the entire postfix expression is converted into prefix expression.
Let's understand through an example: a b - c +
First, we scan the expression from left to right. We will move '-' operator before the operand ab.
-abc+
The next operator '+' is moved before the operand -abc is shown as below:
+-abc
Conversion of Postfix to Prefix expression using
Stack
• The following are the steps used to convert postfix to prefix
expression using stack:
• Scan the postfix expression from left to right.
• If the element is an operand, then push it into the stack.
• If the element is an operator, then pop two operands from the
stack.
• Create an expression by concatenating two operands and
adding operator before the operands.
• Push the result back to the stack.
• Repeat the above steps until we reach the end of the postfix
expression.
• Pseudocode for the conversion of Postfix to Prefix
1.Function PostfixToPrefix(string postfix)
2.Stack s
3.Loop: i = 0 to postfix.length
if postfix[i] is operand -> s.push(postfix[i])
else if postfix[i] is operator-> op1 = s.top()
s.pop()
op2 = s.top()
s.pop()
expression = postfix[i] + op2 + op1
s.push(expression)
end loop
4.return s.top
• Let's understand the conversion of postfix to
prefix expression using stack. If the Postfix
expression
Symbol Action is given as: AB
Stack+ CD -*
Description
Scanned
A Push A into the stack A
B Push B into the stack AB
+ Pop B from the stack +AB Pop two operands from the stack, i.e.,
Pop A from the stack A and B. Add '+' operator before the
Push +AB into the stack. operands AB, i.e., +AB.

C Push C into the stack +ABC

D Push D into the stack +ABCD
- Pop D from the stack. +AB -CD Pop two operands from the stack, i.e.,
Pop C from the stack. D and C. Add '-' operator before the
Push -CD into the stack operands CD, i.e., -CD.

* Pop -CD from the stack. *+AB - CD Pop two operands from the stack, i.e.,
Pop +AB from the stack. -CD and +AB. Add '*' operator before
Push *+AB -CD into the stack. +AB then the expression would
become *+AB-CD.
 QUEUE
• Queue is a data structure that is similar to the queue in the real world.
• A queue is a linear data structure in which whatever comes first will go out
first, and it follows the FIFO (First-In-First-Out) policy.
• Queue can also be defined as the list or collection in which the insertion is
done from one end known as the rear end or the tail of the queue, whereas
the deletion is done from another end known as the front end or the head of
the queue.
• The real-world example of a queue is the ticket queue outside a cinema hall,
where the person who enters first in the queue gets the ticket first, and the last
person enters in the queue gets the ticket at last.
• Similar approach is followed in the queue in data structure.
• The representation of the queue is shown in the below image
Types of Queue: There are four different types of queue that are listed as
follows
1. Simple Queue or Linear Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue( or Deque)

 Representation of Queue (or) Implementation of Queue: In two ways

1. Queue using Array 2.Queue using Linked List
1. Simple Queue or Linear Queue using Array Representation:
 Operations on LINEAR QUEUE:
• A queue is an object or more specifically an Abstract Data Structure Type (ADT) that allows the following
operations:
• Enqueue or insertion: which inserts an element at the end of the queue.
• Dequeue or deletion: which deletes an element at the start of the queue.
• Display: which displays the elements of the queue.

Linear Queue operations work as follows:

• Two pointers called FRONT and REAR are used to keep track of the first and last elements in the
queue.
• When initializing the queue, we set the value of FRONT and REAR to 0.
• On enqueuing an element, we increase the value of REAR index and place the new element in the
position pointed to by REAR.
• On dequeuing an element, we return the value pointed to by FRONT and increase the FRONT
index.
• Before enqueuing, we check if queue is already full.
• Before dequeuing, we check if queue is already empty.
• When enqueuing the first element, we set the value of FRONT to 0.
• When dequeuing the last element, we reset the values of FRONT and REAR to 0.
• Linear Queue using Array:
• Let us consider a queue, which can hold maximum of five elements. Initially
the queue is empty.

• Now, insert 11 to the queue. Then queue status will be:

• Next, insert 22 to the queue. Then the queue • Again, delete an element. The element to be deleted
status is: is always pointed to by the FRONT pointer. So, 22
is deleted. The queue status is as follows:

• Again insert another element 33 to the queue.

The status of the queue is: • Now, insert new elements 44 and 55 into the queue.
The queue status is:

• Next insert another element, say 66 to the queue.

• Now delete an element. The element deleted is
We cannot insert 66 to the queue as the rear crossed
the element at the front of the queue. So the
the maximum size of the queue (i.e., 5). There will
status of the queue is:
be queue full signal. The queue status is as follows
• Now it is not possible to insert an element 66 even though there are two vacant positions in the
linear queue. To overcome this problem the elements of the queue are to be shifted towards the
beginning of the queue so that it creates vacant position at the rear end.
• Then the FRONT and REAR are to be adjusted properly. The element 66 can be inserted at the
rear end. After this operation, the queue status is as follows:

• This difficulty can overcome if we treat queue position with index 0 as a position that comes
after position with index 4 i.e., we treat the queue as a circular queue.
C program for Queue using Arrays
#include<stdio.h> #include<stdlib.h> switch(choice) {
#define maxsize 5 case 1:
void enqueue(); enqueue();
void dequeue(); break;
void display(); case 2:
int front = -1, rear = -1; dequeue();
int queue[maxsize]; break;
void main () { case 3:
int choice; display();
while(choice != 4) { break;
printf("\n*****Main Menu*****\n"); case 4:
printf("\n1.insert an element\n2.Delete an exit(0);
element\n3.Display the queue\n4.Exit\n"); break;
printf("\nEnter your choice:"); default: printf("\nEnter valid choice??\n");
scanf("%d",&choice); } } }
void enqueue() { void dequeue() {
int item; int item;
printf("\nEnter the element:"); if (front == -1 || front > rear)
scanf("\n%d",&item); {
if(rear == maxsize-1) printf("\n QUEUE IS UNDERFLOW\n");
{ }
printf("\n QUEUE IS OVERFLOW\n"); else
{
}
item = queue[front];
if(front == -1 && rear == -1)
printf("\ndeleted value=%d",item);
{
if(front == rear)
front = rear = 0;
{
}
front = rear= -1 ;
queue[rear] = item;
}
printf("\nValue inserted ");
else {
rear = rear+1;
front = front + 1;
}
}}}
void display() {
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{
printf("\n Queue elements are:");
for(i=front;i<=rear;i++)
{
printf("%d\t\t",queue[i]);
} } }
• Simple Queue or Linear Queue using Linked List Representation:
 Operations:
 Step 1 - Include all the header files which are used in the program. And declare all the user defined
functions.
 Step 2 - Define a 'Node' structure with two members data and next.
 Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
 Step 4 - Implement the main method by displaying Menu of list of operations and make suitable function
calls in the main method to perform user selected operation.
 enQueue(value) - Inserting an element into the Queue

• We can use the following steps to insert a new node into the queue...
 Step 1 - Create a newNode with given value and set 'newNode → next' to NULL.
 Step 2 - Check whether queue is Empty (rear == NULL)
 Step 3 - If it is Empty then, set front = newNode and rear = newNode.
 Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode.
 deQueue() - Deleting an Element from Queue: We can use the following steps to delete a node from the
queue...
 Step 1 - Check whether queue is Empty (front == NULL).
 Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from
the function
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.
 Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).
 display() - Displaying the elements of Queue: We can use the following steps to display the elements
(nodes) of a queue...
 Step 1 - Check whether queue is Empty (front == NULL).
 Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with front.
 Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp' reaches to
'rear' (temp → next != NULL).
 Step 5 - Finally! Display 'temp → data ---> NULL'.
struct Node{ void main(){
int choice, value;
int data; printf("\n:: Queue Implementation using Linked List ::\n");
while(1!=5){
struct Node *next; printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: "); scanf("%d",&choice);
}*front = NULL,*rear = switch(choice){
NULL; case 1: printf("Enter the value to be insert: "); scanf("%d",
&value);
void insert(int); insert(value); break;
case 2: delete(); break;
void delete(); case 3: display(); break;
case 4: exit(0);
void display(); default: printf("\nWrong selection!!! Please try again!!!\
n");
} }}
void insert(int value){ void delete(){
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct if(front == NULL)
Node));
newNode->data = value;
printf("\nQueue is Empty!!!\n");
newNode -> next = NULL; else{
if(front == NULL)
{
struct Node *temp = front;
front = rear = newNode; front = front -> next; printf("\
front->next=NULL; nDeleted element: %d\n",
rear->next=NULL;
} temp->data);
else{ free(temp);
rear -> next = newNode;
rear = newNode; }}
}
printf("\nInsertion is Success!!!\n");
}
void display(){
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct Node *temp = front;
while(temp->next != NULL)
{
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL\n",temp->data);
}}
• Representation of Circular Queue:
• A circular queue is similar to a linear queue as it is also based on the FIFO (First In First
Out) principle except that the last position is connected to the first position in a circular
queue that forms a circle. It is also known as a Ring Buffer.

• Operations on Circular Queue: The following are the operations that can be performed on a circular
queue:
 Front: It is used to get the front element from the Circular Queue.
 Rear: It is used to get the rear element from the Circular Queue.
 enQueue(value): This function is used to insert the new value in the Circular Queue. The new
element is always inserted from the rear end.
 deQueue(): This function deletes an element from the Queue. The deletion in a Circular Queue
always takes place from the front end.
• Scenarios for inserting an element
•There are two scenarios in which queue is not full:
 If rear != max - 1, then rear will be incremented to mod(maxsize) and the new value will be
inserted at the rear end of the queue.
 If front != 0 and rear = max - 1, it means that queue is not full, then set the value of rear to 0
and insert the new element there.
•There are two cases in which the element cannot be inserted:
 When front ==0 && rear = max-1, which means that front is at the first position of the Queue
and rear is at the last position of the Queue.
 front== rear + 1;
• Let us consider a circular queue, which can hold
maximum (MAX) of six elements. Initially the
queue is empty (i.e ., front=-1 and rear=-1) then set
front=0 and rear=0.