Smartzworld.com Smartworld.

asia

case 10 :

printf("\n Number of nodes: %d", countnode(start));

break;

case 11:

exit(0);

getch();

UNIT – II

STACKS AND QUEUES

Basic Stack Operations:

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO)
principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and
pop the item out of the stack. A stack is a limited access data structure - elements can be added and
removed from the stack only at the top. push adds an item to the top of the stack, pop removes the
item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book,
also you can add a new book on the top.

A stack may be implemented to have a bounded capacity. If the stack is full and does not contain
enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state.
The pop operation removes an item from the top of the stack. A pop either reveals previously concealed
items or results in an empty stack, but, if the stack is empty, it goes into underflow state, which means

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

no items are present in stack to be removed.

Representation of a 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.

When a element is added to a stack, the operation is performed by push().

When an element is taken off from the stack, the operation is performed by pop().

Source code for stack operations, using array:

Procedure:

STACK: Stack is a linear data structure which works under the principle of last in first out. Basic
operations: push, pop, display.

1. PUSH: if (top==MAX), display Stack overflow else reading the data and making stack [top] =data
and incrementing the top value by doing top++.
2. Pop: if (top==0), display Stack underflow else printing the element at the top of the stack and

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

decrementing the top value by doing the top.

3. DISPLAY: IF (TOP==0), display Stack is empty else printing the elements in the stack from stack
[0] to stack [top].
# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

# define MAX 6

int stack[MAX];

int top = 0;

int menu()

int ch;

clrscr();

printf("\n … Stack operations using ARRAY... ");

printf("\n -----------**********-------------\n");

printf("\n 1. Push ");

printf("\n 2. Pop ");

printf("\n 3. Display");

printf("\n 4. Quit ");

printf("\n Enter your choice: ");

scanf("%d", &ch);

return ch;

void display()

int i;

if(top == 0)

printf("\n\nStack empty..");

return;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

else

printf("\n\nElements in stack:");

for(i = 0; i < top; i++)

printf("\t%d", stack[i]);

void pop()

if(top == 0)

printf("\n\nStack Underflow..");

return;

else

printf("\n\npopped element is: %d ", stack[--top]);

void push()

int data;

if(top == MAX)

printf("\n\nStack Overflow..");

return;

else

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

printf("\n\nEnter data: ");

scanf("%d", &data);

stack[top] = data;

top = top + 1;

printf("\n\nData Pushed into the stack");

void main()

int ch;

do

ch = menu();

switch(ch)

case 1:

push();

break;

case 2:

pop();

break;

case 3:

display();

break;

case 4:

exit(0);

getch();

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

} while(1);

Output:

Stack using arrays:

**************************************

1.Push

2.Pop

3.Display

4.Quit

Enter your choice:1

Enter charecter:2

charecter inserted successfully

Stack using arrays:

**************************************

1.Push

2.Pop

3.Display

4.Quit

Enter your choice:2

The popped element from stack is:2

Stack using arrays:

**************************************

1.Push

2.Pop

3.Display

4.Quit

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Enter your choice:3

Stack is empty

Stack using arrays:

**************************************

1.Push

2.Pop

3.Display

4.Quit

Enter your choice:4

Linked List Implementation of Stack:

We can represent a stack as a linked list. In a stack push and pop operations are performed at one end
called top. We can perform similar operations at one end of list using top pointer.

Source code for stack operations, using linked list:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

struct stack

int data;

struct stack *next;

};

typedef struct stack node;

node *start = NULL;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

node *top = NULL;

node* getnode()

node *temp;

temp=(node *)malloc(sizeof(node));

printf("\n enter data : ");

scanf("%d",&temp -> data);

temp -> next=NULL;

return temp;

void push(node *newnode)

node *temp;

if(newnode==NULL)

Printf ("\n stack overflow... ");

return;

if(start == NULL)

start = newnode;

top = newnode;

else

temp = start;

while(temp -> next!= NULL)

temp = temp -> next;

temp -> next =newnode;

top = newnode;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Printf ("\n\n\t data pushed into stack...");

void pop()

node *temp;

if(top == NULL)

printf("\n\n\t stack overflow...");

return;

temp = start;

if(start -> next == NULL)

printf("\n\n\t popped element is %d",top -> data);

start = NULL;

free(top);

top = NULL;

else

while(temp -> next!=top)

temp = temp -> next;

temp -> next = NULL;

printf("\n\n\t popped element is %d", top -> data);

free(top);

top = temp;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

void display()

node *temp;

if(top == NULL)

printf("\n\n\t stack is empty...");

else

temp = start;

Printf ("\n\n\t elements in the stack..\n");

printf("%5d",temp -> data);

while(temp!= top)

temp = temp -> next;

printf("%5d",temp -> data);

int menu()

int ch;

printf("\n\t STACK OPERATIONS USING POINTERS : ");

printf("\n ----******----- ");

printf("\n 1. Push ");

Printf ("\n 2. Pop ");

printf("\n 3. Display ");

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

printf("\n 4. Quit");

printf("\n enter your choice : ");

scanf("%d",&ch);

return ch;

void main()

int ch;

node *newnode;

do

ch=menu();

switch(ch)

case 1 :

newnode=getnode();

push(newnode);

break;

case 2 :

pop();

break;

case 3 :

display();

break;

case 4 :

return;

getch();

}while(1);

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Output:

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 1

enter data : 10

data pushed into Stack

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 1

enter data : 20

data pushed into Stack

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

4. Quit

enter your choice : 1

enter data : 30

data pushed into Stack

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 3

elements in the stack..

10 20 30

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 2

popped element is 30

STACK OPERATIONS USING POINTERS

--------------******--------------------

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 3

elements in the stack..

10 20

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 2

popped element is 20

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 3

elements in the stack..

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

10

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 2

popped element is 10

STACK OPERATIONS USING POINTERS

--------------******--------------------

1. Push

2. Pop

3. Display

4. Quit

enter your choice : 3

stack empty

Stack Applications:

1. Stack is used by compilers to check for balancing of parentheses, brackets and braces.
2. Stack is used to evaluate a postfix expression.
3. Stack is used to convert an infix expression into postfix/prefix form.
4. In recursion, all intermediate arguments and return values are stored on the processor’s
stack.
5. During a function call the return address and arguments are pushed onto a stack and on
return they are popped off.
6. Depth first search uses a stack data structure to find an element from a graph.
Factorial Calculation:

Source Code:

#include<stdio.h>

#include<conio.h>

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

void main()

int i,n,stack[20],top=0,f=1;

printf("Enter n:");

scanf("%d",&n);

i=n;

while(n>0)

stack[top]=n;

top++;

n--;

while(top>0)

f=f*stack[--top];

printf("factorial of %d is %d",i,f);

Output:

Enter n:5

factorial of 5 is 120

In-fix- to Postfix Transformation:

Procedure:

Procedure to convert from infix expression to postfix expression is as follows:

1. Scan the infix expression from left to right.

2. a) If the scanned symbol is left parenthesis, push it onto the stack.
b) If the scanned symbol is an operand, then place directly in the postfix expression
(output).
c) If the symbol scanned is a right parenthesis, then go on popping all the items from
the stack and place them in the postfix expression till we get the matching left
parenthesis.
jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

d) If the scanned symbol is an operator, then go on removing all the operators from
the stack and place them in the postfix expression, if and only if the precedence of
the operator which is on the top of the stack is greater than (or equal) to the
precedence of the scanned operator and push the scanned operator onto the stack
otherwise, push the scanned operator onto the stack.

Convert the following infix expression A + B * C – D / E * H into its equivalent postfix expression.

Symbol Postfix string Stack Remarks

A A

+ A +

B AB +

* AB +*

C ABC -

- ABC*+ -

D ABC*+D -

/ ABC*+D -/

E ABC*+DE -/

* ABC*+DE/ -*

H ABC*+DE/H -*

End of The input is now empty. Pop the output symbols from
string ABC*+DE/H*- the stack until it is empty.

Source Code:

#include<stdio.h>

#include<string.h>

char opstack[50];

char infix[50];

char postfix[50];

int i,j,top=0;

void pop();

void push(char);

int lesspriority(char,char);

void main()

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

char ch;

printf("enter infix expression:\n");

gets(infix);

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

switch(ch)

case ' ':break;

case '(':

case '+':

case '-':

case '*':

case '/':

case '^':

case '%':

push(ch);

break;

case ')':

pop();

break;

default:

postfix[j]=ch;

j++;

while(top>=0)

postfix[j]=opstack[--top];

j++;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

postfix[--j]='\0';

printf("\n infix expression:%s",infix);

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

int lesspriority(char op,char op_at_stack)

int k;

int pv1;

int pv2;

char operators[]={'+','-','*','/','%','^','('};

int priority_value[]={0,0,1,1,2,3,4};

if(op_at_stack=='(')

return 0;

for(k=0;k<6;k++)

if(op==operators[k])

pv1=priority_value[k];

for(k=0;k<6;k++)

if(op_at_stack==operators[k])

pv2=priority_value[k];

if(pv1<pv2)

return 1;

else

return 0;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

void push(char op)

if(top==0)

opstack[top]=op;

top++;

else

if(op!='(')

while(lesspriority(op,opstack[top-1])==1 && top>0)

postfix[j]=opstack[--top];

j++;

opstack[top]=op;

top++;

void pop()

While (opstack [--top]! ='(')

postfix[j]=opstack[top];

j++;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Output:

enter infix expression:

(A+B)*(C-D)

infix expression: (A+B)*(C-D)

postfix expression: AB+CD-*

Evaluating Arithmetic Expressions:

Procedure:

The postfix expression is evaluated easily by the use of a stack. When a number is seen, it is pushed onto
the stack; 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.

Evaluate the postfix expression: 6 5 2 3 + 8 * + 3 + *

Symbol Operand 1 Operand 2 Value Stack Remarks

6 6

5 6, 5

2 6, 5, 2

The first four symbols are

3 6, 5, 2, 3
placed on the stack.

Next a ‘+’ is read, so 3 and 2

+ 2 3 5 6, 5, 5 are popped from the stack
and their sum 5, is pushed

8 2 3 5 6, 5, 5, 8 Next 8 is pushed

Now a ‘*’ is seen, so 8 and 5

* 5 8 40 6, 5, 40 are popped as 8 * 5 = 40 is
pushed

Next, a ‘+’ is seen, so 40 and

+ 5 40 45 6, 45 5 are popped and 40 + 5 = 45
is pushed

3 5 40 45 6, 45, 3 Now, 3 is pushed

Next, ‘+’ pops 3 and 45 and

+ 45 3 48 6, 48
pushes 45 + 3 = 48 is pushed

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Finally, a ‘*’ is seen and 48

* 6 48 288 288 and 6 are popped, the result
6 * 48 = 288 is pushed

Source Code:

include<stdio.h>

#include<conio.h>

void evaluate_postfix(char a[20])

int i=0,top=0,n1,n2,r,s[20];

for(i=0;a[i]!='\0';i++)

if((a[i]>=48)&&(a[i]<=57))

s[top]=a[i]-48;

top++;

else

n2=s[--top];

n1=s[--top];

switch(a[i])

case '+': r=n1+n2;break;

case '-': r=n1-n2;break;

case '*': r=n1*n2;break;

case '/': r=n1/n2;break;

case '^': r=n1^n2;break;

s[top]=r;

top++;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

printf("RESULT IS %d",s[0]);

getch();

void main()

char a[20];

printf("Enter the postfix expresion:");

gets(a);

evaluate_postfix(a);

Output:

Enter the postfix expresion:23+5*

RESULT IS 25

Basic Queue Operations:

A queue is a data structure that is best described as "first in, first out". A queue is another special kind of
list, where items are inserted at one end called the rear and deleted at the other end called the front. A
real world example of a queue is people waiting in line at the bank. As each person enters the bank, he
or she is "enqueued" at the back of the line. When a teller becomes available, they are "dequeued" at
the front of the line.

Representation of a Queue using Array:

Let us consider a queue, which can hold maximum of five elements. Initially the queue is empty.

0 1 2 3 4
Q u e u e E mp t y
F RO NT = RE A R = 0

