Stack Data Structure: LIFO Principle and Array Implementation Notes in Hindi & English : स्टैक (Stack): LIFO सिद्धांत, टॉप पॉइंटर और एरे कार्यान्वयन और 20 महत्वपूर्ण MCQ प्रश्न (Rajasthan IT Exam)

Post a Comment

PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Stack Data Structure: LIFO Principle and Array Implementation (स्टैक (Stack): LIFO सिद्धांत, टॉप पॉइंटर और एरे कार्यान्वयन) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।

Overview: A Stack is a linear Abstract Data Type operating strictly on the LIFO (Last-In, First-Out) principle, allowing insertions and deletions only at a single end called top. Implemented with a fixed-size array, it tracks the active top index (initially -1 for 0-based indexing) and provides O(1) access with strong cache locality.

अध्याय सार: स्टैक (Stack) एक रैखिक डेटा संरचना है जो LIFO (Last-In, First-Out) सिद्धांत पर कार्य करती है, जहाँ डेटा जोड़ना व हटाना केवल top नामक एक ही सिरे से होता है। एरे कार्यान्वयन में top वैरिएबल शीर्ष तत्व का इंडेक्स रखता है (प्रारंभ में -1) और उच्च कैश लोकैलिटी के साथ O(1) गति देता है।

Stack Data Structure: LIFO Principle and Array Implementation: Detailed Notes & Architecture (स्टैक (Stack): LIFO सिद्धांत, टॉप पॉइंटर और एरे कार्यान्वयन)

1. LIFO / FILO Principle & Restricted Single-End Access (LIFO / FILO सिद्धांत और एक-सिरे का प्रतिबंधित प्रवेश)

[EN] A Stack restricts all element insertions (Push) and removals (Pop) to one active end known as the top, enforcing LIFO (Last-In, First-Out)—equivalently FILO (First-In, Last-Out). Random access or insertion in the middle violates the Stack ADT contract. Consequently, the element placed most recently is always the very first one retrieved, making Stacks naturally reverse arrival order.

[HI] स्टैक में सभी इंसर्शन (Push) और डिलीशन (Pop) केवल top नामक एक ही सिरे पर होते हैं, जिसे LIFO (जो अंत में आया वह पहले बाहर जाएगा) या FILO सिद्धांत कहते हैं। एरे की तरह स्टैक के बीच से सीधे किसी तत्व को निकालना या बदलना ADT नियमों के विरुद्ध है। इसी गुण के कारण स्टैक में जाने वाला डेटा स्वतः उल्टे क्रम में बाहर आता है।

2. Static Array Implementation & Top Index Conventions (स्टेटिक एरे कार्यान्वयन और Top इंडेक्स नियम)

[EN] Using a fixed array stack[MAX] with 0-based indexing (indices 0 through MAX - 1), an integer variable top begins at -1 to indicate an empty state. Pushing an item increments top first (stack[++top] = x) so top always equals the index of the latest item, and the stack becomes full when top == MAX - 1. Note that the current number of stored elements is always (top + 1), while alternative 1-based textbooks initialize top = 0.

[HI] 0-आधारित इंडेक्सिंग वाले एरे stack[MAX] में खाली स्टैक को दर्शाने के लिए प्रारंभ में top = -1 रखा जाता है। तत्व डालते समय पहले top बढ़ाकर (stack[++top] = x) मान रखा जाता है, जिससे किसी भी समय स्टैक में कुल (top + 1) तत्व रहते हैं और top == MAX - 1 होने पर स्टैक पूरा भर जाता है।

3. Performance, Cache Locality & Fixed-Capacity Limitation (प्रदर्शन, कैश लोकैलिटी और निश्चित आकार की सीमा)

[EN] Array-backed stacks store elements contiguously in memory, offering superior CPU cache locality, zero per-element pointer overhead, and strict O(1) time per Push or Pop. Their primary drawback is static capacity MAX fixed at declaration: underestimating MAX causes premature Stack Overflow, whereas overestimating wastes unused RAM. Dynamic array wrappers (like C++ std::vector) overcome fixed size via capacity doubling in O(1) amortized time.

