Assignment 9: Linear Queue and circular queue
Queue:
A queue is a linear data structure which follows a particular order in which the operations are performed. The order is First in First out (FIFO) or Last in Last out (LILO).
Set A
a) Implement a linear queue library (st_queue.h) of integers using a static implementation of the queue and implementing the above six operations. Write a program that includes queue library and calls different queue operations
#include<stdio.h>
#define MAX 3
int a[MAX],front,rear;
void init()
{
front=-1;
rear=-1;
printf("\nStatic Queue is initialized\n");
}
void insert()
{
int number;
if(rear==MAX-1)
printf("\nQueue is full\n");
else
{
printf("\nEnter the value:");
scanf("%d",&number);
front=0;
rear=rear+1;
a[rear]=number;
printf("\nValue Enqueued\n");
}
}
void delete1()
{
if(front==-1 || rear==front-1)
printf("\nQueue is empty\n");
else
{
printf("\nDeleted value is %d",a[front]);
front=front+1;
}
}
void isfull()
{
if(rear==MAX-1)
printf("\nQueue is full\n");
else
printf("\nQueue is not full");
}
void isempty()
{
if(front==-1 || rear==front-1)
printf("\nQueue is empty\n");
else
printf("\nQueue is not empty");
}
void peek()
{
if(front==-1 || rear==front-1)
printf("\nQueue is empty\n");
else
printf("\nValue at front is %d",a[front]);
}
Save this above code in the stack library file as stqueue.h
#include<stdio.h>
#include<stdlib.h>
#include "stqueue.h"
int main()
{
int ch;
while(1)
{
printf("\n----Static Queue----\n");
printf("\n1.Init\n");
printf("2.Insert\n");
printf("3.Delete\n");
printf("4.Peek\n");
printf("5.IsEmpty\n");
printf("6.IsFull\n");
printf("7.Exit\n");
printf("Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:init(); break;
case 2:insert(); break;
case 3:delete1(); break;
case 4:peek(); break;
case 5:isempty(); break;
case 6:isfull(); break;
case 7:exit(0);
}
}
}
Save this file as queue.c and compile and run the queue.c
b) Implement a circular queue library (cir_queue.h) of integers using a dynamic (circular linked list) implementation of the queue and implementing the above five operations. Write a menu driven program that includes queue library and calls different queue operations.
// Circular Queue implementation in C
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// Check if the queue is full
int isFull() {
if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
return 0;
}
// Check if the queue is empty
int isEmpty() {
if (front == -1) return 1;
return 0;
}
// Adding an element
void enQueue(int element) {
if (isFull())
printf("\n Queue is full!! \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
printf("\n Queue is empty !! \n");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element, so we reset the
// queue after dequeing it. ?
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}
// Display the queue
void display() {
int i;
if (isEmpty())
printf(" \n Empty Queue\n");
else {
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE) {
printf("%d ", items[i]);
}
printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear);
}
}
int main() {
// Fails because front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Fails to enqueue because front == rear + 1
enQueue(8);
return 0;
}
Set B
a) Implement a linear queue library (dyqueue.h) of integers using a dynamic (circular linked list) implementation of the queue and implementing the above five operations. Write a driver program that includes queue library and calls different queue operations.
// dyqueue.h
struct node
{
int data;
struct node *next;
};
struct node * Create()
{
return malloc(sizeof(struct node));
}
int isEmpty(struct node *head)
{
return (head == NULL) ? 1 : 0;
}
void Append(struct node **head, int data)
{
struct node *newnode;
newnode = Create();
newnode->data = data;
newnode->next = NULL;
if( *head==NULL )
*head = newnode;
else
{
struct node *temp = *head;
do
{
temp = temp->next;
}while(temp->next != *head );
temp->next = newnode;
}
newnode->next = *head;
}
void Display(struct node *head)
{
struct node *temp = head;
printf("\n\t[");
if( temp != NULL )
{
do
{
printf("%d,",temp->data);
temp = temp->next;
} while( temp != head );
}
printf("]");
}
int Delete(struct node **head, int data)
{
struct node *temp = *head, *prev;
if( temp != NULL )
{
do
{
if( temp->data == data )
{
if( temp->next == *head )
head = NULL;
else
if( temp == *head )
{
struct node *temp2 = *head;
while( temp2->next != *head )
temp2 = temp2->next;
temp2->next = (*head)->next;
*head = (*head)->next;
}
else
prev->next = temp->next;
free(temp);
return 1;
}
prev = temp;
temp = temp->next;
} while(temp != *head);
return 0;
}
}
int Insert(struct node **head, int data, int pos)
{
struct node *newnode;
newnode = Create();
newnode->data = data;
if( pos < 1 )
return 0;
if( pos == 1 )
{
if( *head==NULL )
{
*head = newnode;
newnode->next = *head;
return 1;
}
else
{
newnode->next = *head;
*head = newnode;
return 1;
}
}
else
if( pos > 1 )
{
struct node *temp = *head;
if( temp != NULL )
{
int i;
for(i=1; i<pos-1; ++i)
{
temp = temp->next;
if( temp == *head)
return 0;
}
newnode->next = temp->next;
temp->next = newnode;
return 1;
}
}
}
The above file is save as dyqueue.h
#include <stdio.h>
#include <stdlib.h>
#include "dyqueue.h"
int menu()
{
int ch;
system("clear");
printf("\n\t0) Exit");
printf("\n\t1) Append");
printf("\n\t2) Delete");
printf("\n\t3) Insert");
printf("\n\t4) Display");
printf("\n\tEnter Choice : ");
scanf("%d",&ch);
return ch;
}
main()
{
struct node *head=NULL,*end=NULL;
int ch;
while((ch=menu())!=0)
{
if(ch==1)
{
int data;
printf("\tenter data:");
scanf("%d",&data);
Append(&head,data);
}
else
if(ch==2)
{
int data;
printf("\tenter data to delete : ");
scanf("%d",&data);
if( Delete(&head,data) == 1 )
printf("\n\tDeleted");
else
printf("\n\tNot Deleted");
getchar();getchar();
}
else
if(ch==3)
{
int data,position;
printf("\tenter data to insert : ");
scanf("%d",&data);
printf("\tenter position to insert at : ");
scanf("%d",&position);
if( Insert(&head,data, position) == 1 )
printf("\n\tInserted");
else
printf("\n\tNot Inserted");
getchar();getchar();
}
else
if(ch==4)
{
Display(head);
getchar();getchar();
}
}
}
b)Write a program to reverse the elements of a queue using queue library.
No comments:
Post a Comment