F R

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

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

0 1 2 3 4
RE A R = RE A R + 1 = 1
11
F RO NT = 0

F R

Next, insert 22 to the queue. Then the queue status is:

0 1 2 3 4
RE A R = RE A R + 1 = 2
11 22
F RO NT = 0

F R

Again insert another element 33 to the queue. The status of the queue is:

0 1 2 3 4
RE A R = RE A R + 1 = 3
11 22 33
F RO NT = 0

F R

Now, delete an element. The element deleted is the element at the front of the queue. So the status of
the queue is:

0 1 2 3 4
RE A R = 3
22 33
F RO NT = F R O NT + 1 = 1

F R

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

0 1 2 3 4
RE A R = 3
33
F RO NT = F R O NT + 1 = 2

F R

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

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

0 1 2 3 4
RE A R = 5
33 44 55
F RO NT = 2

F R

Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the rear crossed
the maximum size of the queue (i.e., 5). There will be queue full signal. The queue status is as follows:

0 1 2 3 4
RE A R = 5
33 44 55
F RO NT = 2

F R

Now it is not possible to insert an element 66 even though there are two vacant positions in the linear
queue. To over come 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:

0 1 2 3 4
RE A R = 4
33 44 55 66
F RO NT = 0

F R

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.

Procedure for Queue operations using array:

In order to create a queue we require a one dimensional array Q(1:n) and two variables front and rear.
The conventions we shall adopt for these two variables are that front is always 1 less than the actual
front of the queue and rear always points to the last element in the queue. Thus, front = rear if and only
if there are no elements in the queue. The initial condition then is front = rear = 0.

The various queue operations to perform creation, deletion and display the elements in a queue are as
follows:

1. insertQ(): inserts an element at the end of queue Q.

2. deleteQ(): deletes the first element of Q.
3. displayQ(): displays the elements in the queue.
Source Code:

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

# include <stdio.h>

# include <conio.h>

# define MAX 6

int Q[MAX];

int front, rear;

void insertQ()

int data;

if(rear == MAX)

printf("\n Linear Queue is full");

return;

else

printf("\n Enter data: ");

scanf("%d", &data);

Q[rear] = data;

rear++;

printf("\n Data Inserted in the Queue ");

void deleteQ()

if(rear == front)

printf("\n\n Queue is Empty..");

return;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

else

printf("\n Deleted element from Queue is %d", Q[front]);

front++;

void displayQ()

int i;

if(front == rear)

printf("\n\n\t Queue is Empty");

return;

else

printf("\n Elements in Queue are: ");

for(i = front; i < rear; i++)

printf("%d\t", Q[i]);

int menu()

int ch;

clrscr();

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

printf("\n \tQueue operations using ARRAY..");

printf("\n -----------**********-------------\n");

printf("\n 1. Insert ");

printf("\n 2. Delete ");

printf("\n 3. Display");

printf("\n 4. Quit ");

printf("\n Enter your choice: ");

scanf("%d", &ch);

return ch;

void main()

int ch;

do

ch = menu();

switch(ch)

case 1:

insertQ();

break;

case 2:

deleteQ();

break;

case 3:

displayQ();

break;

case 4:

return;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

getch();

} while(1);

Output:

Queue using arrays:

*****************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:1

Enter data:2

Data entered successfully

Queue using arrays:

*****************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:1

Enter data:25

Data entered successfully

Queue using arrays:

*****************

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:2

The deleted element from the queue is:2

Queue using arrays:

*****************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:1

Enter data:36

Data entered successfully

Queue using arrays:

*****************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:1

Enter data:25

Data entered successfully

Queue using arrays:

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

*****************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:2

The deleted element from the queue is:25

Queue using arrays:

****************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:3

The elements in the queue are: 36 25

Queue using arrays:

****************

1.Insertion

2.Deletion

3.Display

4.QUIT

Linked List Implementation of Queue: We can represent a queue as a linked list. In a queue data is
deleted from the front end and inserted at the rear end. We can perform similar operations on the two
ends of a list. We use two pointers front and rear for our linked queue implementation.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Source Code:

# include <stdio.h>

# include <stdlib.h>

