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

This answer is restricted. Please login to view the answer of this question.

Login Now

Queue as ADT:

A queue q of type T is a finite sequence of elements with the operations.

  1. MakeEmpty(q): To make q as an empty queue
  2. IsEmpty(q): To check whether the queue q is empty. Return true if queue is empty otherwise return false.
  3. IsFull(q): To check whether the queue q is full. Return true if queue is full otherwise return false.
  4. Enqueue(q, x): To insert an item x at the rear of the queue, if and only if q is not full
  5. Dequeue(q, x): To delete an item x from the front of the queue, if and only if q is not empty
  6. 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);
    }
}
If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .