FSc Part 1 Computer Science Chapter 4 Complete Guide Book — Computational Structures

Computer میں data کو صرف رکھنا کافی نہیں ہوتا — اسے ایسے انداز میں رکھنا پڑتا ہے کہ ضرورت پڑھنے پر وہ فوراً مل بھی جائے اور اس میں تبدیلی بھی آسانی سے ہو سکے. Data کو ترتیب دینے کے اسی طریقے کو computational structure (ya data structure) کہتے ہیں. سوچو, کتابوں کو اگر almari میں بے-ترتیب phenk دیا جائے تو ایک کتاب ڈھونڈنا مشکل ہو جائے گا; لیکن اگر وہ subject کے حساب سے لگی ہوں تو کام آساں ہو جاتا ہے. بالکل اسی طرح program میں data کی ترتیب ہی اس کی رفتار اور آسانی طے کرتی ہے.

اس chapter میں ہم پانچ بنیادی structures پڑھیں گے: lists, stacks, queues, trees aur graphs. ان میں سے سب سے پہلا اور سب سے زیادہ استعمال ہونے والا structure list ہے. List ایک ایسی ترتیب ہے جس میں کئی چیزیں ایک خاص sequence میں رکھی جاتی ہیں. List کی ہر چیز کو element کہتے ہیں, اور ہر element کی ایک index (position) ہوتی ہے جس سے اسے سیدھا پکڑا جا سکتا ہے.

Python میں list بنانے کے لیے square brackets [ ] استعمال ہوتے ہیں اور items کو comma سے الگ کیا جاتا ہے. کتاب کی مثال دیکھو:

Yahan items list کا نام ہے. Text والی چیزیں quotes میں لکھی گئی ہیں اور ہر item comma سے جدا ہے. print(items) پوری list ایک ہی line میں دکھا دیتا ہے. یاد رکھو, Python میں counting 0 سے شروع ہوتی ہے — اس لیے "Decorations" index 0 پر ہے, "Snacks" index 1 پر, اور آخری item "Balloon" index 4 پر.

List کی تین خاص properties ہیں, اور انہی کی وجہ سے وہ اتنی مفید ہے. پہلی: Dynamic Size — Python کی list کا size fixed نہیں ہوتا. تم بعد میں نئے items add کر سکتے ہو یا پرانے hata سکتے ہو, اور list خود-ba-خود اپنے size کو adjust کر لیتی ہے. کسی نئی list بنانے کی ضرورت نہیں پڑتی; وہی list بڑھتی یا گھٹتی رہتی ہے.

Doosri: Index-Based Access — ہر item کی ایک fixed position ہوتی ہے. پہلا item index 0, دوسرا index 1, تیسرا index 2, اور اسی طرح آگے. اس کا مطلب ہے کہ تم پوری list کو chaanay کے بجائے سیدھا items[2] لکھ کر "Cold drinks" تک pahonch سکتے ہو. یہ سیدھی رسائی (direct access) list کی سب سے بڑی طاقت ہے.

Teesri: Ordered Collection — جس ترتیب سے تم items add کرتے ہو, وہی ترتیب محفوظ رہتی ہے. اگر "Buy drinks" پہلے لکھا گیا تو وہ پہلے ہی رہیگا, جب تک تم خود اسے move نہ کرو. اس لیے list ان کاموں کے لیے بہترین ہے جہاں ترتیب matter کرتی ہے — جیسے تو-دو list, shopping list یا students کی attendance.

1. Insertion — insert() se kisi bhi jagah item dalna. کتاب کی party-list مثال کو step by step دیکھو:

insert(0, ...) کا پہلا number بتاتا ہے kahan ڈالنا ہے اور دوسرا kya ڈالنا ہے. Index 0 کا مطلب سب سے شروع, اس لیے "Invite friends" سب سے پہلے آ گیا اور باقی سب items ایک-ایک position آگے کھسک گئے. ⚠️ کتاب میں note کرو: printed page 57 پر اس code کا output غلط چھپا ہے — اس میں "Invite friends" نظر نہیں آتا اور پرانی list ہی دکھائی گئی ہے. صحیح output وہی ہے جو اوپر دیا گیا ہے, کیوں کے insert() کا کام ہی item کو شامل کرنا ہے.

2. Deletion — do tareeqay. (a) Value se — remove(): party_list.remove("Buy snacks") پہلی دفعہ ملنے والا "Buy snacks" hata دیتا ہے, چاہے وہ کسی بھی index پر ہو. (b) Index se — pop(): party_list.pop(0) index 0 والا item hata دیتا ہے. کتاب کی مثال میں list ["Invite friends", "Buy decorations", "Buy cold drinks"] thi; pop(0) ne "Invite friends" hataya to baaqi reh gaya ['Buy decorations', 'Buy cold drinks'].

3. Searching — ان keyword سے check کرنا. if "Buy cold drinks" in party_list: صرف یہ پوچھتا ہے کہ item list میں ہے یا نہیں — True یا False. کتاب کے code میں یہ item موجود تھا, اس لیے output آیا: "Buy cold drinks is on the list." یہ search پوری list میں item ڈھونڈتا ہے, index یاد رکھنے کی ضرورت نہیں.

List صرف کتابی چیز نہیں — روزمرہ کے programs میں ہر جگہ نظر آتی ہے. پہلا بڑا استعمال Data Storage and Manipulation ہے: records, entries اور values کا ایک مجموعہ رکھنا. Students کے نام, test کے marks, دکان کے items — یہ سب lists میں رکہے جاتے ہیں کیوں کے ان میں insertion, deletion اور access تینوں آساں ہیں.

دوسرا استعمال تھوڑا گہرا ہے لیکن بہت اہم: lists سے ہی stacks اور queues بنائے جاتے ہیں. آگے اس chapter میں تم دیکھو گے کے stack کا push/pop Python میں list کے append() aur pop() سے ہی ہوتا ہے. مطلب list ایک بنیادی اینٹ (building block) ہے — اسے سمجھ لیا تو آگے کے structures سمجھنا آدھا آساں ہو جاتا ہے. اسی لیے کتاب lists کو "primitive computational structures" میں سب سے پہلے رکھتی ہے.

Stack کو سمجھنے کا سب سے آساں طریقہ کتابوں کا ڈھیر ہے — کتاب کی Figure 4.1 بھی یہی دکھاتی ہے. تم نئی کتاب ہمیشہ oopar رکھتے ہو, اور جب کوئی کتاب چاہیے ہوتی ہے تو سب سے اوپر والی ہی اٹھاتے ہو; نیچے والی کتاب تک pahonchnay کے لیے اوپر والی hatani پڑتی ہے. Stack میں insertion اور deletion دونوں صرف ایک ہی end پر ہوتے ہیں, جسے top کہتے ہیں.

Is usool ka naam LIFO — Last-In, First-Out ہے. مطلب جو item سب سے آخر میں آیا, وہ سب سے پہلے باہر جائے گا. کتابوں کی مثال میں: اگر تم نے پہلے Book A رکھی پھر Book B, تو Book B اوپر ہوگی اور پہلے وہی اٹھے گی. یہ اصول computer میں ہر جگہ ہے — browser کا Back button, undo (Ctrl+Z), اور function calls کا حساب, سب stack پر چلتے ہیں.

Stack ke sirf do bunyadi operations ہیں. Push: item کو stack کے top پر add کرنا. Pop: top سے item کو remove کرنا. Python میں stack بنانے کے لیے الگ کوئی چیز نہیں چاہیے — ایک خالی list ہی stack بن جاتی ہے, append() push کا کام کرتا ہے اور pop() pop ka.

کتاب کے code کو line by line trace کرو:

Dekho, pop() نے کوئی index نہیں manga — اس نے خود top والی چیز, یعنی آخری item 'Book B', نکال لی. کتاب کا جملہ یہی کہتا ہے: "the last book added is the first one taken off" — یہی LIFO کی زندہ مثال ہے. اگر دوبارہ pop کیا جائے تو اب 'Book A' نکلے گی, کیوں کے اب وہی top پر ہے.

Queue کا مطلب ہے line — بالکل ویسی line جیسی bank یا ticket counter کے سامنے لگتی ہے (کتاب کی Figure 4.2). جو شخص سب سے پہلے line میں لگا, اسے سب سے پہلے serve کیا جاتا ہے. Computer کی queue بھی یہی کرتی ہے: پہلے آیا ہوا item پہلے باہر جاتا ہے.

Is usool ka naam FIFO — First-In, First-Out ہے. Stack سے فرق سمجھ لو: stack میں دونوں کام ایک ہی end (top) پر ہوتے تھے; queue میں do alag ends ہوتے ہیں — نئے items back (rear) سے آتے ہیں اور پرانے items front سے نکلتے ہیں. بیچ میں گھسنا یا بیچ سے نکالنا allowed نہیں. Printer کی line, ticket booking اور کسی بھی "پہلے آؤ, پہلے pao" والی situation میں queue ہی استعمال ہوتی ہے.

Queue کے دو بنیادی operations ہیں. Enqueue: item کو line کے آخر (back) میں لگانا. Dequeue: front سے item کو serve کر کے نکالنا. ان کے علاوہ تین مددگار کام بھی ہوتے ہیں: queue خالی ہے یا نہیں check کرنا, front والا item baghair nikale dekhna (peek), اور queue کا size معلوم کرنا.

کتاب کا Python code (printed p. 60) line by line trace کرو:

