UNIT 2

Stacks and Queues: Stacks, Stacks using Arrays, Stacks using dynamic arrays, Evaluation
of Expressions – Evaluating Postfix Expression, Infix to Postfix.
Queues: Queues ADT, operations, Circular Queues, Applications
==========================================================================

Stacks
A stack in C is a data structure that follows the Last In, First Out (LIFO) principle, meaning
the last item added is the first to be removed. Stacks are widely used in programming for
tasks like parsing expressions, managing function calls, and supporting operations like
undo/redo in applications.

Characteristics of Stacks
LIFO (Last In, First Out): The last element added is the first one to be removed.
Limited Operations: Only the top item is accessible, and elements can be added or removed
only from this top position.

Stack ADT
Push: Add an item to the top of the stack.
Pop: Remove an item from the top of the stack.
Peek/Top: View the top element without removing it.
isEmpty: Check if the stack is empty.
isFull: (in fixed-size stacks) Check if the stack is full.
Stack Representation in C
Stacks can be implemented using either arrays or linked lists in C.

Array-based Stack: The stack has a fixed size. Operations like push and pop are implemented
on an array, with a top variable indicating the current top element.
Linked List-based Stack: The stack can dynamically grow in size. A linked list node structure
is used, with each node pointing to the next item.

Advantages
 Simple to implement.
 Provides LIFO access, useful in certain applications (e.g., managing function calls,
backtracking).
Limitations
 Fixed-size (in array-based stacks), which can lead to overflow.
 Restricted access since only the top element is accessible.

DR. V SREENIVASULU 1
Applications of Stacks
 Function Call Management: Manages nested function calls with each call’s context
pushed onto the stack.
 Expression Evaluation: Assists in evaluating expressions in postfix, prefix, and infix
notations.
 Undo Mechanisms: Supports "undo" operations by keeping track of actions.
 Syntax Parsing: Helps validate balanced parentheses in code and expression parsing.

Stacks using Arrays

Implementing a stack using arrays in C involves defining an array to hold the stack elements
and an integer variable often called top that tracks the index of the last inserted element. The
main operations (push, pop, peek, etc.) are then implemented using this array.

1_Write a C program that reads # elements into a stack with Push (), Pop (), Display ()

#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = -1,i;

void push(int stack_size)

{
int element;

if (top == stack_size - 1)
printf("Stack Overflow\n");

else
{
for ( i = 0; i < stack_size; i++)
{
printf("Enter element %d: ",i+1);
scanf("%d", &element);

top++;
stack[top] = element;
}
}
}

