Queue – Class 12 Computer Science notes, important questions and MCQs

Chapter overview

A queue is a linear data structure in which elements are inserted at one end, called the rear, and removed from the other end, called the front. It follows the First In First Out (FIFO) principle, like people standing in a line. The main operations are ENQUEUE and DEQUEUE. Queues are implemented in Python using lists, and a deque (double-ended queue) allows insertion and deletion at both ends.

Queue and its operations

• In a queue, the element inserted first is removed first (FIFO).
• ENQUEUE adds an element at the rear; DEQUEUE removes an element from the front; PEEK returns the front element without removing it; isEmpty checks whether the queue is empty; overflow and underflow occur as in stacks.
• In Python, a list is used: queue.append(x) for ENQUEUE and queue.pop(0) for DEQUEUE; queue[0] gives the front element.

Applications and deque

• Applications include printer job queues, CPU scheduling, ticket booking, call centre waiting lines and handling requests on a web server.
• A deque (double-ended queue) allows insertion and deletion at both front and rear; it can work as both a stack and a queue.
• Deque operations in a Python list: insertFront with insert(0, x), insertRear with append(x), deletionFront with pop(0), deletionRear with pop(); a deque can be used to check palindromes by comparing elements removed from both ends.

Key terms

Queue

a linear data structure following FIFO

FIFO

First In First Out

ENQUEUE

inserting an element at the rear of a queue

DEQUEUE

removing an element from the front of a queue

Deque

a double-ended queue allowing operations at both ends

Important questions with answers

Quick revision

• FIFO principle.
• ENQUEUE, DEQUEUE, PEEK, isEmpty.
• Implementation using lists.
• Applications; deque and its operations.

Exam tips

• Queue in a Python list: append() to enqueue, pop(0) to dequeue.
• Compare stack (LIFO, one end) with queue (FIFO, two ends).

Practice MCQs

1. A queue follows the principle

   1. LIFO
   2. random order
   3. FIFO
   4. priority only
   Show answer

   Answer: (c) FIFO. First In First Out.

2. Adding an element to a queue is called

   1. PUSH
   2. ENQUEUE
   3. DEQUEUE
   4. POP
   Show answer

   Answer: (b) ENQUEUE. It happens at the rear.

3. Elements are removed from a queue at the

   1. rear
   2. middle
   3. front
   4. top
   Show answer

   Answer: (c) front. The oldest element leaves first.

4. For a Python list used as a queue, DEQUEUE is done by

   1. pop()
   2. append()
   3. pop(0)
   4. insert(0, x)
   Show answer

   Answer: (c) pop(0). The front is index 0.

5. A data structure allowing insertion and deletion at both ends is a

   1. deque
   2. stack
   3. simple queue
   4. tuple
   Show answer

   Answer: (a) deque. Double-ended queue.

6. Which situation is best modelled by a queue

   1. undo in an editor
   2. printing documents in the order they were sent
   3. evaluating postfix
   4. browser back button
   Show answer

   Answer: (b) printing documents in the order they were sent. Jobs are served in order.

7. If 10, 20, 30 are enqueued in order and one DEQUEUE is done, the front element becomes

   1. 10
   2. none
   3. 30
   4. 20
   Show answer

   Answer: (d) 20. 10 is removed first.

8. Why can a deque be used to check whether a string is a palindrome

   1. it sorts characters
   2. characters can be removed from both ends and compared
   3. it stores only vowels
   4. it reverses words automatically
   Show answer

   Answer: (b) characters can be removed from both ends and compared. Matching front and rear characters confirms a palindrome.