# include <conio.h>

struct queue

int data;

struct queue *next;

};

typedef struct queue node;

node *front = NULL;

node *rear = NULL;

node* getnode()

node *temp;

temp = (node *) malloc(sizeof(node)) ;

printf("\n Enter data ");

scanf("%d", &temp -> data);

temp -> next = NULL;

return temp;

void insertQ()

node *newnode;

newnode = getnode();

if(newnode == NULL)

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

printf("\n Queue Full");

return;

if(front == NULL)

front = newnode;

rear = newnode;

else

rear -> next = newnode;

rear = newnode;

printf("\n\n\t Data Inserted into the Queue..");

void deleteQ()

node *temp;

if(front == NULL)

printf("\n\n\t Empty Queue..");

return;

temp = front;

front = front -> next;

printf("\n\n\t Deleted element from queue is %d ", temp -> data);

free(temp);

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

void displayQ()

node *temp;

if(front == NULL)

printf("\n\n\t\t Empty Queue ");

else

temp = front;

printf("\n\n\n\t\t Elements in the Queue are: ");

while(temp != NULL )

printf("%5d

temp = temp

char menu()

char ch;

clrscr();

printf("\n \t..Queue operations using pointers.. ");

printf("\n\t -----------**********-------------\n");

printf("\n 1. Insert ");

printf("\n 2. Delete ");

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

printf("\n 3. Display");

printf("\n 4. Quit ");

printf("\n Enter your choice: ");

ch = getche();

return ch;

void main()

char ch;

do

ch = menu();

switch(ch)

case '1' :

inser

brea

case '2' :

delet

brea

case '3' :

displ

brea

case '4':

retur

getch();

} while(ch != '4');

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Output:

QUEUE OPERATIONS USING POINTERS :

-----------------******-------------------

1. Insert

2. Delete

3. Display

4. Quit

enter your choice : 1

enter data : 10

data inserted into Queue...

QUEUE OPERATIONS USING POINTERS :

---------------******--------------------

1. Insert

2. Delete

3. Display

4. Quit

enter your choice : 1

enter data : 20

data inserted into Queue...

QUEUE OPERATIONS USING POINTERS :

----------------******-------------------

1. Insert

2. Delete

3. Display

4. Quit

enter your choice : 1

enter data : 30

data inserted into Queue...

QUEUE OPERATIONS USING POINTERS :

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

----------------******-------------------

1. Insert

2. Delete

3. Display

4. Quit

enter your choice : 2

popped element is 10

QUEUE OPERATIONS USING POINTERS :

---------------******--------------------

1. Insert

2. Delete

3. Display

4. Quit

enter your choice : 3

Elements in the Queue...

20 30

QUEUE OPERATIONS USING POINTERS :

-----------------******------------------

1. Insert

2. Delete

3. Display

4. Quit

enter your choice : 2

popped element is 20

QUEUE OPERATIONS USING POINTERS :

------------------******-----------------

1. Insert

2. Delete

3. Display

4. Quit

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

enter your choice : 2

popped element is 30

QUEUE OPERATIONS USING POINTERS :

------------------*****-------------------

1. Insert

2. Delete

3. Display

4. Quit

enter your choice : 3

QUEUE is EMPTY...

Applications of Queues:

1. It is used to schedule the jobs to be processed by the CPU.

2. When multiple users send print jobs to a printer, each printing job is kept in the printing
queue. Then the printer prints those jobs according to first in first out (FIFO) basis.

3. Breadth first search uses a queue data structure to find an element from a graph.
Disadvantages of Linear Queue:
There are two problems associated with linear queue. They are:

 Time consuming: linear time to be spent in shifting the elements to the beginning of the
queue.

 Signaling queue full: even if the queue is having vacant position.

Round Robin Algorithm:

The round-robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is
similar to FCFS scheduling, but pre-emption is added to switch between processes. A small unit
of time, called a time quantum or time slices, is defined. A time quantum is generally from 10 to
100 milliseconds. The ready queue is treated as a circular queue. To implement RR scheduling

 We keep the ready queue as a FIFO queue of processes.

 New processes are added to the tail of the ready queue.
 The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt
after 1 time quantum, and dispatches the process.
 The process may have a CPU burst of less than 1 time quantum.
o In this case, the process itself will release the CPU voluntarily.
o The scheduler will then proceed to the next process in the ready queue.
 Otherwise, if the CPU burst of the currently running process is longer than 1 time
quantum,
o The timer will go off and will cause an interrupt to the OS.
o A context switch will be executed, and the process will be put at the tail of the
ready queue.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

o The CPU scheduler will then select the next process in the ready queue.

The average waiting time under the RR policy is often long. Consider the following set of
processes that arrive at time 0, with the length of the CPU burst given in milliseconds: (a time
quantum of 4 milliseconds)

Burst Waiting Turnaround

Process Time Time Time

24 6 30

3 4 7

3 7 10

Average - 5.66 15.66

Using round-robin scheduling, we would schedule these processes according to the following
chart:

Source Code:
#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 4

#define TS 5

struct process

char pname[20];

int bt;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

int wt;

}pq[MAX];

int f,r;

void readprocess()

printf("\nEnter the process name nd execution time:\n");

for(r=0;r<MAX;r++)

scanf("%s%d",pq[r].pname,&pq[r].bt);

pq[r].wt=0;

void calculatewt()

int i,j,ctr=0;

f=0;

while(1)

if(pq[f].bt>0)

pq[f].bt=pq[f].bt-TS;

j=f;

for(i=0;i<MAX;i++)

j=(j+1)%MAX;

if(j == f)

break;

if(pq[j].bt>0)

pq[j].wt+=TS;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

f=(f+1)%MAX;

ctr=0;

for(i=0;i<MAX;i++)

if(pq[i].bt<=0)

ctr++;

if(ctr==MAX)

break;

void printwt()

float twt=0;int i;

for(i=0;i<MAX;i++)

printf("\n%s\t%d",pq[i].pname,pq[i].wt);

twt+=pq[i].wt;

printf("\nAvgerage waiting time : %f",(twt/MAX));

void main()

readprocess();

calculatewt();

printwt();

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Output:
Enter the process name nd execution time:

P1

20

P2

30

P3

15

P4

P1 35

P2 40

P3 35

P4 15

Avgerage waiting time : 31.250000

DEQUE(Double Ended Queue):

A double-ended queue (dequeue, often abbreviated to deque, pronounced deck) generalizes a queue,
for which elements can be added to or removed from either the front (head) or back (tail).It is also often
called a head-tail linked list. Like an ordinary queue, a double-ended queue is a data structure it
supports the following operations: enq_front, enq_back, deq_front, deq_back, and empty. Dequeue can
be behave like a queue by using only enq_front and deq_front , and behaves like a stack by using only
enq_front and deq_rear.

The DeQueue is represented as follows.

DEQUE can be represented in two ways they are

1) Input restricted DEQUE(IRD)

2) output restricted DEQUE(ORD)

The output restricted DEQUE allows deletions from only one end and input restricted DEQUE allow
insertions at only one end. The DEQUE can be constructed in two ways they are

1) Using array

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

2)Using linked list

Operations in DEQUE

1. Insert element at back

2. Insert element at front
3. Remove element at front
4. Remove element at back

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Applications of DEQUE:

1. The A-Steal algorithm implements task scheduling for several processors (multiprocessor
scheduling).
2. The processor gets the first element from the deque.
3. When one of the processor completes execution of its own threads it can steal a thread from
another processor.
4. It gets the last element from the deque of another processor and executes it.
Circular Queue:

Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is
connected back to the first node to make a circle.

 Circular linked list fallow the First In First Out principle

 Elements are added at the rear end and the elements are deleted at front end of the queue
 Both the front and the rear pointers points to the beginning of the array.
 It is also called as “Ring buffer”.
 Items can inserted and deleted from a queue in O(1) time.
Circular Queue can be created in three ways they are

 Using single linked list

 Using double linked list

 Using arrays

Representation of Circular Queue:

Let us consider a circular queue, which can hold maximum (MAX) of six elements. Initially the queue is
empty.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia
F R

5 0