DR. V SREENIVASULU 2
int pop()
{
if (top == -1)
printf("Stack Underflow\n");

else
{
int temp = stack[top];
top--;
return temp;
}

void display()
{
if (top == -1)
printf("Stack is empty\n");

else
{
for (i = top; i >= 0; i--)
printf("%d\n", stack[i]);
}
}

int main()
{
int stack_size, val;

printf("Enter the size of the stack: ");

scanf("%d", &stack_size);

push(stack_size);

printf("Elements in the stack after pushing:\n");

display();

val = pop();
printf("The popped element is %d:\n",val);

printf("Elements in the stack after popping:\n");

display();

DR. V SREENIVASULU 3
 return 0;
}

OUTPUT
Enter the size of the stack: 3
Enter element 1: 11
Enter element 2: 22
Enter element 3: 33
Elements in the stack after pushing:
33
22
11
The popped element is 33:
Elements in the stack after popping:
22
11

2_Imagine you are developing an order processing system where each new order’s ID needs to
be recorded in the order they are received. For simplicity, this order history uses a stack,
allowing you to handle only a limited number of orders at a time due to memory constraints

#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = -1,i;
int stack_size;

void push(int element)

{
if (top == stack_size - 1)
printf("Stack Overflow\n");

else
{
top++;
stack[top] = element;
printf("Element %d pushed onto stack...", element);
}
}

DR. V SREENIVASULU 4
void pop()
{
if (top == -1)
printf("Stack Underflow\n");

else
{
printf("Element %d popped from stack...", stack[top]);
top--;
}
}

void display()
{
if (top == -1)
printf("Stack is empty\n");

else
{
printf("Stack elements ...");
for (i = top; i >= 0; i--)
{
printf("%d ", stack[i]);
}
printf("\n");
}
}

int main()
{
int choice, element;
printf("Enter the stack size ...");
scanf("%d", &stack_size);

do
{
printf("\n--- Stack Operations Menu ---\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Display\n");
printf("4. Exit\n");

printf("Enter the choice: ");

DR. V SREENIVASULU 5
 scanf("%d", &choice);

switch (choice)
{
case 1:
printf("Enter element to push: ");
scanf("%d", &element);
push(element);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
printf("Exiting program\n");
break;
default:
printf("Check choice\n");
}
} while (choice != 4);

return 0;
}

OUTPUT
Enter the stack size ...5

--- Stack Operations Menu ---

1. Push
2. Pop
3. Display
4. Exit
Enter the choice: 1
Enter element to push: 11
Element 11 pushed onto stack...
--- Stack Operations Menu ---
1. Push
2. Pop
3. Display
4. Exit
Enter the choice: 1
Enter element to push: 22

DR. V SREENIVASULU 6
Element 22 pushed onto stack...
--- Stack Operations Menu ---
1. Push
2. Pop
3. Display
4. Exit
Enter the choice: 1
Enter element to push: 33
Element 33 pushed onto stack...
--- Stack Operations Menu ---
1. Push
2. Pop
3. Display
4. Exit
Enter the choice: 3
Stack elements ...33 22 11

--- Stack Operations Menu ---

1. Push
2. Pop
3. Display
4. Exit
Enter the choice: 2
Element 33 popped from stack...
--- Stack Operations Menu ---
1. Push
2. Pop
3. Display
4. Exit
Enter the choice: 3
Stack elements ...22 11

--- Stack Operations Menu ---

1. Push
2. Pop
3. Display
4. Exit
Enter the choice:

DR. V SREENIVASULU 7
Dynamic arrays
 Implementing a stack using dynamic arrays allows the stack to grow and shrink as
needed, overcoming the fixed-size limitation of static arrays.

 This dynamic resizing provides flexibility in cases where the number of elements in the
stack isn't known in advance.

Points to ponder a Dynamic Array Stack

1. Dynamic Resizing: As elements are added, the array's size increases when it reaches
its current capacity. When elements are removed, the array can decrease in size to save
memory if needed.
2. Doubling Strategy: To make resizing efficient, the stack's size is typically doubled
whenever it runs out of space.
3. Shrinking Strategy: To prevent excessive memory usage, the array size can be halved
if the number of elements falls below a certain threshold, like one-quarter of the current
capacity.
4. Time Complexity: Push and pop operations are O (1) on average. However, resizing
(which involves copying elements) can take O(n), but this only happens occasionally.

Advantages
 Dynamic Resizing: Flexible stack size, with memory allocated only as needed.
 Efficient Memory Usage: Reduces memory waste by shrinking the stack when it
has excess space.
Disadvantages
 Overhead: Occasional resizing operations may be costly O(n) Time complexity.
 Memory Fragmentation: Frequent realloc calls may lead to memory fragmentation
in long-running programs.
This dynamic array-based stack implementation in C is efficient and flexible, making it
suitable for applications where the stack size fluctuates.

Normal (Static) Arrays

 A normal array in C has a fixed size, so size must specify when declaring the array.
This size cannot change during the program's execution.
Characteristics:
 Fixed Size: The size must be known at compile-time and remains constant. For
example, int array [5]; allocates exactly 5 integers and cannot grow or shrink.
 Memory Allocation: Memory is allocated on the stack if declared inside a function, or
in the global/static memory area if declared outside any function.
 Fast Access: Accessing elements is fast because memory for the array is allocated at
compile-time.

DR. V SREENIVASULU 8
Drawbacks:
 Inflexibility: If more space needed , a static array can’t be expanded. Conversely, if the
allocated size is too large, it can waste memory.
 Usage: Static arrays are useful when the exact size needed for the array in advance
and don't expect it to change.
Dynamic array
 Dynamic array on the other hand, is allocated at runtime using functions like malloc
or calloc and can be resized using realloc.
 Dynamic arrays are useful when the array size is unknown at compile-time or needs
to change as the program runs.
Characteristics:
 Resizable: The size of a dynamic array can change at runtime, allowing to allocate only
as much memory as needed.
 Memory Allocation: Memory is allocated on the heap that allows for larger memory
allocation but requires manual management (i.e., freeing memory with free when done).
 Flexible: Dynamic arrays can grow or shrink as needed by reallocating memory.
Drawbacks:
 Complexity: Managing dynamic memory requires additional work, including calling
malloc, realloc, and free to manage the memory lifecycle.
 Risk of Memory Leaks: If memory is not freed after use, it can lead to memory leaks,
which reduce available memory over time.

Feature Normal (Static) Array Dynamic Array

Size Fixed at compile-time Variable, can be resized at runtime
Memory Allocation Stack or static Heap memory (manual management
memory required)
Resizable No Yes
Efficiency Faster, as size is May be slower due to resizing operations
known
Use Case Known, unchanging Unknown or varying size requirements
size
Example int array[10]; int *array = malloc(size * sizeof(int));
Declaration

DR. V SREENIVASULU 9
3_Write a C program for Stack using Dynamic array that Implements a Resizable Array-Based
Stack to Facilitate Flexible Data Storage and Retrieval

#include <stdio.h>
#include <stdlib.h>

#define Stack_size 2

int *stack;
int top = -1,i;
int capacity = Stack_size;

void initialize()
{
stack = (int *)malloc(capacity * sizeof(int));
if (stack == NULL)
{
printf("Memory allocation failed\n");
exit(1);
}
}

void resize()
{
capacity *= 2;
stack = (int *)realloc(stack, capacity * sizeof(int));
if (stack == NULL)
{
printf("Memory allocation failed during resizing\n");
exit(1);
}
}

void push(int value)

{
if (top == capacity - 1)
{
resize();
}
top++;
stack[top] = value;
printf("Pushed %d onto stack:", value);
}

DR. V SREENIVASULU 10
void pop()
{
if (top == -1)
printf("Stack is empty\n");

else
{
int var = stack[top];
top--;
printf("Popped %d from stack:", var);
}

void display()
{
if (top == -1)
printf("Stack is empty:\n");

else
{
printf("Stack elements: ");
for (i = top; i >= 0; i--)
printf("%d ", stack[i]);
printf("\n");
}
}

void freeStack()
{
free(stack);
}

int main()
{
initialize();

int choice, value;

while (1)
{
printf("\nChoose an operation:\n1. Push\n2. Pop\n3. Display\n4. Exit\n");

DR. V SREENIVASULU 11
 printf("Enter choice: ");
scanf("%d", &choice);

switch (choice)
{
case 1:
printf("Enter value to push: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
printf("Exiting program.\n");
freeStack();
return 0;
default:
printf("Invalid correct choice: ");
}
}
}

OUTPUT

Choose an operation:
1. Push
2. Pop
3. Display
4. Exit
Enter choice: 1
Enter value to push: 11
Pushed 11 onto stack:
Choose an operation:
1. Push
2. Pop
3. Display
4. Exit
Enter choice: 1
Enter value to push: 22
Pushed 22 onto stack:

DR. V SREENIVASULU 12
Choose an operation:
1. Push
2. Pop
3. Display
4. Exit
Enter choice: 1
Enter value to push: 33
Pushed 33 onto stack:
Choose an operation:
1. Push
2. Pop
3. Display
4. Exit
Enter choice: 1
Enter value to push: 44
Pushed 44 onto stack:
Choose an operation:
1. Push
2. Pop
3. Display
4. Exit
Enter choice: 3
Stack elements: 44 33 22 11

Choose an operation:
1. Push
2. Pop
3. Display
4. Exit
Enter choice: 2
Popped 44 from stack:
Choose an operation:
1. Push
2. Pop
3. Display
4. Exit
Enter choice: 3
Stack elements: 33 22 11

Choose an operation:
1. Push
2. Pop
3. Display
4. Exit

DR. V SREENIVASULU 13
Enter choice:

Converting infix notation to postfix notation

Converting infix notation to postfix notation is an essential process in expression evaluation.

The postfix notation is useful because it removes the need for parentheses to maintain
precedence, simplifying evaluation. This conversion is often done using a stack data structure
to keep track of operators and their precedence.

1. Infix Expression: Operators are between operands, e.g., A + B * C.

2. Postfix Expression: Operators follow operands, e.g., ABC*+.
3. Operator Precedence: Determines the order of operations:
 High precedence: ^ (exponentiation)
 Medium precedence: *, / (multiplication, division)
 Low precedence: +, - (addition, subtraction)
4. Associativity:
o Left-to-right for +, -, *, and /.
o Right-to-left for ^.
o
Procedure Using a Stack - Step-by-Step Algorithm
1. Initialize:
o Create an empty stack to hold operators and parentheses.
o Create an empty output list for the postfix expression.
2. Process Each Symbol in the Infix Expression:
o Operand (e.g., A, B, 1, 2): Directly add it to the output list.
o Operator (e.g., +, -, *, /, ^):
 While there is an operator on top of the stack with greater or equal
precedence (for left-associative operators) or greater precedence (for right-
associative operators), pop it from the stack and add it to the output list.
 Push the current operator onto the stack.
o Left Parenthesis ((): Push it onto the stack to signify that a sub-expression has
started.
o Right Parenthesis ()):
 Pop operators from the stack and add them to the output list until a left
parenthesis (() is encountered.
 Discard the left parenthesis from the stack.
3. After Processing All Symbols:
 Pop all remaining operators from the stack and add them to the output
list.
4. Result: The output list now contains the postfix expression.

DR. V SREENIVASULU 14
Conversion of infix expression into post fix expression in detail using a tabular form
a+g*d^k/m–p

Step Token Stack Output Explanation

1 a Empty a Operand goes to output.
2 + + a Push + onto the stack.
3 g + ag Operand goes to output.
4 * +* ag Push * onto the stack (higher
precedence than +).
5 d +* agd Operand goes to output.
6 ^ +*^ agd Push ^ onto the stack (higher
precedence than *).
7 k +*^ agdk Operand goes to output.
8 / +* agdk^ Pop ^ to output because / has
lower precedence. Push / onto
the stack.
9 m +* / agdk^m Operand goes to output.
10 - + agdk^m/* Pop / and * to output because -
has lower precedence. Pop - to
stack.
11 p - agdk^m/*+p Operand goes to output.
12 Empty Empty agdk^m/*+p Pop remaining operators (-) to
output.

4_Write a C program that reads an Infix expression and convert the same into Postfix
notation

#include <stdio.h>
#include <ctype.h>

#define size 50

char stack[size];
int top = -1;

void push(char ch)

{
if (top == size - 1)
printf("Stack Overflow\n");
else
{

DR. V SREENIVASULU 15
 top = top + 1;
stack[top] = ch;
}
}

char pop()
{
if (top ==-1)
printf("Stack Underflow\n");

else
{
char temp = stack[top];
top = top - 1;
return temp;
}
}

int precedence(char ch)

{
if (ch == '+' || ch == '-') return 1;
if (ch == '*' || ch == '/') return 2;
if (ch == '^') return 3;
return 0;
}

void infixToPostfix(char infix[], char postfix[])

{
int i = 0, j = 0;

while (infix[i] != '\0')

{
char ch = infix[i];
if (isalpha(ch))
{
postfix[j] = ch;
j = j + 1;
}
else
{
while (top >= 0 && precedence(stack[top]) >= precedence(ch))
{
postfix[j] = pop();

DR. V SREENIVASULU 16
 j = j + 1;
}
push(ch);
}
i = i + 1;
}

while (top >= 0)

{
postfix[j] = pop();
j = j + 1;
}
postfix[j] = '\0';
}

int main()
{
char infix[size];
char postfix[size];

printf("Enter an infix expression: ");

scanf("%s", infix);

infixToPostfix(infix, postfix);

printf("Postfix Expression: %s\n", postfix);

return 0;
}
OUTPUT
Enter an infix expression: A+B*C^D
Postfix Expression: ABCD^*+

Evaluate a postfix expression

To evaluate a postfix expression (Reverse Polish Notation) using a stack to process each
operand and operator in the correct order. Postfix expressions are easy to evaluate with
stacks because they follow a simple, well-defined order: operands appear before their
operators, so no precedence rules or parentheses are required.

Algorithm for Evaluating a Postfix Expression

1. Initialize an empty stack to store operands.
2. Read the expression from left to right, one symbol either operand or operator at a time.
3. Process each symbol:
 Operand: If the symbol is an operand, push it onto the stack.

DR. V SREENIVASULU 17
 
Operator: If the symbol is an operator (+, -, *, /, ^, etc.):

Pop the top two operands from the stack.
Apply the operator to these two operands:
 Second operand = pop the first item (top of stack)
 First operand = pop the next item
 Push the result of the operation back onto the stack.
4. End of Expression: After all symbols have been processed, the stack should contain
only one element, which is the result of the expression.
5. Result: Pop the final element from the stack, which is the evaluated result of the postfix
expression.
Evaluate the postfix expression

A B C D ^ * + E - where A=2, B=5, C=3, D=1, E=5

Step Token Stack Explanation

1 2 2 Push operand onto the stack.
2 5 2, 5 Push operand onto the stack.
3 3 2, 5, 3 Push operand onto the stack.
4 1 2, 5, 3, 1 Push operand onto the stack.
5 ^ 2, 5, 3, 1 ^ 3 Apply exponentiation: 13 =1.
6 * 2, 5, 3 *1 Apply multiplication: 3⋅1 = 3.
7 + 2, 5 + 3 Apply addition: 5 + 3 = 8.
8 5 2, 8, 5 Push operand onto the stack.
9 - 2, 8 - 5 Apply subtraction: 8 – 5 = 3
10 - 2-3 Apply subtraction: 2 – 3 = −1

5_Write a C program that reads a postfix expression from keyboard and evaluate it
using a Stack

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define SIZE 20

int stack[SIZE];
int top = -1;

void push(int value)

{
if (top==SIZE-1)

DR. V SREENIVASULU 18
 printf("Stack overflow\n");
else
{
top++;
stack[top]=value;
}
}

int pop()
{
if(top==-1)
printf("The stack underflow\n");
else
{
int temp=stack[top];
top--;
return temp;
}
}

int evaluatePostfix(char* postfix)

{
int i = 0;
while (postfix[i] != '\0')
{
char ch = postfix[i];
if (isdigit(ch))
{
int operand = ch - '0';
push(operand);
}
else
{
int operand2 = pop();
int operand1 = pop();
switch (ch)
{
case '+':
push(operand1 + operand2);
break;
case '-':
push(operand1 - operand2);

DR. V SREENIVASULU 19
 break;
case '*':
push(operand1 * operand2);
break;
case '/':
if (operand2 == 0)
{
printf("Division by zero error\n");
exit(1);
}
push(operand1 / operand2);
break;
case '^':
push((int)pow(operand1, operand2));
break;
default:
printf("Invalid operator: %c\n", ch);
exit(1);
}
}
i++;
}
return pop();
}

int main()
{
char postfix[SIZE];
printf("Enter a postfix expression: ");
scanf("%s", postfix);

int result = evaluatePostfix(postfix);

printf("Result of postfix evaluation: %d\n", result);

return 0;
}
OUTPUT
Infix:A+B*C^D-E
Postfix:ABCD^*+E-
A=2, B=5, C=3, D=1, E=5

Enter a postfix expression: 2531^*+5-

Result of postfix evaluation: 12

DR. V SREENIVASULU 20
Queues ADT
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This
means that elements are added at the rear (end) of the queue and removed from the front,
making it to a real-life (or queue) where people join from the back and leave from the front.

Characteristics of a Queue

1. FIFO Approach: The element inserted first will be the first one to be removed.
2. Operations: Enqueue:
 Adding an element to the back of the queue.
 Dequeue: Removing an element from the front of the queue.
3. Two Ends:
 Front: Points to the element at the front of the queue (next to be removed).
 Rear: Points to the last element in the queue (the most recent addition).

Basic Queue Operations

1. Enqueue (Add):
 Adds an element to the end of the queue.
 Increment the rear pointer to accommodate the new element.
 If the queue is full, the enqueue operation is not performed queue overflow.
2. Dequeue (Remove):
 Removes an element from the front of the queue.
 Increment the front pointer to remove the element.
 If the queue is empty, the dequeue operation is not performed (queue underflow).
3. Peek/Front:
 Returns the element at the front of the queue without removing it.
4. isEmpty:
 Checks if the queue has no elements.
5. isFull:
 Checks if the queue has reached its maximum capacity.
Types of Queues
1. Simple Queue:
 A basic queue that follows the FIFO principle.
 Once an element is dequeued, the space it occupied is not reused. This leads to
unused space at the front when elements are removed.
2. Circular Queue:
 In a circular queue, the last position is connected back to the first position, forming
a circle.
 This allows reusing space at the beginning once elements are removed, preventing
overflow when there is available space.
 More efficient in memory usage than a simple queue.
3. Priority Queue:

DR. V SREENIVASULU 21
  Each element is assigned a priority.
 Elements with higher priority are dequeued before those with lower priority.
 Elements with the same priority follow FIFO order.
4. Deque (Double-Ended Queue):
 Allows insertion and deletion at both ends.
 Supports operations from both the front and rear ends.
Queue Implementation
Queues can be implemented in several ways, but the two primary methods are:
1. Using Arrays:
 The queue is represented by a fixed-size array.
 Array indices front and rear are used to keep track of the front and rear elements.
 Simple and straightforward, but resizing can be challenging without circular queue
implementation.
2. Using Linked Lists:
 Each element is a node containing data and a pointer to the next node.
 front and rear pointers keep track of the head and tail nodes.
 The queue can dynamically grow or shrink, making it more memory-efficient when
queue size changes frequently.

Applications of Queues
1. CPU Scheduling: In operating systems, queues manage tasks to execute based on
scheduling algorithms.
2. Print Spooling: Documents are queued in a spooler to be printed sequentially.
3. Network Buffers: Data packets are queued for processing in routers.
4. Customer Service: Real-world service lines follow a queue-based approach to serve
customers in FIFO order.

Queue Operations Complexity

Operation Simple Queue Circular Queue Linked List Queue
Enqueue O(1) O(1) O(1)
Dequeue O(1) O(1) O(1)
isFull O(1) O(1) N/A
O(1)
isEmpty O(1) O(1)

DR. V SREENIVASULU 22
6_Write a C Program that reads elements into a queue using arrays and display the
elements

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1;
int rear = -1;
int i;

void enqueue(int value)

{
if (rear == MAX-1)
printf("Queue overflow\n");
else
{
if (front == -1)
front++;
rear++;
queue[rear] = value;
printf("Enqueued: %d\n", value);
}

void dequeue()
{
int data;
if (front == -1)
{
printf("Queue underflow\n");
return;
}
else if(rear==0 && front==0)
{
data = queue[front];
printf("Dequeued element is %d\n",data);
front = -1;
rear = -1;
}
else
{

DR. V SREENIVASULU 23
 data = queue[front];
printf("Dequeued element is %d\n",data);
front++;
}

void display()
{
if (front==-1)
printf("Queue is empty\n");
else
{
printf("Queue elements are: ");
for (i = front; i <= rear; i++)
{
printf("%d ", queue[i]);
}
printf("\n");
}
}

int main()
{
int choice, value;

while (1)
{
printf("\nMenu:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice)
{
case 1:
printf("Enter the value to enqueue: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:

DR. V SREENIVASULU 24
 dequeue();
break;
case 3:
display();
break;
case 4:
printf("Exited\n");
return 0;
default:
printf("Invalid choice\n");
}
}
}

/*OUTPUT

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 2
Queue underflow

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue is empty

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 1
Enter the value to enqueue: 11
Enqueued: 11

Menu:
1. Enqueue
2. Dequeue

DR. V SREENIVASULU 25
3. Display
4. Exit
Enter your choice: 1
Enter the value to enqueue: 22
Enqueued: 22

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 2
Dequeued element is 11

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice:

Circular Queue
 A circular queue is a linear data structure in which the last position is connected back
to the first position to form a circle.

 This allows for efficient utilization of space, as the queue can reuse slots that become
available when elements are removed, even if the queue's logical end has been reached.

Characteristics of a Circular Queue

1. Circular Queue: Unlike a linear queue, where the elements are arranged in a straight
line, the elements in a circular queue are conceptually arranged in a circle.

2. Two Pointers
 Front: Points to the position of the first element in the queue.
 Rear: Points to the position where the next element will be inserted.

3. Fixed Size: Circular queues are usually implemented with a fixed-size array. The size
of the queue is determined at the time of its creation.

4. Efficient Space Utilization: When the queue becomes "full," but there are empty slots
in the beginning (due to deletions), these slots can be reused. This is unlike a linear
queue where such slots would remain unused.

DR. V SREENIVASULU 26
Operations in a Circular Queue

1. Enqueue (Insertion)
 Add an element to the position pointed to by rear.
 If the queue is full, no insertion is possible.
 Update the rear pointer circularly using the formula:
rear=(rear+1)mod size} = + 1) }
 rear=(rear+1)modsize
2. Dequeue (Deletion):
 Remove an element from the position pointed to by front.
 If the queue is empty, no deletion is possible.
 Update the front pointer circularly using the formula:
front=(front+1)mod size}
3. Peek/Front:
 Retrieve the front element without removing it.
 Return the value at the position pointed to by front.

Advantages of Circular Queue:

1. Efficient Use of Space: Reuses empty slots, avoiding memory wastage.
2. Simple Implementation: Easy to implement using an array with modular arithmetic.
3. Improved Performance: Fewer memory reallocations compared to dynamic structures.
Disadvantages of Circular Queue:
1. Fixed Size: If implemented using an array, the maximum size must be known
beforehand.
2. Complexity in Dynamic Expansion: Managing dynamic resizing in a circular queue is
more complex compared to a linear queue.
Applications of Circular Queue
1. CPU Scheduling: Circular queues are used in time-sharing systems to manage
processes in a round-robin fashion.
2. Buffer Management: Used in buffering mechanisms, like printers or network routers,
to efficiently manage memory.
3. Real-Time Data Streaming: Used to store packets of data that are continuously
arriving, such as audio/video streams.

DR. V SREENIVASULU 27
7_Write a C program that reads and prints elements by implementing A Circular
Queue using Arrays

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

void enqueue(int value)

{
if ((rear + 1) % MAX == front)
{
printf("Queue is full\n");
return;
}
if (front == -1)
{
front = 0;
//rear = 0;
}
rear = (rear + 1) % MAX;
queue[rear] = value;
printf("Inserted %d\n", value);
}

void dequeue()
{
if (front == -1)
{
printf("Queue is empty\n");
return;
}
//printf("Dequeued %d\n", queue[front]);
if (front == rear)
{
front = -1;
rear = -1;
}
else
{
printf("Dequeued %d\n", queue[front]);

DR. V SREENIVASULU 28
 front = (front + 1) % MAX;
}
}

void display()
{
if (front == -1)
{
printf("Queue is empty\n");
return;
}

printf("Queue elements are: ");

int i;
for(i = front; i != rear; i = (i + 1)%MAX)
printf("%d ", queue[i]);
printf("%d\n", queue[rear]);
}

int main()
{
int choice, value;
while (1)
{
printf("\nMenu:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter the choice: ");
scanf("%d", &choice);

switch (choice)
{
case 1:
printf("Enter the value: ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
dequeue();
break;

DR. V SREENIVASULU 29
 case 3:
display();
break;
case 4:
return 0;
default:
printf("Please enter correct option\n");
}
}
}
OUTPUT
Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 11
Inserted 11

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 22
Inserted 22

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 33
Inserted 33

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1

DR. V SREENIVASULU 30
Enter the value: 44
Inserted 44

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 55
Inserted 55

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 3
Queue elements are: 11 22 33 44 55

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 66
Queue is full

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 2
Dequeued 11

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 2
Dequeued 22

DR. V SREENIVASULU 31
Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 2
Dequeued 33

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 3
Queue elements are: 44 55

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 66
Inserted 66

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 77
Inserted 77

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 1
Enter the value: 77
Inserted 77

DR. V SREENIVASULU 32
Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice: 3
Queue elements are: 44 55 66 77 77

Menu:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter the choice:

=====End of UNIT 2 =====

DR. V SREENIVASULU 33