[HI] एरे आधारित स्टैक में तत्व मेमोरी में लगातार रहते हैं, जिससे CPU कैश लोकैलिटी शानदार होती है और प्रति तत्व पॉइंटर मेमोरी खर्च नहीं होती। इसकी मुख्य कमी निश्चित क्षमता MAX है: कम रखने पर जल्दी Overflow होता है और बहुत बड़ा रखने पर मेमोरी व्यर्थ जाती है।

4. Core Computing Applications of Stack (कंप्यूटिंग में स्टैक के प्रमुख व्यावहारिक उपयोग)

[EN] Operating systems and compilers rely on the hardware Call Stack to store activation records (return addresses, parameters, and local variables) during function calls and recursion. Stacks also drive Depth-First Search (DFS) on graphs, backtracking algorithms, syntax delimiter matching, infix-to-postfix conversion, string reversal, and Undo history in editors. Note that Recursion inherently uses the system call stack, whereas iterative conversion uses an explicit programmer-managed stack.

[HI] कंपाइलर और ऑपरेटिंग सिस्टम फंक्शन कॉल व रिकर्शन को सँभालने के लिए कॉल स्टैक (Activation Records: रिटर्न पता, लोकल वैरिएबल) का उपयोग करते हैं। इसके अलावा ग्राफ में DFS ट्रैवर्सल, बैकट्रैकिंग, स्ट्रिंग पलटने, व्यंजक मूल्यांकन और एडिटर के Undo फीचर में स्टैक अनिवार्य भूमिका निभाता है।

Syntax, Formula & Technical Example (Stack Data Structure: LIFO Principle and Array Implementation)

#define MAX 5
int stack[MAX], top = -1;
/* Empty: top == -1 | Full: top == MAX - 1 | Count: top + 1 */
void push(int x) {
    if (top < MAX - 1) stack[++top] = x;
}
int pop(void) {
    return (top >= 0) ? stack[top--] : -1;
}

Stack Data Structure: LIFO Principle and Array Implementation Quick Reference & Comparison Table

Stack Aspect / RuleArray Implementation DetailExam Key Point
LIFO / FILO OrderAll insertions & deletions happen strictly at topReverses insertion order upon full pop
Empty Stack Statetop == -1 in 0-indexed array stack[0..MAX-1]Contains 0 items; count formula top + 1 = 0
Full Stack Statetop == MAX - 1 in 0-indexed arrayHolds MAX items; further push triggers Overflow
Array Memory LayoutContiguous O(MAX) fixed buffer; 0 pointer overheadHigh cache locality; static size unless resized

Stack Data Structure: LIFO Principle and Array Implementation Top 20 Bilingual MCQs with Answers

Q1. Which ordering principle governs the Stack data structure?

(स्टैक डेटा संरचना किस क्रम सिद्धांत का पालन करती है?)

(A) LILO (Last-In, Last-Out)

(B) Priority-Sorted Random Access

(C) LIFO (Last-In, First-Out)

(D) FIFO (First-In, First-Out)

Correct Answer: (C)

[EN] The element pushed most recently into a stack is always the first one popped out, defining LIFO (or FILO).

[HI] स्टैक में सबसे अंत में डाला गया तत्व सबसे पहले बाहर निकलता है, जिसे LIFO (Last-In, First-Out) सिद्धांत कहते हैं।

Q2. In a 0-indexed array implementation stack[MAX], what initial value is assigned to 'top' to indicate an empty stack?

(0-आधारित एरे कार्यान्वयन stack[MAX] में खाली स्टैक को दर्शाने के लिए 'top' का प्रारंभिक मान क्या रखा जाता है?)

(A) -1

(B) MAX - 1

(C) 0

(D) MAX

Correct Answer: (A)

[EN] Indices start at 0, so top = -1 unambiguously represents zero elements; the first push increments top to 0.

[HI] एरे का पहला इंडेक्स 0 होता है, इसलिए 0 तत्व होने पर top = -1 रखा जाता है ताकि पहले पुश पर top बढ़कर 0 हो सके।

Q3. If a 0-indexed array stack of capacity MAX = 10 currently has top == 6, how many elements are inside the stack?

(यदि MAX = 10 क्षमता वाले 0-इंडेक्स एरे स्टैक में अभी top == 6 है, तो स्टैक में कुल कितने तत्व मौजूद हैं?)

(A) 6 elements

(B) 7 elements

(C) 10 elements

(D) 4 elements

Correct Answer: (B)

[EN] Elements occupy indices 0, 1, 2, 3, 4, 5, and 6, giving top + 1 = 7 elements.

[HI] तत्व इंडेक्स 0 से 6 तक भरे हैं, इसलिए कुल संख्या top + 1 = 7 होगी।

Q4. What condition indicates that a static 0-indexed array stack of size MAX is completely full?

(MAX आकार वाले 0-इंडेक्स्ड स्टेटिक एरे स्टैक के पूरी तरह भरे होने की शर्त क्या है?)

(A) top == MAX - 1

(B) top == 0

(C) top == MAX

(D) top == -1

Correct Answer: (A)

[EN] Valid array indices span 0 to MAX - 1, so once top reaches MAX - 1 no free slot remains.

[HI] एरे के वैध इंडेक्स 0 से MAX - 1 तक होते हैं, इसलिए top == MAX - 1 होते ही स्टैक भर जाता है।

Q5. If numbers 1, 2, 3, 4 are pushed onto a stack in that order (interleaved with arbitrary pops), which pop output sequence is IMPOSSIBLE?

(यदि 1, 2, 3, 4 को इसी क्रम में स्टैक में पुश किया जाए (बीच में पॉप संभव है), तो कौन सा आउटपुट क्रम असंभव (IMPOSSIBLE) है?)

(A) 4, 3, 1, 2

(B) 4, 3, 2, 1

(C) 1, 2, 3, 4

(D) 2, 4, 3, 1

Correct Answer: (A)

[EN] To pop 4 first, 1, 2, and 3 must already sit in the stack (3 on top of 2 on top of 1), so 1 CANNOT be popped before 2!

[HI] 4 को सबसे पहले पॉप करने के लिए 1, 2, 3 पहले ही स्टैक में नीचे से ऊपर होंगे; अतः 2 से पहले 1 बाहर नहीं निकल सकता!

Q6. Which data structure is used internally by compilers and CPUs to manage recursive function calls and return addresses?

(कंपाइलर और CPU द्वारा रिकर्सिव फंक्शन कॉल्स व उनके रिटर्न एड्रेस सँभालने के लिए किस डेटा संरचना का उपयोग होता है?)

(A) Binary Search Tree

(B) Call Stack (Stack of Activation Records)

(C) Circular Queue

(D) Adjacency Matrix

Correct Answer: (B)

[EN] Each function invocation pushes an activation frame onto the Call Stack and pops it when returning to the caller.

[HI] प्रत्येक फंक्शन कॉल पर उसका एक्टिवेशन रिकॉर्ड कॉल स्टैक में पुश होता है और फंक्शन समाप्त होने पर पॉप हो जाता है।

Q7. Which graph traversal algorithm explicitly uses a Stack (or recursion stack) rather than a Queue?

(निम्नलिखित में से कौन सा ग्राफ ट्रैवर्सल एल्गोरिथ्म Queue की बजाय Stack का उपयोग करता है?)

(A) Depth-First Search (DFS)

(B) Round-Robin Scheduling

(C) Level-Order Tree Traversal

(D) Breadth-First Search (BFS)

Correct Answer: (A)

[EN] DFS explores deeply along a branch using a Stack (LIFO), whereas BFS explores level by level using a Queue (FIFO).

[HI] DFS गहराई में जाने के लिए Stack (LIFO) का उपयोग करता है, जबकि BFS स्तर-दर-स्तर चलने के लिए Queue (FIFO) उपयोग करता है।

Q8. What is the time complexity to reverse a string of length n by pushing all characters onto a stack and popping them back?

(n अक्षरों की किसी स्ट्रिंग के सभी वर्ण स्टैक में पुश करके वापस पॉप करते हुए उसे पलटने (Reverse) की टाइम कॉम्प्लेक्सिटी क्या है?)

(A) O(n)

(B) O(log n)

(C) O(1)

(D) O(n^2)

Correct Answer: (A)

[EN] n pushes take O(n) and n pops take O(n), yielding O(2n) = O(n) total time.

[HI] सभी n अक्षरों को पुश करने में O(n) और पॉप करने में O(n) समय लगता है, अतः कुल कॉम्प्लेक्सिटी O(n) होती है।

Q9. Why is stack[++top] = x used instead of stack[top++] = x when top starts at -1?

(जब top = -1 से शुरू हो, तो stack[top++] = x की जगह stack[++top] = x क्यों लिखा जाता है?)

(A) Pre-increment automatically doubles the array size

(B) Post-increment is syntax error in C

(C) Pre-increment advances top from -1 to 0 before writing, avoiding invalid stack[-1] access

(D) Post-increment deletes the previous value in stack[0]

Correct Answer: (C)

[EN] Using top++ at -1 would write into out-of-bounds memory stack[-1] before changing top to 0.

[HI] top = -1 पर top++ लिखने से पहले stack[-1] की अवैध मेमोरी में डेटा लिखा जाएगा, जबकि ++top पहले इंडेक्स को 0 बनाता है।

Q10. In an array stack where top is initialized to 0 (representing the next free slot instead of the top occupied element), what is the full condition?

(यदि किसी एरे स्टैक में top = 0 से शुरुआत हो (जो अगले खाली स्लॉट को दर्शाता हो), तो स्टैक भरने की शर्त क्या होगी?)

(A) top == MAX

(B) top == -1

(C) top == MAX - 1

(D) top == 1

Correct Answer: (A)

[EN] When top points to the next empty slot starting at 0, after MAX insertions top reaches MAX (all 0..MAX-1 filled).

[HI] यदि top अगले खाली इंडेक्स को दिखाता है, तो 0 से MAX-1 तक सभी स्थान भरने के बाद top का मान MAX पर पहुँच जाएगा।

Q11. Which advantage does a static array implementation of a Stack hold over a linked list implementation?

(लिंक्ड लिस्ट कार्यान्वयन की तुलना में स्टैक के स्टेटिक एरे कार्यान्वयन का मुख्य लाभ क्या है?)

(A) No pointer memory overhead per element and superior CPU cache locality

(B) Unlimited dynamic growth without resizing

(C) Automatic garbage collection in C

(D) O(log n) search time for middle items

Correct Answer: (A)

[EN] Contiguous array elements avoid storing a 4/8-byte next pointer per item and stay cache-friendly.

[HI] एरे में प्रति तत्व अतिरिक्त पॉइंटर मेमोरी नहीं लगती और डेटा लगातार होने से CPU कैश लोकैलिटी बेहतर रहती है।

Q12. When implementing TWO stacks inside a single fixed array arr[0..N-1] for maximum space utilization, where should their tops start?

(एक ही एरे arr[0..N-1] में दो स्टैक को अधिकतम स्थान दक्षता से चलाने के लिए उनके top कहाँ से शुरू होने चाहिए?)

(A) Stack 1 starts at N/2 going left, Stack 2 at N/2 going right

(B) Both start at index 0 and move right

(C) Stack 1 grows right from -1, while Stack 2 grows left from N

(D) Both start at index N - 1

Correct Answer: (C)

[EN] Growing inward from opposite ends (top1 = -1, top2 = N) prevents overflow until total items reach N (top1 + 1 == top2).

[HI] दोनों सिरों (top1 = -1 आगे और top2 = N पीछे) से बढ़ने पर पूरा एरे भरने (top1 + 1 == top2) तक ओवरफ्लो नहीं होता।

Q13. What happens to an element's insertion order after passing through a single Stack (all pushed then all popped)?

(सभी तत्वों को एक स्टैक में पुश करके फिर पूरा पॉप करने पर उनके क्रम पर क्या प्रभाव पड़ता है?)

(A) Only the first and last items swap

(B) The sequence is completely reversed

(C) The sequence stays identical

(D) The sequence becomes sorted in ascending order

Correct Answer: (B)

[EN] Because LIFO pops the latest pushed item first, pushing a1..an outputs an..a1.

[HI] LIFO नियम के कारण अंत में डाला गया तत्व पहले बाहर आता है, जिससे पूरा क्रम पलट (Reverse) जाता है।

Q14. What is the total number of distinct valid stack-permutation outputs obtainable from 3 inputs (1, 2, 3) using a stack?

(3 तत्वों (1, 2, 3) को स्टैक से गुजारकर कुल कितने अलग-अलग वैध आउटपुट क्रम (Stack Permutations) प्राप्त हो सकते हैं?)

(A) 4

(B) 5 (the 3rd Catalan number)

(C) 3

(D) 6 (all 3! permutations)

Correct Answer: (B)

[EN] Valid stack permutations for n items equal the nth Catalan number C_n = (2n)! / ((n+1)! n!); for n=3, C_3 = 5 (only 3,1,2 is impossible).

[HI] n तत्वों के लिए वैध स्टैक क्रम कैटलन संख्या C_n होते हैं; n=3 के लिए 3!=6 में से '3,1,2' असंभव है, अतः कुल 5 क्रम संभव हैं।

Q15. Which statement best distinguishes a Stack ADT from a simple 1D Array?

(कौन सा कथन Stack ADT और सामान्य 1D एरे के मुख्य अंतर को सही ढंग से स्पष्ट करता है?)

(A) Arrays enforce LIFO automatically

(B) Stack cannot store integers whereas an array can

(C) Stack always requires pointers whereas arrays never use addresses

(D) Stack restricts access strictly to one end (top), while an array allows O(1) random access at any index

Correct Answer: (D)

[EN] A Stack is defined by its behavioral restriction (top-only Push/Pop/Peek), even when implemented atop an array.

[HI] एरे में किसी भी इंडेक्स से डेटा पढ़ा या बदला जा सकता है, जबकि स्टैक केवल top सिरे से ही प्रवेश व निकासी की अनुमति देता है।

Q16. Which of the following is NOT true about an array-based Stack?

(एरे-आधारित स्टैक (Array-based Stack) के बारे में निम्नलिखित में से कौन सा कथन असत्य (NOT true) है?)

(A) It can grow indefinitely at runtime without reallocation or overflow

(B) It stores elements in contiguous memory locations

(C) It requires checking top == MAX - 1 before pushing

(D) Push and Pop both execute in O(1) time

Correct Answer: (A)

[EN] A fixed-size array stack has static capacity MAX and triggers Stack Overflow if pushed past capacity without dynamic reallocation.

[HI] निश्चित आकार वाला एरे स्टैक रनटाइम पर अपने आप अनंत तक नहीं बढ़ सकता; क्षमता MAX पार करने पर ओवरफ्लो हो जाता है।

Q17. Within Stack Data Structure: LIFO Principle and Array Implementation, which stack aspect / rule directly maps to: "All insertions & deletions happen strictly at top"?

(Stack Data Structure: LIFO Principle and Array Implementation में कौन सा Stack Aspect / Rule सीधे "All insertions & deletions happen strictly at top" से संबंधित है?)

(A) Empty Stack State

(B) Array Memory Layout

(C) Full Stack State

(D) LIFO / FILO Order

Correct Answer: (D)

[EN] In Stack Data Structure: LIFO Principle and Array Implementation, 'LIFO / FILO Order' handles 'All insertions & deletions happen strictly at top' (Reverses insertion order upon full pop).

[HI] Stack Data Structure: LIFO Principle and Array Implementation में 'LIFO / FILO Order' का कार्य/विवरण 'All insertions & deletions happen strictly at top' (Reverses insertion order upon full pop) है।

Q18. Which option accurately describes 'Empty Stack State' in Stack Data Structure: LIFO Principle and Array Implementation?

(Stack Data Structure: LIFO Principle and Array Implementation के संदर्भ में 'Empty Stack State' की सही विशेषता कौन सी है?)

(A) top == MAX - 1 in 0-indexed array

(B) Contiguous O(MAX) fixed buffer; 0 pointer overhead

(C) top == -1 in 0-indexed array stack[0..MAX-1]

(D) All insertions & deletions happen strictly at top

Correct Answer: (C)

[EN] 'Empty Stack State' provides 'top == -1 in 0-indexed array stack[0..MAX-1]' — key point: Contains 0 items; count formula top + 1 = 0.

[HI] 'Empty Stack State' का मुख्य विवरण 'top == -1 in 0-indexed array stack[0..MAX-1]' है (Contains 0 items; count formula top + 1 = 0)।

Q19. In Stack Data Structure: LIFO Principle and Array Implementation, identify the correct parameter for the specification: "top == MAX - 1 in 0-indexed array".

(Stack Data Structure: LIFO Principle and Array Implementation में "top == MAX - 1 in 0-indexed array" विवरण किस विकल्प के लिए सही है?)

(A) Array Memory Layout

(B) Full Stack State

(C) LIFO / FILO Order

(D) Empty Stack State

Correct Answer: (B)

[EN] 'Full Stack State' corresponds to 'top == MAX - 1 in 0-indexed array' (Holds MAX items; further push triggers Overflow).

[HI] 'Full Stack State' का संबंध 'top == MAX - 1 in 0-indexed array' (Holds MAX items; further push triggers Overflow) से है।

Q20. Considering Stack Data Structure: LIFO Principle and Array Implementation, what key behavior defines 'Array Memory Layout'?

(Stack Data Structure: LIFO Principle and Array Implementation में 'Array Memory Layout' की मुख्य भूमिका या मान क्या है?)

(A) Contiguous O(MAX) fixed buffer; 0 pointer overhead

(B) All insertions & deletions happen strictly at top

(C) top == MAX - 1 in 0-indexed array

(D) top == -1 in 0-indexed array stack[0..MAX-1]

Correct Answer: (A)

[EN] 'Array Memory Layout' represents 'Contiguous O(MAX) fixed buffer; 0 pointer overhead' (High cache locality; static size unless resized).

[HI] 'Array Memory Layout' का अर्थ/मान 'Contiguous O(MAX) fixed buffer; 0 pointer overhead' है (High cache locality; static size unless resized)।

Stack Data Structure: LIFO Principle and Array Implementation — Exam FAQs

Q1: Why does Stack Overflow occur during infinite recursion?

अनंत रिकर्शन (Infinite Recursion) चलने पर Stack Overflow एरर क्यों आती है?

[EN] Every recursive call pushes a new activation frame onto the fixed-size system Call Stack without returning; without a base case, it exhausts the stack memory limit.

[HI] हर रिकर्सिव कॉल पर सिस्टम कॉल स्टैक में एक नया फ्रेम जुड़ता है; बेस केस न होने पर पॉप नहीं होता और कॉल स्टैक की निर्धारित मेमोरी भर जाती है।

Q2: Can a Queue be simulated using Stacks?

क्या स्टैक की सहायता से Queue (FIFO) का व्यवहार बनाया जा सकता है?

[EN] Yes, two Stacks (an input stack and an output stack) can implement a FIFO Queue with O(1) amortized enqueue and dequeue.

[HI] हाँ, दो स्टैक (एक इनपुट और एक आउटपुट स्टैक) की मदद से FIFO Queue को O(1) अमॉर्टाइज्ड कॉम्प्लेक्सिटी में कार्यान्वित किया जा सकता है।

Q3: What is the difference between LIFO and FILO?

LIFO और FILO सिद्धांतों में क्या अंतर है?

[EN] They describe the exact same behavior from opposite perspectives: the Last item In is the First item Out (LIFO), which equivalently means the First item In is the Last item Out (FILO).

[HI] दोनों बिल्कुल एक ही सिद्धांत को अलग नजरिए से बताते हैं: अंत में आने वाला पहले निकलेगा (LIFO), अर्थात पहले आने वाला सबसे अंत में निकलेगा (FILO)।

Related Posts

  • Loading related posts...

Post a Comment

Search Topic Notes & 20 MCQs (Hindi / English)