1 Queue E mp t y
4 MAX = 6
F RO N T = RE A R = 0
C O U NT = 0

3 2

C irc u l a r Q u e u e

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

5 0
R
11

1 F RO N T = 0
4 RE A R = ( RE A R + 1) % 6 = 1
C O U NT = 1

3 2

C irc u l a r Q u e u e

Insert new elements 22, 33, 44 and 55 into the circular queue. The circular queue status is:

F
R

0
5
11

22 1 F RO N T = 0, RE A R = 5
4 55
RE A R = RE A R % 6 = 5
C O U NT = 5

44 33

3 2

C irc u l a r Q u e u e

Now, delete an element. The element deleted is the element at the front of the circular queue. So, 11 is
deleted. The circular queue status is as follows:

0
5
F

22 1 F RO N T = (F R O N T + 1) % 6 = 1
4 55
RE A R = 5
C O U NT = C O U NT - 1 = 4

44 33

3 2

C irc u l a r Q u e u e

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

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

0
5

1 F RO N T = (F R O N T + 1) % 6 = 2
4 55
RE A R = 5
C O U NT = C O U NT - 1 = 3

44 33
F
3 2

C irc u l a r Q u e u e

Again, insert another element 66 to the circular queue. The status of the circular queue is:

0
5
66

55 1
4 F RO N T = 2
RE A R = ( RE A R + 1) % 6 = 0
C O U NT = C O U NT + 1 = 4
44 33

3 2 F

C irc u l a r Q u e u e

Now, insert new elements 77 and 88 into the circular queue. The circular queue status is:

0
5
66 77

55 88 1
4 F RO NT = 2, RE A R = 2
RE A R = RE A R % 6 = 2
C O U NT = 6
44 33
R
3 2
F

C irc u l ar Q u e u e

Now, if we insert an element to the circular queue, as COUNT = MAX we cannot add the element to
circular queue. So, the circular queue is full.

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Source Code:

# include <stdio.h>

# include <conio.h>

# define MAX 6

int CQ[MAX];

int front = 0;

int rear = 0;

int count = 0;

void insertCQ()

int data;

if(count == MAX)

printf("\n Circular Queue is Full");

else

printf("\n Enter data: ");

scanf("%d", &data);

CQ[rear] = data;

rear = (rear + 1) % MAX;

count ++;

printf("\n Data Inserted in the Circular Queue ");

void deleteCQ()

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

if(count == 0)

printf("\n\nCircular Queue is Empty..");

else

printf("\n Deleted element from Circular Queue is %d ", CQ[front]);

front = (front + 1) % MAX;

count --;

void displayCQ()

int i, j;

if(count == 0)

printf("\n\n\t Circular Queue is Empty ");

else

printf("\n Elements in Circular Queue are: ");

j = count;

for(i = front; j != 0; j--)

printf("%d\t", CQ[i]);

i = (i + 1) % MAX;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

int menu()

int ch;

clrscr();

printf("\n \t Circular Queue Operations using ARRAY..");

printf("\n -----------**********-------------\n");

printf("\n 1. Insert ");

printf("\n 2. Delete ");

printf("\n 3. Display");

printf("\n 4. Quit ");

printf("\n Enter Your Choice: ");

scanf("%d", &ch);

return ch;

void main()

int ch;

do

ch = menu();

switch(ch)

case 1:

insertCQ();

break;

case 2:

deleteCQ();

break;

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

case 3:

displayCQ();

break;

case 4:

return;

default:

printf("\n Invalid Choice ");

getch();

} while(1);

Output:

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:1

Enter data:3

Data entered successfully

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

4.QUIT

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

Enter your choice:1

Enter data:2

Data entered successfully

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:2

Data deleted at queue is:3

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:1

Enter data:36

Data entered successfully

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

jntuworldupdates.org Specworld.in
Smartzworld.com Smartworld.asia

4.QUIT

Enter your choice:1

Enter data:32

Data entered successfully

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:2

Data deleted at queue is:2

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:3

3 2

Circular Queue using arrays:

*****************************

1.Insertion

2.Deletion

3.Display

4.QUIT

Enter your choice:4

jntuworldupdates.org Specworld.in