Define queue as ADT. Describe its primitive operation on circular array implementation and singly linked list implementation.

Question

Suresh Chand · Accepted Answer

Queue as ADT: 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 queue is empty otherwise return false. IsFull(q): To check whether the queue q is full. Return true if queue is full otherwise return false. Enqueue(q, x): To insert an item x at the rear of the queue, if and only if q is not full Dequeue(q, x): To delete an item x from the front of the queue, if and only if q is not empty Traverse(q): To read entire queue that is to display the content of queue Circular Queue is an linear data structure in which the operations are performed based on FIFO principle and last portion is connected back to first position to make a circle. Operations of Circular Queue: 1. Declaration: #define MAXQUEUE 50 struct queue{ int front; int rear; int items[MAXQUEUE] } typedef struct queue qt; 2. IsEmpty function void IsEmpty(qt *q){ if(q→rear < q→front) return 1; else return 0; } 4. IsFull Function void IsFull(qt *q){ if(q→front = (q→rear+1) % MAXQUEUE) return 1; else return 0; } 5. Enqueue: void Enqueue(qt *q, int newitem){ if( IsFull(q) ){ printf('Queue is Full'); exit(0); }else{ q->rear = (q→rear + 1) % MAXQUEUE; q->items[q->rear] = newitem; } } 6. Dequeue: void Dequeue(qt *q){ if( IsEmpty(q) ){ printf('Queue is Empty'); exit(0); }else{ q->front = (q->rear + 1) % MAXQUEUE; return(q->items[q->front]); } } Queue can be implemented using link list. Here are the some basic operations: 1. Insert function: void insert(int item){ NodeType *node; node = (NodeType*) malloc(sizeof(NodeType)); if( rear == 0 ){ node->info = item; node->next = NULL; rear = front = node; }else{ node->info = item; node->next = NULL; rear->next = node; rear = node; } } 2. Delete Function void delete(){ NodeType *node; if( front == 0 ){ printf('Queue is empty'); exit(0); }else if(front->next == NULL){ temp = front; rear = front = NULL; printf('ItemDeleted'); free(temp); }else{ temp = front; front = temp->next; printf('Item Deleted'); free(temp); } }

Define queue as ADT. Describe its primitive operation on circular array implementation and singly linked list implementation.

Leave your Answer:

Hits Counter

Question

Define queue as ADT. Describe its primitive operation on circular array implementation and singly linked list implementation.

Leave your Answer: