Data Structures and Algorithms - Old Questions
1. Define Queue as an ADT. Write a program for basic operations in Linear queue in array implementation.
Answer
AI is thinking...
A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).
Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.
A queue q of type T is a finite sequence of elements with the operations:
- MakeEmpty(q): To make q as an empty queue
- IsEmpty(q): To check whether the queue q is empty. Return true if q is empty, return false otherwise.
- IsFull(q): To check whether the queue q is full. Return true in q is full, return false otherwise.
- Enqueue(q, x): To insert an item x at the rear of the queue, if and only if q is not full.
- Dequeue(q): To delete an item from the front of the queue q. if and only if q is not empty.
- Traverse (q): To read entire queue that is display the content of the queue.
#include<stdio.h>
#include<conio.h>
#define
SIZE 10
void
enQueue(int);
void
deQueue();
void
display();
int
queue[SIZE], front = -1, rear = -1;
void
main()
{
int value, choice;
clrscr();
while(1){
printf("\\n\\n***** MENU
*****\\n");
printf("1. Insertion\\n2.
Deletion\\n3. Display\\n4. Exit");
printf("\\nEnter your choice:
");
scanf("%d",&choice);
switch(choice){
case
1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\\nWrong selection!!! Try
again!!!");
}
}
}
void
enQueue(int value){
if(rear == SIZE-1)
printf("\\nQueue is Full!!! Insertion
is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\\nInsertion
success!!!");
}
}
void
deQueue(){
if(front == rear)
printf("\\nQueue is Empty!!! Deletion
is not possible!!!");
else{
printf("\\nDeleted : %d",
queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void
display(){
if(rear == -1)
printf("\\nQueue is Empty!!!");
else{
int i;
printf("\\nQueue elements
are:\\n");
for(i=front; i<=rear; i++)
printf("%d\\t",queue[i]);
}
}