PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Queue Data Structure: FIFO Principle and Array Implementation (कतार (Queue): FIFO सिद्धांत, फ्रंट और रियर पॉइंटर्स) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: A Queue is a linear abstract data type governed by the First-In, First-Out (FIFO) discipline, where insertions occur strictly at the rear pointer and deletions occur strictly at the front pointer. In a static array of capacity MAX indexed from 0 to MAX - 1, both operations achieve O(1) time complexity without shifting elements.
अध्याय सार: कतार (Queue) एक रैखिक डेटा संरचना है जो FIFO (First-In, First-Out) सिद्धांत पर चलती है, जहाँ नया तत्व हमेशा rear पॉइंटर पर जुड़ता है और पुराना तत्व हमेशा front पॉइंटर से हटता है। 0 से MAX - 1 इंडेक्स वाले स्टैटिक एरे कार्यान्वयन में दोनों प्रमुख ऑपरेशन्स O(1) समय जटिलता में पूरे होते हैं।
Queue Data Structure: FIFO Principle and Array Implementation: Detailed Notes & Architecture (कतार (Queue): FIFO सिद्धांत, फ्रंट और रियर पॉइंटर्स)
1. FIFO Principle and Dual-Pointer Architecture (FIFO सिद्धांत और दो-पॉइंटर संरचना)
[EN] Unlike a Stack (LIFO) which restricts all access to a single top end, a Queue maintains two open logical ends: front (head) for removal and rear (tail) for insertion. The oldest element residing in the queue is always serviced first, also described equivalently as Last-In, Last-Out (LILO). Because elements preserve exact arrival chronology, queues guarantee fair sequential ordering across concurrent requests.
[HI] स्टैक (LIFO) के विपरीत, जिसमें सारा काम केवल एक सिरे (top) से होता है, कतार (Queue) में दो अलग सिरे होते हैं: हटाने के लिए front और जोड़ने के लिए rear। जो डेटा सबसे पहले कतार में आता है, वही सबसे पहले बाहर निकलता है—इसे LILO (Last-In, Last-Out) भी कहा जाता है। यह संरचना आगमन के सटीक क्रम को सुरक्षित रखती है।
2. Static Array Representation and Initialization Conventions (स्टैटिक एरे निरूपण और प्रारंभिक मान (Initialization))
[EN] An array-backed linear queue allocates a contiguous block arr[MAX] alongside two integer indices front and rear. The most common C/textbook convention initializes front = -1 and rear = -1 to signify an empty queue; inserting the very first item sets both front = 0 and rear = 0. An alternative convention sets front = 0 and rear = -1 initially, where front > rear indicates emptiness and rear == MAX - 1 indicates fullness.
[HI] एरे आधारित लीनियर कतार में MAX आकार का एक सन्निहित एरे arr[MAX] तथा दो पूर्णांक सूचकांक front व rear रखे जाते हैं। मानक C पाठ्यपुस्तकों में खाली कतार दर्शाने के लिए front = -1 और rear = -1 से शुरुआत होती है, तथा पहला तत्व डालते समय front = 0 कर दिया जाता है। एक अन्य प्रचलित नियम में front = 0 और rear = -1 रखा जाता है, जहाँ front > rear खाली स्थिति दर्शाता है।
3. Time Complexity, Space Footprint, and Stack Contrast (समय व स्थान जटिलता तथा स्टैक से तुलना)
[EN] Because array indices allow direct O(1) random memory addressing via base + i * sizeof(element), incrementing rear or front avoids scanning the array. Space complexity for a static queue is fixed at O(MAX), regardless of how many items are currently active. Searching for an arbitrary key inside a queue still requires O(n) linear traversal from front to rear.
[HI] एरे में सीधे इंडेक्स गणना से डेटा प्राप्त होने के कारण एनकतार व डिकतार दोनों O(1) स्थिर समय लेते हैं। स्टैटिक कतार में मेमोरी स्थान हमेशा O(MAX) के बराबर आरक्षित रहता है, चाहे उसमें कम तत्व हों। यदि कतार में किसी विशेष तत्व को खोजना हो, तो front से rear तक O(n) रैखिक जांच करनी पड़ती है।
4. Operating System, Networking, and Graph Applications (ऑपरेटिंग सिस्टम, नेटवर्किंग और एल्गोरिदम अनुप्रयोग)
[EN] Operating systems rely on queues for First-Come, First-Served (FCFS) CPU scheduling, printer spooling queues, and interrupt request buffering. Network routers buffer incoming packets in FIFO queues before transmission to absorb bursty traffic. Graph algorithms employ queues directly inside Breadth-First Search (BFS) to visit vertices level by level from a source node.
[HI] ऑपरेटिंग सिस्टम में FCFS CPU शेड्यूलिंग, प्रिंटर स्पूलिंग और कीबोर्ड I/O बफर के लिए कतार का उपयोग होता है। नेटवर्क राउटर आने वाले पैकेट्स को कतारबद्ध करके ट्रैफिक बस्ट संभालते हैं। ग्राफ एल्गोरिदम में Breadth-First Search (BFS) स्तर-दर-स्तर नोड्स को विज़िट करने के लिए कतार पर निर्भर रहता है।
Syntax, Formula & Technical Example (Queue Data Structure: FIFO Principle and Array Implementation)
#define MAX 5
struct LinearQueue {
int arr[MAX];
int front, rear;
};
void init(struct LinearQueue *q) {
q->front = -1;
q->rear = -1;
}
int isEmpty(struct LinearQueue *q) { return q->front == -1; }
Queue Data Structure: FIFO Principle and Array Implementation Quick Reference & Comparison Table
| Queue Concept | Standard Array Specification | Key Exam Fact |
|---|---|---|
| Ordering Discipline | FIFO (First-In, First-Out) / LILO | Opposite of Stack LIFO rule |
| Front Pointer Role | Tracks oldest element; advances on deletion | Initialized to -1 when empty |
| Rear Pointer Role | Tracks newest element; advances on insertion | Full check triggers at MAX - 1 |
| Access Complexity | O(1) insert/delete; O(n) arbitrary search | Static array allocates O(MAX) RAM |
Queue Data Structure: FIFO Principle and Array Implementation Top 20 Bilingual MCQs with Answers
Q1. Which ordering principle governs the Queue data structure?
(कतार (Queue) डेटा संरचना किस क्रम सिद्धांत का पालन करती है?)
(A) First-In, First-Out (FIFO)
(B) Highest-Key First
(C) Last-In, First-Out (LIFO)
(D) Random Priority Access
Correct Answer: (A)
[EN] The first item inserted at the rear is always the first item removed from the front (FIFO / LILO).
[HI] कतार में जो तत्व सबसे पहले पीछे से जुड़ता है, वही सबसे पहले आगे से हटाया जाता है (FIFO)।
Q2. In a linear queue, which end is strictly used for inserting new elements?
(लीनियर कतार में नए तत्व जोड़ने (Insertion) के लिए किस सिरे का उपयोग किया जाता है?)
(A) Front end
(B) Middle index
(C) Rear end
(D) Both ends simultaneously
Correct Answer: (C)
[EN] Standard queues permit insertions exclusively at the rear pointer and deletions at the front pointer.
[HI] सामान्य कतार में नए तत्व हमेशा rear सिरे पर जोड़े जाते हैं और front सिरे से हटाए जाते हैं।
Q3. Under the front = -1, rear = -1 initialization convention, what are their values after inserting the very first element into an array queue of size 5?
(front = -1, rear = -1 से शुरू होने वाली साइज 5 की एरे कतार में पहला तत्व डालने के बाद front और rear के मान क्या होंगे?)
(A) front = -1, rear = 0
(B) front = 0, rear = 1
(C) front = 1, rear = 1
(D) front = 0, rear = 0
Correct Answer: (D)
[EN] When inserting into an empty queue (front == -1), front advances from -1 to 0 alongside rear = 0.
[HI] खाली कतार (front == -1) में पहला तत्व जोड़ते समय front और rear दोनों 0 पर सेट हो जाते हैं।
Q4. What is the time complexity of inserting an element at the rear of an array-based queue (without shifting)?
(एरे-आधारित कतार के rear सिरे पर नया तत्व जोड़ने की समय जटिलता क्या होती है?)
(A) O(1)
(B) O(log n)
(C) O(n^2)
(D) O(n)
Correct Answer: (A)
[EN] Direct array indexing via arr[++rear] executes in constant O(1) time.
[HI] एरे इंडेक्सिंग द्वारा arr[++rear] सीधे एक स्थिर चरण में चलता है, अतः समय जटिलता O(1) है।
Q5. Which graph traversal algorithm fundamentally relies on a Queue?
(निम्नलिखित में से कौन सा ग्राफ ट्रैवर्सल एल्गोरिदम कतार (Queue) पर आधारित है?)
(A) Kruskal's MST
(B) Breadth-First Search (BFS)
(C) Quick Sort
(D) Depth-First Search (DFS)
Correct Answer: (B)
[EN] BFS explores neighbors level by level using a FIFO queue, whereas DFS uses a Stack or recursion.
[HI] BFS नोड्स को स्तर-दर-स्तर विज़िट करने के लिए Queue का उपयोग करता है, जबकि DFS स्टैक उपयोग करता है।
Q6. In an array queue indexed 0 to MAX - 1 using front = 0 and rear = -1 initially, which expression tests whether the queue is empty?
(यदि एरे कतार front = 0 और rear = -1 से प्रारंभ होती है, तो कतार खाली होने की सही जांच कौन सी है?)
(A) rear == MAX - 1
(B) front == rear
(C) front == 0 && rear == 0
(D) front > rear
Correct Answer: (D)
[EN] Before any insertion (0 > -1) or after the last item leaves (front exceeds rear), front > rear holds true.
[HI] प्रारंभ में या अंतिम तत्व हटने के बाद front का मान rear से बड़ा हो जाता है (front > rear)।
Q7. Suppose elements 10, 20, 30 are inserted sequentially into an initially empty array queue (front=-1, rear=-1), and one deletion occurs. What are (front, rear)?
(एक खाली एरे कतार (front=-1, rear=-1) में क्रमशः 10, 20, 30 डालने और फिर 1 तत्व हटाने पर (front, rear) के मान क्या होंगे?)
(A) front = 1, rear = 1
(B) front = 2, rear = 2
(C) front = 0, rear = 2
(D) front = 1, rear = 2
Correct Answer: (D)
[EN] Three insertions put 10 at [0], 20 at [1], 30 at [2] (front=0, rear=2). Deleting 10 increments front to 1.
[HI] तीन प्रविष्टियों से front=0 व rear=2 होता है; एक विलोपन के बाद front बढ़कर 1 हो जाता है और rear=2 रहता है।
Q8. Which OS scheduling policy directly models a standard FIFO Queue?
(निम्नलिखित में से कौन सी OS शेड्यूलिंग नीति सीधे मानक FIFO कतार का अनुसरण करती है?)
(A) First-Come, First-Served (FCFS)
(B) Multilevel Feedback
(C) Priority Preemptive
(D) Shortest Job Next (SJN)
Correct Answer: (A)
[EN] FCFS dispatches processes in the exact order they enter the ready queue.
[HI] FCFS शेड्यूलिंग प्रक्रियाओं को ठीक उसी क्रम में CPU देती है जिस क्रम में वे रेडी कतार में आती हैं।
Q9. What is the maximum valid array index for a 0-indexed static queue declared with capacity MAX?
(MAX क्षमता वाली 0-इंडेक्स्ड स्टैटिक कतार में अधिकतम वैध एरे इंडेक्स क्या होता है?)
(A) MAX - 1
(B) MAX / 2
(C) MAX
(D) MAX + 1
Correct Answer: (A)
[EN] Zero-based indexing runs from index 0 through MAX - 1, giving MAX total slots.
[HI] 0-आधारित इंडेक्सिंग 0 से MAX - 1 तक चलती है, जिसमें कुल MAX स्लॉट होते हैं।
Q10. Why is a static array queue's space complexity stated as O(MAX) even when only 2 elements are stored?
(केवल 2 तत्व होने पर भी स्टैटिक एरे कतार की स्थान जटिलता O(MAX) क्यों मानी जाती है?)
(A) Because array shrinks automatically
(B) The fixed array buffer is pre-allocated at compile/init time regardless of active count
(C) Because FIFO doubles pointer overhead
(D) Because rear duplicates every element
Correct Answer: (B)
[EN] Static arrays reserve all MAX slots upfront and cannot dynamically shrink unused slots.
[HI] स्टैटिक एरे शुरुआत में ही पूरा MAX आकार आरक्षित कर लेता है और खाली स्लॉट वापस नहीं करता।
Q11. What happens if a queue holds elements [A, B, C, D] (A at front, D at rear) and we remove two items?
(यदि कतार में [A, B, C, D] (A front पर, D rear पर) हैं और दो तत्व हटाए जाते हैं, तो क्या बचेगा?)
(A) [A, D] with A at front
(B) [A, B] with A at front
(C) [B, C] with B at front
(D) [C, D] with C at front
Correct Answer: (D)
[EN] Deletions always remove from the front under FIFO, so A then B depart, leaving C at front.
[HI] FIFO नियम से हमेशा आगे (front) से A व B हटेंगे, जिससे C नए front के रूप में बचेगा।
Q12. Which alternative name accurately describes FIFO behavior from the newest element's perspective?
(नवीनतम तत्व के दृष्टिकोण से FIFO व्यवहार को किस दूसरे नाम से जाना जाता है?)
(A) LILO (Last-In, Last-Out)
(B) FILO (First-In, Last-Out)
(C) LIFO (Last-In, First-Out)
(D) Random-In, First-Out
Correct Answer: (A)
[EN] The last element to enter the queue waits behind all earlier items and therefore exits last (LILO).
[HI] जो तत्व सबसे अंत में जुड़ता है, वह सबसे अंत में बाहर निकलता है—इसे LILO कहते हैं।
Q13. What is the time complexity to search whether a specific key exists inside an unsorted linear queue of n elements?
(n तत्वों वाली सामान्य लीनियर कतार में किसी विशेष मान को खोजने की सबसे खराब समय जटिलता क्या है?)
(A) O(log n)
(B) O(n log n)
(C) O(n)
(D) O(1)
Correct Answer: (C)
[EN] Queues expose only front and rear directly; finding an internal key requires scanning up to n items.
[HI] कतार में सीधे बीच का तत्व नहीं देखा जा सकता, अतः खोजने के लिए अधिकतम n तत्वों को पढ़ना पड़ता है।
Q14. Which application does NOT use a Queue as its primary mechanism?
(इनमें से कौन सा अनुप्रयोग मुख्य रूप से Queue का उपयोग नहीं करता?)
(A) Keyboard keystroke buffering
(B) Evaluating balanced parentheses / function call stack frames
(C) Breadth-First Search traversal
(D) Print job spooling in a shared office printer
Correct Answer: (B)
[EN] Parenthesis matching and function call frames follow LIFO order and require a Stack, not a Queue.
[HI] कोष्ठक मिलान (Parentheses matching) और फंक्शन कॉल फ्रेम LIFO होते हैं, जिनमें Stack लगता है।
Q15. When using a single-linked list instead of an array for a standard Queue, which pointers are needed for O(1) enqueue and dequeue?
(एरे के बजाय सिंगली लिंक्ड लिस्ट से कतार बनाने पर O(1) एनकतार व डिकतार हेतु किन पॉइंटर्स की आवश्यकता होती है?)
(A) Only a head pointer
(B) A middle pointer only
(C) Both head (front) and tail (rear) pointers
(D) Only a tail pointer
Correct Answer: (C)
[EN] Deleting from head (front) is O(1) with head, and appending at tail (rear) is O(1) only if a tail pointer is maintained.
[HI] head से O(1) में हटाने और tail पर O(1) में जोड़ने के लिए head (front) और tail (rear) दोनों पॉइंटर्स चाहिए।
Q16. Which statement is NOT true about a standard Linear Queue implemented with an array?
(एरे से बनी मानक लीनियर कतार के बारे में इनमें से कौन सा कथन असत्य (NOT true) है?)
(A) Full condition occurs when rear reaches MAX - 1
(B) Insertion and deletion both happen at the front pointer
(C) Deletion takes O(1) time by advancing front
(D) It follows FIFO ordering
Correct Answer: (B)
[EN] Insertion happens at the rear pointer while deletion happens at the front pointer—never both at front.
[HI] लीनियर कतार में जोड़ना (insertion) rear पर और हटाना (deletion) front पर होता है; दोनों एक ही सिरे पर नहीं होते।
Q17. Within Queue Data Structure: FIFO Principle and Array Implementation, which queue concept directly maps to: "FIFO (First-In, First-Out) / LILO"?
(Queue Data Structure: FIFO Principle and Array Implementation में कौन सा Queue Concept सीधे "FIFO (First-In, First-Out) / LILO" से संबंधित है?)
(A) Rear Pointer Role
(B) Access Complexity
(C) Front Pointer Role
(D) Ordering Discipline
Correct Answer: (D)
[EN] In Queue Data Structure: FIFO Principle and Array Implementation, 'Ordering Discipline' handles 'FIFO (First-In, First-Out) / LILO' (Opposite of Stack LIFO rule).
[HI] Queue Data Structure: FIFO Principle and Array Implementation में 'Ordering Discipline' का कार्य/विवरण 'FIFO (First-In, First-Out) / LILO' (Opposite of Stack LIFO rule) है।
Q18. Which option accurately describes 'Front Pointer Role' in Queue Data Structure: FIFO Principle and Array Implementation?
(Queue Data Structure: FIFO Principle and Array Implementation के संदर्भ में 'Front Pointer Role' की सही विशेषता कौन सी है?)
(A) O(1) insert/delete; O(n) arbitrary search
(B) FIFO (First-In, First-Out) / LILO
(C) Tracks newest element; advances on insertion
(D) Tracks oldest element; advances on deletion
Correct Answer: (D)
[EN] 'Front Pointer Role' provides 'Tracks oldest element; advances on deletion' — key point: Initialized to -1 when empty.
[HI] 'Front Pointer Role' का मुख्य विवरण 'Tracks oldest element; advances on deletion' है (Initialized to -1 when empty)।
Q19. In Queue Data Structure: FIFO Principle and Array Implementation, identify the correct parameter for the specification: "Tracks newest element; advances on insertion".
(Queue Data Structure: FIFO Principle and Array Implementation में "Tracks newest element; advances on insertion" विवरण किस विकल्प के लिए सही है?)
(A) Access Complexity
(B) Ordering Discipline
(C) Rear Pointer Role
(D) Front Pointer Role
Correct Answer: (C)
[EN] 'Rear Pointer Role' corresponds to 'Tracks newest element; advances on insertion' (Full check triggers at MAX - 1).
[HI] 'Rear Pointer Role' का संबंध 'Tracks newest element; advances on insertion' (Full check triggers at MAX - 1) से है।
Q20. Considering Queue Data Structure: FIFO Principle and Array Implementation, what key behavior defines 'Access Complexity'?
(Queue Data Structure: FIFO Principle and Array Implementation में 'Access Complexity' की मुख्य भूमिका या मान क्या है?)
(A) Tracks newest element; advances on insertion
(B) O(1) insert/delete; O(n) arbitrary search
(C) Tracks oldest element; advances on deletion
(D) FIFO (First-In, First-Out) / LILO
Correct Answer: (B)
[EN] 'Access Complexity' represents 'O(1) insert/delete; O(n) arbitrary search' (Static array allocates O(MAX) RAM).
[HI] 'Access Complexity' का अर्थ/मान 'O(1) insert/delete; O(n) arbitrary search' है (Static array allocates O(MAX) RAM)।
Queue Data Structure: FIFO Principle and Array Implementation — Exam FAQs
Q1: Why do textbooks show two different empty conditions (front == -1 vs front > rear) for linear queues?
किताबों में खाली कतार की दो अलग शर्तें (front == -1 बनाम front > rear) क्यों मिलती हैं?
[EN] It depends on initial values: if both front and rear start at -1, emptiness is checked via front == -1 (resetting both to -1 when the last item leaves). If front starts at 0 and rear at -1, front increases past rear on the final deletion, making front > rear true.
[HI] यह शुरुआती मान पर निर्भर है: यदि front व rear दोनों -1 से शुरू हों, तो खाली स्थिति front == -1 होती है। यदि front=0 और rear=-1 से शुरू हो, तो अंतिम तत्व हटने पर front > rear हो जाता है।
Q2: Can a Queue ever behave like a Stack without changing its underlying insertion/deletion rules?
क्या कोई एक सामान्य FIFO कतार अपने नियम बदले बिना स्टैक की तरह काम कर सकती है?
[EN] Not a single standard queue directly—you need either two queues (making push or pop O(n)) or one queue plus auxiliary reversal/rotation to simulate LIFO behavior.
[HI] सीधे एक सामान्य कतार से नहीं; LIFO व्यवहार पाने के लिए या तो दो कतारें चाहिए या तत्वों को O(n) समय में घुमाना (rotate) पड़ता है।
Q3: How many elements exist in an array queue when front = 2 and rear = 4?
यदि किसी एरे कतार में front = 2 और rear = 4 है, तो उसमें कुल कितने तत्व मौजूद हैं?
[EN] There are (rear - front + 1) = (4 - 2 + 1) = 3 elements, stored at indices 2, 3, and 4.
[HI] कतार में (rear - front + 1) = (4 - 2 + 1) = 3 तत्व इंडेक्स 2, 3 और 4 पर मौजूद हैं।
Post a Comment
Post a Comment