دیکھو, peek نے صرف بتایا کے front پر Ahmed ہے, اسے ہٹایا نہیں; ہٹایا تب جب get() چلا. اور سارا آخر میں لگی, فاطمہ کے پیچھے — اس لیے updated queue [Fatima, Sara] bani. ⚠️ Naam ka note: عام زبان میں ان operations کو enqueue/dequeue کہتے ہیں, لیکن Python کے queue module میں وہی کام put() aur get() سے ہوتا ہے — exercise کے سوال اسی لیے دونوں نام استعمال کرتے ہیں.

List اور queue میں چیزیں ایک سیدھی line میں ہوتی ہیں — پیچھے ایک, آگے ایک. Tree اس سے بالکل مختلف ہے. Tree میں data ایک main point (root node) سے شروع ہوتا ہے اور پھر branches کی طرح پھیلتا ہے. ہر piece of information کو node کہتے ہیں, اور ایک node کئی دوسرے nodes سے جڑ سکتا ہے.

کتاب کی Figure 4.3 (family tree) اسے سب سے اچھی طرح سمجھاتی ہے: سب سے اوپر dada-دادی (ancestors) root کی طرح ہیں, ان کے نیچے father-mother اور uncle-aunt, اور ان کے نیچے بچے — brother, sister, "Me" اور cousins. یہ parent-child رشتہ list میں ٹھیک سے نہیں دیکھایا جا سکتا, کیوں کے list میں ہر item کا صرف ایک پیچھے اور ایک آگے ہوتا ہے; tree میں ایک parent کے کئی children ہو سکتے ہیں. اسی لیے hierarchical data — family tree, company کا organisation chart, computer کے folders — tree میں رکھا جاتا ہے.

1. Root Node: tree کا سب سے پہلا یا سب سے اوپر والا node. جیسے computer میں میں folder جس میں باقی تمام folders اور files ہوتی ہیں, ویسے ہی root سے پورا tree شروع ہوتا ہے. Root کا کوئی parent نہیں ہوتا.

2. Edges aur Nodes: nodes tree کے individual elements ہیں, اور ان کو جوڑنے والی lines کو edges کہتے ہیں. جس node کے کوئی child nodes نہ ہوں, اسے leaf کہتے ہیں — بالکل اس file کی طرح جو folder میں ہے لیکن اس کے اندر کوئی اور file نہیں. Family tree میں سب سے نیچے والے بچے leaves ہیں.

3. Height: root سے سب سے دور والے leaf تک کا سب سے لمبا راستہ. یہ بتاتا ہے کہ tree کتنا گہرا یا اونچا ہے. ⚠️ Counting note: کتاب height کو "longest path" کہتی ہے, اور exercise کا MCQ 5 اسی بنیاد پر edges کی تعداد کو صحیح جواب مانتا ہے (root سے deepest node تک edges). کچھ کتابیں nodes گن کر height بتاتی ہیں — وہ ایک زیادہ ہوگی — اس لیے exam میں کتاب کی definition (edges) استعمال کرو.

4. Balanced Trees: aik tree balanced کہلاتا ہے جب اس کی left اور right branches کی height تقریبا برابر ہو. اگر ایک طرف بہت لمبی اور دوسری طرف بہت چھوٹی ہو تو tree unbalanced کہلائے گا اور search دھیمی ہو سکتی ہے.

Trees صرف family tree بنانے کے لیے نہیں — computer کے اندر روز کام آتے ہیں. 1. File Systems (Pre-order): جب file system کا backup بنایا جاتا ہے تو pre-order traversal استعمال ہوتی ہے — پہلے root (directory) visit کرو, پھر recursively اس کے اندر کی چیزیں. اس طرح directory اپنے contents سے پہلے backup ہو جاتی ہے, جو backup کی ترتیب کے لیے ضروری ہے.

2. File System Deletion (Post-order): delete kartay waqt ulta tareeqa — post-order traversal. پہلے تمام sub-directories اور files delete کرو, پھر parent directory. اگر پہلے parent delete کر دیا جائے تو اندر کی چیزیں پھنس جائیں گی; post-order اسی غلطی سے بچاتا ہے.

3. Hierarchical Data Representation: organisation charts اور family trees جیسے data جن میں اوپر-نیچے کا رشتہ ہو, tree میں سب سے صاف نظر آتے ہیں. 4. Decision Making: decision trees میں ہر node ایک شرط ہوتی ہے اور ہر branch ایک ممکن نتیجہ — algorithm شرط در شرط آگے بڑھ کر فیصلہ کرتا ہے.

Tree میں ہر چیز کی ایک جگہ ہوتی ہے — اوپر root, نیچے branches. Graph اس پابندی کو توڑ دیتا ہے. Graph ایک ایسا structure ہے جو vertices (nodes) کے ایک set اور ان کو جوڑنے والی edges پر مشتمل ہوتا ہے. Vertices کچھ بھی ہو سکتے ہیں — شہر, log, websites — اور edges ان کے درمیان رشتہ یا راستہ بتاتی ہیں.

کتاب کی مثال لو: Pakistan کے تمام شہروں کا نقشہ بناؤ. ہر شہر ایک vertex, aur shehron ke darmiyan har road aik edge. Social network میں بھی یہی ہے: ہر شخص ایک vertex, اور دوستی ایک edge. Tree کے bar-عکس graph کا کوئی ایک "root" نہیں ہوتا اور کوئی hierarchy نہیں ہوتی — کوئی بھی vertex کسی بھی vertex سے جڑ سکتا ہے, اور یہ جال (web) جیسا دکھتا ہے.

Graph کو سمجھنے کے لیے تین لفظ کافی ہیں. Degree: کسی vertex سے کتنی edges جڑی ہوئی ہیں, وہی اس vertex کی degree ہے. کتاب کی مثال: اگر ایک شہر تین دوسرے شہروں سے جڑا ہے تو اس vertex کی degree 3 ہے. Degree بتاتی ہے کہ وہ point کتنا "connected" ہے.

Weight: کچھ graphs میں ہر edge پر ایک number لکھا ہوتا ہے — distance, وقت یا cost. مثال: دو شہروں کے درمیان road 50 kilometre لمبی ہے تو اس edge کا weight 50 ہوگا. Weight والے graphs سے shortest یا cheapest راستہ نکالا جاتا ہے.

Direction: edge ایک طرف کی ہو سکتی ہے یا دونوں طرف کی. Directed edge one-way ہوتی ہے — شہر A سے شہر B تک road ہے, اس کا مطلب یہ نہیں کہ B سے A تک بھی وہی road ہے. Undirected edge two-way ہوتی ہے — دونوں طرف سفر ممکن ہے. (کتاب میں 4.1.5.1 "Characteristics" کے نام پر کوئی الگ list نہیں دی گئی; اصل تفصیل 4.1.5.2 Properties میں ہے, اس لیے دونوں یہاں ایک ساتھ سمجھائی گئی ہیں.)

1. Directed Graphs: جن میں edges کی direction ہوتی ہے — وہ ایک vertex سے دوسرے تک ایک خاص طرف جاتی ہیں. کتاب کی Figure 4.4 ایک directed weighted graph ہے: B→A (10), A→C (12), A→D (60), C→D (32), C→B (20), E→A (7). اب کتاب کی مثال حل کرو: کیا تم A سے سیدھا B جا سکتے ہو? نہیں — A سے نکلنے والی edges صرف C اور D کی طرف جاتی ہیں, B کی طرف کوئی تیر نہیں. A سے B جانے کے لیے راستہ A→C→B ہے, جس کا total weight 12 + 20 = 32 بنتا ہے.

2. Undirected Graphs: جن میں edges کی کوئی direction نہیں ہوتی — connection ہے تو دونوں طرف سفر ممکن ہے. Figure 4.5 میں A–B, B–C, B–D, B–E, A–E, C–D, D–E سب بغیر تیر کے ہیں. کتاب کی مثال: اگر Person A, Person B کا دوست ہے تو Person B بھی Person A کا دوست ہے — دوستی one-way نہیں ہوتی, اس لیے undirected graph ٹھیک ہے.

3. Weighted Graphs: جن میں ہر edge پر weight (distance, time ya cost) لکھا ہوتا ہے — جیسا Figure 4.4 میں ہے. شہر کے نقشے کی مثال لو: ہر road پر اس کا فاصلہ یا travel time لکھا ہو تو تم shortest یا quickest راستہ chun سکتے ہو. Directed/undirected بتاتا ہے kis taraf جا سکتے ہو, weighted بتاتا ہے kitni cost par.

Chapter کے Student Learning Outcomes میں ایک بات خاص ہے: صرف structures کے نام یاد کرنا کافی نہیں — maslay ke hisaab se sahi structure chunna آنا چاہیے. یہ section کتاب کے SLOs اور introduction سے لیا گیا خلاصہ ہے (کتاب میں اس کے لیے کوئی الگ heading نہیں ہے, اس لیے اسے derived guidance سمجھو).

سیدھا اصول یہ ہے: tartib wali list چاہیے تو list; aakhri aaya pehle jaye (undo, back button) to stack; pehle aaya pehle jaye (ticket line, printer) to queue; oopar-neechay ka rishta (folders, family) to tree; jaal jaisa rishta (dosti, roads, networks) تو graph. اور اکثر ایک مسئلہ ایک structure سے حل نہیں ہوتا — مثال کے طور پر ایک network app میں graph roads بتائے گا اور queue requests کو ترتیب سے چلائے گی. Structures کو combine کرنا ہی اصل programming ہے.