Weekly Test Key
Unit 4: Queues
Short Answer Questions (2 Marks each)
1. What is the condition to check Queue Full and Empty?
In a linear (array-based) queue of size MAX:
Queue Full:
rear == MAX - 1
Queue Empty:
front == -1 || front>rear
Example check in C:
if (rear == MAX - 1)
printf("QueueisFull\n");
if(front==-1||front>rear)
printf("Queue is Empty\n");
2. Importance of front and rear in Queues
A queue uses two pointers/indices to manage its elements:
• front — Points to the first (oldest) element in the queue.
– Used during Dequeue (deletion) operation.
– When front == -1, the queue is empty.
• rear — Points to the last (newest) element in the queue.
– Used during Enqueue (insertion) operation.
– When rear == MAX-1, the queue is full.
Example:
int queue[MAX], front = -1, rear = -1;
// Enqueue
if (rear == MAX - 1) printf("Full\n");
else { if (front == -1) front = 0; queue[++rear] = val; }
// Dequeue
if(front==-1||front>rear)printf("Empty\n"); else
printf("%d", queue[front++]);
3. Representation of Input-Restricted DEQUE
AnInput-RestrictedDeque(DEQUE)allowsinsertiononlyatoneend(rear)butdeletionfrombothends(front and rear).
Diagrammatic representation:
Delete (front) DEQUE Delete / Insert (rear)
[ 10 | 20 | 30 | 40 ] Insert / Delete
Structure:
#define MAX 10
intdeque[MAX];
int front = -1, rear = -1;
// Insert only at rear
if (rear == MAX - 1) printf("Deque Full\n");
else { if (front == -1) front = 0; deque[++rear] = val; }
// Delete from front
if(front==-1)printf("DequeEmpty\n"); else
printf("%d", deque[front++]);
// Delete from rear
if(rear<front)printf("DequeEmpty\n"); else
printf("%d", deque[rear--]);
4. List out the various operations of Queue
Operation Description
Enqueue (Insert) Add element at the rear end.
Dequeue (Delete) Remove element from the front end.
Peek / Front Return front element without removal.
isEmpty Check if queue has no elements.
isFull Check if queue has reached max capacity.
Display Print all elements from front to rear.
5. List out various operations in DEQUE (Double Ended Queue)
Operation Description
insertFront() Insert element at the front end.
insertRear() Insert element at the rear end.
deleteFront() Delete element from the front end.
deleteRear() Delete element from the rear end.
getFront() Get the front element without deletion.
getRear() Get the rear element without deletion.
isEmpty() Check if deque is empty.
isFull() Check if deque is full.
6. List out various types of Queues
Queue Type Description
Linear Queue Basic FIFO queue; insertion at rear, deletion at front.
Circular Queue Rear wraps around to front; avoids wasted space.
Double Ended Queue Insertion/deletion at both ends.
Priority Queue Elements served based on priority, not order.
Input Restricted DEQ Insertion only at rear; deletion from both ends.
Output Restricted DEQ Deletion only at front; insertion at both ends.
7. What is condition to check Full in DEQUE (Double Ended Queue)?
For an array-based deque of size MAX:
Deque Full:
For a Deque of size MAX:
(front == 0 && rear == MAX-1) ||
(front == rear + 1)
}
C Example:
if((front==0 && rear==MAX-1) ||
(front==rear+1))
{
printf("Deque Full");
}
8. List out the applications of Queues
• CPU Scheduling (Round Robin, FCFS)
• Disk Scheduling algorithms
• Print Spooler — print jobs queued in order
• BFS (Breadth First Search) in graphs/trees
• Keyboard input buffer
• Handling of interrupts in Operating Systems
• Call center / Customer service systems
• Data transfer between processes (pipe/buffer)
9. List out the applications of DEQUE (Double Ended Queue)
• Undo/Redo operations in text editors (add/remove from both ends)
• Browser history — navigate forward and backward
• Palindrome checking using deque
• Sliding window maximum problem (algorithm design)
• Implementing both stack and queue with a single deque
• Task scheduling with steal-work algorithms (threads steal from rear)
• A-Steal job scheduling algorithm
Long Answer Questions (7 Marks each)
10. Explain the process of Dequeuing in Circular Queue [7M]
A Circular Queue treats the array as circular so that rear can wrap around to the beginning, eliminating
wastedspace of a linear queue.
Conditions:
• Empty: front == -1
• Full: (rear + 1) % MAX == front
Dequeue Algorithm (Step-by-step):
• Step 1: Check if queue is empty (front == -1). If yes, print 'Queue Empty'.
• Step 2: Store the value at queue[front] in a temp variable.
• Step 3: If front == rear (only one element), reset front = rear = -1.
• Step 4: Otherwise, update front = (front + 1) % MAX (circular wrap).
• Step 5: Return the stored temp value.
C Implementation:
#define MAX 5
int queue[MAX], front = -1, rear = -1;
int dequeue() {
if (front == -1) {
printf("CircularQueueisEmpty\n");
return -1;
}
intval=queue[front]; if
(front == rear)
front = rear = -1; // last element removed
else
front = (front + 1) % MAX; //circularincrement
return val;
}
Trace Example (MAX=5):
State front rear Queue Action
Initial 0 3 [10,20,30,40,_] —
dequeue()=10 1 3 [,20,30,40,_] front moves to 1
dequeue()=20 2 3 [,,30,40,_] front moves to 2
dequeue()=30 3 3 [,,,40,_] front moves to 3
dequeue()=40 -1 -1 [_,_,_,_,_] front=rear=-1 (empty)
Note: The modulo operator (%) makes the queue circular, reusing positions freed by dequeue.
11. Explain the process of Inserting and Deleting in DEQUE [7M]
A Double Ended Queue (Deque) supports insertion and deletion at both front and rear ends.
Conditions (Linear Deque, size MAX):
• Full: rear == MAX - 1
• Empty: front == -1 or front >rear
Operations:
① Insert at Rear
void insertRear(int deque[], int *rear, int val) {
if(*rear==MAX-1){printf("DequeFull\n");return;}
deque[++(*rear)] = val;
printf("Inserted %d at Rear\n", val);
}
② Insert at Front
voidinsertFront(intdeque[],int*front,intval){ if
(*front == 0 || *front == -1) {
printf("Cannot Insert at Front\n"); return;
}
deque[--(*front)] = val;
printf("Inserted%datFront\n",val);
}
③ Delete from Front
voiddeleteFront(intdeque[],int*front,int*rear){ if
(*front == -1 || *front > *rear) {
printf("Deque Empty\n"); return;
}
printf("Deleted %d from Front\n", deque[(*front)++]);
}
④ Delete from Rear
voiddeleteRear(intdeque[],int*front,int*rear){ if
(*rear < *front) {
printf("Deque Empty\n"); return;
}
printf("Deleted %d from Rear\n", deque[(*rear)--]);
}
Trace Example:
Operation front rear Deque State
insertRear(10) 0 0 [10]
insertRear(20) 0 1 [10, 20]
insertRear(30) 0 2 [10, 20, 30]
deleteFront() 1 2 [20, 30]removed 10
deleteRear() 1 1 [20]removed 30
12. Explain the process of Inserting and Deleting in Linear Queue using Linked List [7M]
In a linked list-based queue, each node holds data and a pointer to the next node. front points to the first node
(dequeue end), rear points to the last node (enqueue end).
Node Structure:
struct Node {
int data;
struct Node *next;
};
struct Node *front = NULL, *rear = NULL;
① Enqueue (Insert at Rear):
• Step 1: Create a new node; assign data; set next = NULL.
• Step 2: If queue is empty (rear == NULL), set front = rear = newNode.
• Step 3: Otherwise, rear->next = newNode; rear = newNode.
void enqueue(int val) {
structNode*newNode=
(struct Node*) malloc(sizeof(struct Node));
if(newNode==NULL){printf("MemoryFull\n");return;}
newNode->data = val;
newNode->next = NULL;
if(rear==NULL){front=rear=newNode;return;} rear->next
= newNode;
rear = newNode;
printf("Enqueued:%d\n",val);
}
② Dequeue (Delete from Front):
• Step 1: Check if front == NULL (queue empty); print message.
• Step 2: Store front node in a temp pointer.
• Step 3: Move front = front->next.
• Step 4: If front becomes NULL, set rear = NULL as well.
• Step 5: Free the temp node; return stored value.
int dequeue() {
if(front==NULL){printf("QueueEmpty\n");return-1;} struct Node
*temp = front;
intval=temp->data; front
= front->next;
if (front == NULL) rear = NULL; //queuenowempty
free(temp);
printf("Dequeued:%d\n",val);
return val;
}
Linked Queue Diagram:
front rear
[10|•] [20|•] [30|•] [40|NULL]
13. Write briefly about Queues and all its Operations with Neat Diagram [7M]
Definition:AQueueisalineardatastructurethatfollowsFIFO(FirstInFirstOut)principle—theelementinserted first is
removed first. Insertion happens at the rear and deletion at the front.
Queue Diagram:
FRONT Queue Elements REAR
Delete [ 10 | 20 | 30 | 40 | 50 ] Insert
Operations in Detail:
① Enqueue — Insert at Rear
void enqueue(int queue[], int *rear, int val) {
if(*rear==MAX-1){printf("QueueFull\n");return;}
queue[++(*rear)] = val;
printf("Enqueued: %d\n", val);
}
② Dequeue — Delete from Front
intdequeue(intqueue[],int*front,int*rear){ if
(*front == -1 || *front > *rear) {
printf("Queue Empty\n"); return -1;
}
return queue[(*front)++];
}
③ Peek — View Front Element
intpeek(intqueue[],intfront,intrear){ if
(front == -1 || front > rear) {
printf("Queue Empty\n"); return -1;
}
return queue[front];
}
④ isEmpty and isFull checks
int isEmpty(int front, int rear) {
return (front == -1 || front >rear);
}
int isFull(int rear) {
return (rear == MAX - 1);
}
⑤ Display — Print all elements
voiddisplay(intqueue[],intfront,intrear){ if
(front == -1 || front > rear) {
printf("Queue is Empty\n"); return;
}
printf("Queue: ");
for(inti=front;i<=rear;i++) printf("%d
", queue[i]);
printf("\n");
}
Operation Trace (MAX=5):
Operation front rear Queue State Output
Initial -1 -1 [_____] —
enqueue(10) 0 0 [10 _ _ _ _] Enqueued: 10
enqueue(20) 0 1 [10 20 _ _ _] Enqueued: 20
enqueue(30) 0 2 [10 20 30 _ _] Enqueued: 30
dequeue() 1 2 [_ 20 30 _ _] Dequeued: 10
peek() 1 2 [_ 20 30 _ _] Front: 20
Note:[Link]=[Link]>rearthequeueislogicallyemptyevenif array has
elements (wasted space — solved by Circular Queue).