Theory
આ શું કામ મહત્વનું છે
તમે જ્યારે Ctrl+Z દબાવીને undo કરો, browser નું Back button click કરો, અથવા એક function બીજા function ને call કરે, ત્યારે અંદર ને અંદર stack જ કામ કરી રહ્યું હોય છે. આ સૌથી સાદી data structures પૈકીની એક છે, અને સાથે સાથે સૌથી વધારે વપરાતી પણ. એક વાર આ બરાબર સમજી લેશો તો પછીના ઘણા topics (recursion, expression evaluation, parsing) એકદમ સહેલા લાગવા માંડશે.
Theory
થાળીઓની થપ્પી વિચારો
તમે નવી ચોખ્ખી થાળી થપ્પીની top પર મૂકો છો, અને જ્યારે જોઈએ ત્યારે પણ top પરથી જ ઉપાડો છો. વચ્ચેથી થાળી ક્યારેય નથી ખેંચતા, ખરું ને? એટલે જે થાળી છેલ્લે મૂકી એ જ સૌથી પહેલા બહાર આવે. આ એક જ નિયમ એટલે આખો ખેલ: LIFO, Last In, First Out.
Theory
મૂળ વાત
Stack એ એક linear list જ છે, પણ એક શરત સાથે: બધું જ કામ એક જ છેડે થાય, જેને આપણે top કહીએ છીએ.
- એક pointer (સામાન્ય રીતે
topનામનું) યાદ રાખે છે કે stack ની top ક્યાં છે. - તમે insert કે delete ફક્ત top પર જ કરી શકો, વચ્ચે કે bottom પર ક્યારેય નહીં.
- આ કારણે જ જે element છેલ્લે add થાય એ સૌથી પહેલા remove થાય (LIFO).
Theory
Operations શું શું છે
- Push, નવો item top પર મૂકવો.
topએક વધી જાય. - Pop, top નો item કાઢીને return કરવો.
topએક ઘટી જાય. - Peek / Peep / Display, top નો item કાઢ્યા વગર ફક્ત જોવો.
- isEmpty, stack ખાલી છે કે નહીં? (
topકશા તરફ point જ ન કરતું હોય) - isFull, fixed-size array stack માં, હવે જગ્યા બાકી નથી ને?
Practical
Visualize it
This step has an interactive visualizer in Gri-Learn on the web.
Think first
મનમાં trace કરી જુઓ
ખાલી stack થી શરૂ કરો. તમે push 5, push 9, pop, પછી push 2 કરો છો. 5 સેકન્ડ લો: pop માં શું નીકળ્યું, અને અત્યારે top પર શું છે?
Show the answer
Pop માં 9 નીકળ્યું, કારણ કે એ સૌથી છેલ્લે push થયેલો item હતો (LIFO). પછી 2 push કર્યા બાદ stack bottom થી top સુધી 5, 2 છે, એટલે top પર 2 છે. જો તમે કહ્યું કે pop માં 5 નીકળ્યું, તો એ queue નું behaviour છે (FIFO), stack નું નહીં.
Watch out
Exam માટે 2 errors ખાસ યાદ રાખો
Overflow ત્યારે થાય જ્યારે તમે પહેલેથી full stack પર push કરવા જાવ (array-based stack ની size fixed હોય છે). Underflow ત્યારે થાય જ્યારે તમે ખાલી stack માંથી pop (કે peek) કરવા જાવ. સારો code push પહેલા isFull() અને pop પહેલા isEmpty() હંમેશા check કરે છે.
Watch
Data structures: Introduction to Stack
Watch on YouTube · mycodeschool
Theory
એને implement કેવી રીતે કરાય
સૌથી સાદી implementation માં એક array વાપરીએ છીએ, સાથે એક integer top index જે -1 થી શરૂ થાય છે (એટલે ખાલી).
- push(x): full ન હોય તો
top = top + 1કરો, પછીarr[top] = x. - pop(): empty ન હોય તો
arr[top]વાંચો, પછીtop = top - 1કરો. - peek():
arr[top]return કરો (topને બદલવાનું નહીં).
નીચે એક ચાલતું version છે, એને બદલો, run કરો, અને output જુઓ.
Practical
એક નાનું array-based stack, run કરો અને થોડું બદલી જુઓ
// A simple fixed-size stack. Press Run, then try changing the values.
class Stack {
constructor(capacity) {
this.items = [];
this.capacity = capacity;
}
isFull() { return this.items.length === this.capacity; }
isEmpty() { return this.items.length === 0; }
push(x) {
if (this.isFull()) { console.log("Overflow! cannot push", x); return; }
this.items.push(x);
console.log("push", x, "-> top is now", this.peek());
}
pop() {
if (this.isEmpty()) { console.log("Underflow! stack is empty"); return; }
const x = this.items.pop();
console.log("pop ->", x);
return x;
}
peek() { return this.items[this.items.length - 1]; }
}
const s = new Stack(3);
s.push(10);
s.push(20);
s.push(30);
s.push(40); // full -> overflow
s.pop();
s.pop();
console.log("top after two pops:", s.peek());
This example runs in Gri-Learn on the web, where you can edit it and see the output.
Quiz
capacity 3 વાળું stack ખાલી છે. તમે આ ચલાવો: push A, push B, push C, push D, pop. હવે peek() શું return કરશે?
- B
- C
- D
- A
Show the answer
B
push D આવે ત્યારે stack પહેલેથી જ full છે, એટલે એ reject થાય (Overflow) અને કશું બદલાતું નથી. પછી pop થાય એટલે top વાળો C નીકળી જાય. બાકી રહે A, B, એટલે peek() B return કરે. જો તમે C લખ્યું હોય તો તમે overflow ચૂકી ગયા; D તો અંદર આવ્યું જ નહોતું.
Formula
Stack ક્યાં ક્યાં વપરાય છે
Function calls ("call stack"), undo/redo, browser history (Back), balanced parentheses ()[]{} check કરવા, અને expressions convert/evaluate કરવા (infix → postfix / prefix). આ exam ના classic applications છે, ઓછામાં ઓછા 3 તો યાદ રાખજો.
Summary
Key takeaways
- Stack એ LIFO list છે, બધું કામ top પર જ થાય.
- Push top પર add કરે; Pop top પરથી remove કરે; Peek/Peep top ને કાઢ્યા વગર વાંચે.
- Overflow = full stack પર push; Underflow = empty stack પર pop.
- Array implementation:
topindex -1 થી શરૂ, push પર વધે અને pop પર ઘટે. - વપરાય છે: call stack, undo/redo, browser back, balanced parentheses, infix→postfix/prefix.