PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Queue Operations: Enqueue, Dequeue and Empty/Full Conditions (कतार ऑपरेशन्स: एनकतार (रियर) और डिकतार (फ्रंट)) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Queue operations center on Enqueue (inserting at rear after checking Overflow), Dequeue (removing from front after checking Underflow), and Peek (reading front non-destructively), all running in O(1) time. Handling boundary states—especially initializing front on the first insert and resetting both pointers when the single remaining element leaves—prevents invalid array reads.
अध्याय सार: कतार ऑपरेशन्स में मुख्य रूप से Enqueue (Overflow जांचकर rear पर जोड़ना), Dequeue (Underflow जांचकर front से हटाना) और Peek (बिना हटाए front पढ़ना) शामिल हैं, जो सभी O(1) समय में चलते हैं। पहले तत्व पर front को 0 करना और आखिरी तत्व हटने पर दोनों पॉइंटर्स को -1 पर रीसेट करना अनिवार्य सीमांत नियम हैं।
Queue Operations: Enqueue, Dequeue and Empty/Full Conditions: Detailed Notes & Architecture (कतार ऑपरेशन्स: एनकतार (रियर) और डिकतार (फ्रंट))
1. Enqueue Operation and First-Element Boundary (एनकतार (Enqueue) प्रक्रिया और प्रथम तत्व शर्त)
[EN] The enqueue(x) routine begins with an Overflow guard: if rear == MAX - 1, no index remains rightward, so it aborts and reports Queue Overflow. Otherwise, if front == -1 (meaning the queue was empty), front must also be updated to 0 before or alongside setting rear = 0. Finally, rear increments by 1 and stores arr[rear] = x.
[HI] enqueue(x) ऑपरेशन की शुरुआत Overflow जांच से होती है: यदि rear == MAX - 1 हो, तो कतार भर चुकी है और Queue Overflow त्रुटि आती है। यदि कतार खाली थी (front == -1), तो पहले तत्व के साथ front को 0 करना जरूरी होता है। इसके बाद rear को 1 बढ़ाकर arr[rear] = x लिखा जाता है।
2. Dequeue Operation and Single-Element Reset (डिकतार (Dequeue) प्रक्रिया और अंतिम तत्व रीसेट)
[EN] The dequeue() routine first checks Underflow: if front == -1 or front > rear, no element exists to remove and Queue Underflow is signaled. Next, val = arr[front] saves the front element before adjusting pointers. Crucially, if front == rear (meaning only one item remained), both front and rear reset to -1 so the queue cleanly returns to its initial empty state; otherwise, front increments by 1.
[HI] dequeue() सबसे पहले Underflow जांचता है: यदि front == -1 या front > rear हो, तो कतार खाली है और Queue Underflow होता है। मान arr[front] को सुरक्षित रखने के बाद जांचा जाता है कि क्या front == rear (केवल एक तत्व बचा था); यदि हाँ, तो कतार को पूर्णतः खाली करने हेतु front = -1 और rear = -1 रीसेट करते हैं, अन्यथा front को 1 बढ़ा देते हैं।
3. Empty, Full, Overflow, and Underflow Conditions (खाली (Empty), पूर्ण (Full), ओवरफ्लो और अंडरफ्लो शर्तें)
[EN] isEmpty() returns true when front == -1 (or front > rear in the front=0 variant), while isFull() evaluates rear == MAX - 1. Overflow is a runtime failure triggered exclusively by attempting enqueue() while isFull() holds true. Conversely, Underflow occurs when dequeue() or peek() is invoked while isEmpty() holds true.
[HI] isEmpty() की जांच front == -1 (या front > rear) से और isFull() की जांच rear == MAX - 1 से होती है। जब कतार पहले से भरी हो और enqueue() चलाया जाए तो Overflow होता है। इसके विपरीत, खाली कतार में dequeue() या peek() चलाने पर Underflow स्थिति उत्पन्न होती है।
4. Peek / Front Inspection and Active Size Formula (पीक (Peek) ऑपरेशन और सक्रिय आकार सूत्र)
[EN] The peek() (also called front() or getFront()) helper reads arr[front] after confirming !isEmpty(), without modifying front or rear—making it strictly non-destructive in O(1) time. Similarly, getRear() inspects arr[rear] without altering pointers. When non-empty, active item count equals (rear - front + 1); when empty (front == -1), size is 0.
[HI] peek() या front() फंक्शन कतार से कोई डेटा हटाए बिना केवल arr[front] का मान O(1) समय में पढ़ता है। इसी प्रकार getRear() अंतिम तत्व arr[rear] को दिखाता है। गैर-खाली कतार में वर्तमान तत्वों की गिनती (rear - front + 1) सूत्र से और खाली कतार में 0 प्राप्त होती है।
Syntax, Formula & Technical Example (Queue Operations: Enqueue, Dequeue and Empty/Full Conditions)
void enqueue(int x) {
if (rear == MAX - 1) { printf("Overflow\n"); return; }
if (front == -1) front = 0;
arr[++rear] = x;
}
int dequeue() {
if (front == -1 || front > rear) return -1; // Underflow
int val = arr[front];
if (front == rear) front = rear = -1;
else front++;
return val;
}
Queue Operations: Enqueue, Dequeue and Empty/Full Conditions Quick Reference & Comparison Table
| Queue Operation | Pointer Rule & Guard | Key Exam Fact |
|---|---|---|
| enqueue(x) | Check rear == MAX - 1; set front=0 if -1; arr[++rear]=x | Raises Overflow when array end reached |
| dequeue() | Check front == -1; return arr[front]; reset if front==rear | Raises Underflow when queue is empty |
| peek() / front() | Reads arr[front] if !isEmpty() without moving pointers | Non-destructive O(1) inspection |
| size() | Returns 0 if front == -1 else (rear - front + 1) | Tracks active element count accurately |
Queue Operations: Enqueue, Dequeue and Empty/Full Conditions Top 20 Bilingual MCQs with Answers
Q1. Which condition triggers Queue Underflow in a linear array queue?
(लीनियर एरे कतार में Queue Underflow की स्थिति कब उत्पन्न होती है?)
(A) Attempting dequeue() or peek() when the queue is empty
(B) Attempting enqueue() when rear == MAX - 1
(C) Setting front = 0 during first insertion
(D) Deleting when front == 0 and rear == 4
Correct Answer: (A)
[EN] Underflow occurs whenever an extraction or front inspection is attempted on an empty queue.
[HI] खाली कतार से तत्व निकालने (dequeue) या peek करने का प्रयास करने पर Underflow होता है।
Q2. During dequeue() on a queue containing only ONE element (front == rear), what should happen after reading arr[front]?
(जब कतार में केवल एक ही तत्व बचा हो (front == rear), तो dequeue() करते समय मान पढ़ने के बाद क्या करना चाहिए?)
(A) Increment rear by 1
(B) Reset both front and rear to -1
(C) Leave front == rear unchanged
(D) Decrement rear to -2
Correct Answer: (B)
[EN] Resetting front = -1 and rear = -1 cleanly returns the queue to its initial empty state and reclaims all indices.
[HI] अंतिम तत्व हटने पर front और rear दोनों को -1 पर रीसेट किया जाता है ताकि कतार फिर से खाली अवस्था में आ जाए।
Q3. Which operation inspects the front element without removing it or modifying pointers?
(कौन सा ऑपरेशन बिना किसी पॉइंटर को बदले या तत्व हटाए कतार के सबसे आगे वाले मान को पढ़ता है?)
(A) dequeue()
(B) peek() / getFront()
(C) popRear()
(D) enqueue()
Correct Answer: (B)
[EN] peek() returns arr[front] non-destructively in O(1) time while keeping front and rear intact.
[HI] peek() बिना डेटा हटाए arr[front] का मान दिखाता है और पॉइंटर्स को अपरिवर्तित रखता है।
Q4. If a linear queue has MAX = 6, front = 1, and rear = 4, how many active elements are currently inside?
(यदि MAX = 6 वाली लीनियर कतार में front = 1 और rear = 4 हो, तो कतार में अभी कितने तत्व मौजूद हैं?)
(A) 5
(B) 3
(C) 4
(D) 6
Correct Answer: (C)
[EN] Using count = rear - front + 1 gives 4 - 1 + 1 = 4 elements at indices 1, 2, 3, and 4.
[HI] सूत्र rear - front + 1 से 4 - 1 + 1 = 4 तत्व (इंडेक्स 1, 2, 3, 4 पर) मौजूद हैं।
Q5. In an array queue of MAX = 4 (initially empty: front=-1, rear=-1), trace: enqueue(5), enqueue(9), dequeue(), enqueue(12), dequeue(). What is front?
(MAX = 4 की खाली कतार (front=-1, rear=-1) पर enqueue(5), enqueue(9), dequeue(), enqueue(12), dequeue() चलाने के बाद front का मान क्या होगा?)
(A) 2
(B) 3
(C) 1
(D) 0
Correct Answer: (A)
[EN] enqueue(5)->f=0,r=0; enqueue(9)->f=0,r=1; dequeue()->f=1,r=1; enqueue(12)->f=1,r=2; dequeue()->f=2,r=2.
[HI] दो बार enqueue से rear=1, फिर dequeue से front=1, फिर enqueue से rear=2, और अंत में दूसरे dequeue से front=2 हो जाएगा।
Q6. What happens if you omit `if (front == -1) front = 0;` inside enqueue() on an array queue initialized with front = -1, rear = -1?
(front=-1, rear=-1 से शुरू होने वाली कतार के enqueue() में `if (front == -1) front = 0;` न लिखने पर क्या गड़बड़ी होगी?)
(A) Overflow fires on index 0
(B) Compiler rejects array syntax
(C) front remains -1, causing isEmpty() to still report true and dequeue() to read invalid arr[-1]
(D) rear becomes negative
Correct Answer: (C)
[EN] If front stays at -1 while rear advances, the queue appears empty forever and arr[front] accesses out-of-bounds memory.
[HI] front के -1 बने रहने से कतार हमेशा खाली दिखेगी और arr[-1] पढ़ते समय अमान्य मेमोरी एक्सेस होगा।
Q7. Given MAX = 5, front = 2, and rear = 4, what happens when enqueue(99) is called in a linear queue?
(MAX = 5 की लीनियर कतार में यदि front = 2 और rear = 4 है, तो enqueue(99) कॉल करने पर क्या होगा?)
(A) front shifts back to 0 automatically
(B) 99 is placed at arr[0]
(C) 99 overwrites arr[2]
(D) Queue Overflow occurs because rear == MAX - 1
Correct Answer: (D)
[EN] Linear queue full condition tests solely whether rear == MAX - 1 (4 == 4), triggering Overflow even though indices 0 and 1 are vacant.
[HI] लीनियर कतार में rear == MAX - 1 (4 == 4) होते ही Overflow रिपोर्ट हो जाता है, भले ही इंडेक्स 0 व 1 खाली हों।
Q8. Which two operations are the primary mutating primitives of a Queue ADT?
(कतार (Queue ADT) के दो मुख्य परिवर्तनकारी मूल ऑपरेशन्स कौन से हैं?)
(A) Enqueue and Dequeue
(B) Push and Pop
(C) Heapify and SiftDown
(D) Split and Merge
Correct Answer: (A)
[EN] Enqueue adds at rear and Dequeue removes from front; Push/Pop belong to Stack.
[HI] कतार के मुख्य ऑपरेशन्स Enqueue (जोड़ना) और Dequeue (हटाना) हैं, जबकि Push/Pop स्टैक के हैं।
Q9. In the front = 0, rear = -1 convention (no -1 reset), after inserting 1 item and deleting 1 item, what are (front, rear)?
(front = 0, rear = -1 नियम वाली कतार में 1 तत्व जोड़ने और 1 तत्व हटाने के बाद (front, rear) क्या होंगे?)
(A) front = 0, rear = -1
(B) front = 0, rear = 0
(C) front = -1, rear = -1
(D) front = 1, rear = 0
Correct Answer: (D)
[EN] Insert puts item at [0] (front=0, rear=0). Deleting increments front to 1, leaving front=1 > rear=0 (empty).
[HI] प्रविष्टि पर front=0, rear=0 होता है और हटाने पर front=1 हो जाता है, जिससे front > rear (खाली) सत्य हो जाता है।
Q10. What value does peek() return if executed sequentially twice on queue [7, 14, 21] (7 at front)?
(कतार [7, 14, 21] (7 front पर) पर लगातार दो बार peek() चलाने पर कौन से मान मिलेंगे?)
(A) 7 and 14
(B) 7 and 7
(C) 21 and 21
(D) 14 and 21
Correct Answer: (B)
[EN] Because peek() does not advance front, repeated calls inspect the same front element 7.
[HI] peek() पॉइंटर आगे नहीं बढ़ाता, इसलिए लगातार दोनों बार सबसे आगे वाला मान 7 ही प्राप्त होगा।
Q11. What is the worst-case time complexity of executing k consecutive enqueue and m consecutive dequeue operations on a static array queue?
(स्टैटिक एरे कतार पर लगातार k बार enqueue और m बार dequeue चलाने की कुल समय जटिलता क्या होगी?)
(A) O(log(k + m))
(B) O(k^2)
(C) O(k + m)
(D) O(k * m)
Correct Answer: (C)
[EN] Each enqueue and dequeue runs in O(1), so k + m total operations take linear O(k + m) time.
[HI] प्रत्येक enqueue और dequeue O(1) लेता है, अतः कुल k + m ऑपरेशन्स O(k + m) समय में पूरे होंगे।
Q12. Which condition evaluates whether a linear array queue of size MAX currently has zero free slots to its right?
(MAX आकार की लीनियर कतार में दाईं ओर कोई भी खाली स्लॉट न बचने की जांच किस शर्त से होती है?)
(A) front == rear
(B) front == 0
(C) rear == 0
(D) rear == MAX - 1
Correct Answer: (D)
[EN] Once rear reaches the last array index MAX - 1, no further rightward insertion is possible.
[HI] जब rear अंतिम एरे इंडेक्स MAX - 1 पर पहुँच जाता है, तब दाईं ओर कोई स्लॉट शेष नहीं रहता।
Q13. If a queue holds 1 element at index 3 (front = 3, rear = 3) and dequeue() runs without resetting pointers to -1, what would isEmpty() fail on?
(यदि front = 3, rear = 3 पर dequeue() बिना रीसेट किए केवल front++ कर दे, तो कौन सी जांच असफल हो सकती है?)
(A) Checking sizeof(arr)
(B) Checking rear == MAX - 1
(C) Checking front >= 0
(D) Checking only `front == -1` would miss `front > rear` (4 > 3) and return false!
Correct Answer: (D)
[EN] If dequeue increments front to 4 without resetting to -1, an implementation checking only front == -1 falsely believes the queue is non-empty.
[HI] यदि front=4 हो जाए और उसे -1 पर रीसेट न करें, तो केवल front == -1 जांचने वाला कोड कतार को खाली नहीं समझेगा।
Q14. If elements A, B, C, D are enqueued into an empty queue, followed by 2 dequeues, then E is enqueued, what is the front item?
(खाली कतार में A, B, C, D एनकतार करने के बाद 2 डिकतार किए जाएँ और फिर E एनकतार हो, तो front पर कौन सा तत्व होगा?)
(A) A
(B) C
(C) B
(D) E
Correct Answer: (B)
[EN] 2 dequeues remove A and B; E goes to the rear behind D, leaving C at the front.
[HI] दो बार डिकतार करने पर A और B हट जाएंगे; E पीछे जुड़ेगा, इसलिए सबसे आगे (front) C रहेगा।
Q15. Which auxiliary helper directly verifies whether dequeue() can safely extract a value?
(dequeue() से पहले कौन सा सहायक फंक्शन सुरक्षित जांच करता है कि डेटा निकाला जा सकता है या नहीं?)
(A) isFull()
(B) isSorted()
(C) !isEmpty()
(D) isBalanced()
Correct Answer: (C)
[EN] Dequeue is legal only when the queue is non-empty (!isEmpty()); isFull() guards enqueue() instead.
[HI] !isEmpty() यह सुनिश्चित करता है कि कतार में कम से कम एक तत्व मौजूद है, जबकि isFull() enqueue की जांच करता है।
Q16. Which statement is NOT true regarding standard Queue operations?
(कतार ऑपरेशन्स के संबंध में निम्नलिखित में से कौन सा कथन असत्य (NOT true) है?)
(A) Dequeue deletes the element pointed to by rear
(B) Peek returns the front item without incrementing front
(C) Enqueue increments rear when space is available
(D) Overflow occurs on inserting into a full queue
Correct Answer: (A)
[EN] Dequeue always removes from the front pointer, never from the rear pointer.
[HI] Dequeue हमेशा front पॉइंटर से तत्व हटाता है, न कि rear पॉइंटर से।
Q17. Within Queue Operations: Enqueue, Dequeue and Empty/Full Conditions, which queue operation directly maps to: "Check rear == MAX - 1; set front=0 if -1; arr[++rear]=x"?
(Queue Operations: Enqueue, Dequeue and Empty/Full Conditions में कौन सा Queue Operation सीधे "Check rear == MAX - 1; set front=0 if -1; arr[++rear]=x" से संबंधित है?)
(A) dequeue()
(B) enqueue(x)
(C) peek() / front()
(D) size()
Correct Answer: (B)
[EN] In Queue Operations: Enqueue, Dequeue and Empty/Full Conditions, 'enqueue(x)' handles 'Check rear == MAX - 1; set front=0 if -1; arr[++rear]=x' (Raises Overflow when array end reached).
[HI] Queue Operations: Enqueue, Dequeue and Empty/Full Conditions में 'enqueue(x)' का कार्य/विवरण 'Check rear == MAX - 1; set front=0 if -1; arr[++rear]=x' (Raises Overflow when array end reached) है।
Q18. Which option accurately describes 'dequeue()' in Queue Operations: Enqueue, Dequeue and Empty/Full Conditions?
(Queue Operations: Enqueue, Dequeue and Empty/Full Conditions के संदर्भ में 'dequeue()' की सही विशेषता कौन सी है?)
(A) Returns 0 if front == -1 else (rear - front + 1)
(B) Check rear == MAX - 1; set front=0 if -1; arr[++rear]=x
(C) Reads arr[front] if !isEmpty() without moving pointers
(D) Check front == -1; return arr[front]; reset if front==rear
Correct Answer: (D)
[EN] 'dequeue()' provides 'Check front == -1; return arr[front]; reset if front==rear' — key point: Raises Underflow when queue is empty.
[HI] 'dequeue()' का मुख्य विवरण 'Check front == -1; return arr[front]; reset if front==rear' है (Raises Underflow when queue is empty)।
Q19. In Queue Operations: Enqueue, Dequeue and Empty/Full Conditions, identify the correct parameter for the specification: "Reads arr[front] if !isEmpty() without moving pointers".
(Queue Operations: Enqueue, Dequeue and Empty/Full Conditions में "Reads arr[front] if !isEmpty() without moving pointers" विवरण किस विकल्प के लिए सही है?)
(A) dequeue()
(B) peek() / front()
(C) size()
(D) enqueue(x)
Correct Answer: (B)
[EN] 'peek() / front()' corresponds to 'Reads arr[front] if !isEmpty() without moving pointers' (Non-destructive O(1) inspection).
[HI] 'peek() / front()' का संबंध 'Reads arr[front] if !isEmpty() without moving pointers' (Non-destructive O(1) inspection) से है।
Q20. Considering Queue Operations: Enqueue, Dequeue and Empty/Full Conditions, what key behavior defines 'size()'?
(Queue Operations: Enqueue, Dequeue and Empty/Full Conditions में 'size()' की मुख्य भूमिका या मान क्या है?)
(A) Reads arr[front] if !isEmpty() without moving pointers
(B) Returns 0 if front == -1 else (rear - front + 1)
(C) Check rear == MAX - 1; set front=0 if -1; arr[++rear]=x
(D) Check front == -1; return arr[front]; reset if front==rear
Correct Answer: (B)
[EN] 'size()' represents 'Returns 0 if front == -1 else (rear - front + 1)' (Tracks active element count accurately).
[HI] 'size()' का अर्थ/मान 'Returns 0 if front == -1 else (rear - front + 1)' है (Tracks active element count accurately)।
Queue Operations: Enqueue, Dequeue and Empty/Full Conditions — Exam FAQs
Q1: Why is resetting front = -1 and rear = -1 on deleting the last item so beneficial?
अंतिम तत्व हटाते समय front = -1 और rear = -1 रीसेट करने का सबसे बड़ा लाभ क्या है?
[EN] It immediately reclaims the entire array from index 0 again once the queue becomes empty, postponing false overflow until the queue fills without ever draining.
[HI] कतार के पूरी तरह खाली होते ही पूरा एरे (इंडेक्स 0 से MAX-1 तक) पुनः उपयोग के लिए तैयार हो जाता है और फॉल्स ओवरफ्लो टल जाता है।
Q2: How do dequeue() and peek() differ in their effect on queue state?
dequeue() और peek() कतार की अवस्था पर अलग-अलग कैसे असर डालते हैं?
[EN] dequeue() returns the front element AND removes it by advancing front (reducing size by 1), whereas peek() returns the exact same front element WITHOUT modifying front, rear, or size.
[HI] dequeue() front तत्व को लौटाकर उसे कतार से हटाता है (आकार 1 कम होता है), जबकि peek() बिना कुछ बदले केवल मान पढ़कर देता है।
Q3: Why does enqueue() check Overflow before incrementing rear?
enqueue() हमेशा rear बढ़ाने से पहले Overflow की जांच क्यों करता है?
[EN] Incrementing rear past MAX - 1 would write to arr[MAX], causing an out-of-bounds array corruption or segmentation fault.
[HI] यदि पहले rear बढ़ा दिया जाए तो arr[MAX] पर अमान्य मेमोरी राइट (out-of-bounds त्रुटि) हो जाएगी।
Post a Comment
Post a Comment