Stack គឺជាបណ្តុំទិន្នន័យបែបចូលក្រោយចេញមុន (LIFO)៖ អ្នកអាចបន្ថែម (push) និងដកចេញ (pop) តែនៅផ្នែកខាងលើបង្អស់ (top) ប៉ុណ្ណោះ ដូចជាជង់ចានអញ្ចឹងដែរ។ ឧបករណ៍ visualizer នេះបង្ហាញ stack ជាពីររបៀប។ កំណែ array គឺជាប្លុកកំណត់ទំហំ 8 ចន្លោះ ជាមួយសន្ទស្សន៍ top ដូច្នេះអ្នកអាចឃើញថា stack overflow មានន័យដូចម្តេចនៅពេលអ្នក push ទៅលើ stack ដែលពេញ។ កំណែ linked រក្សាទុកតម្លៃនីមួយៗក្នុង node នៅអាសយដ្ឋានអង្គចងចាំរៀងៗខ្លួន ដោយចង្អុលទៅ node នៅខាងក្រោមវា។
Push, pop និង peek ត្រូវបានបង្ហាញជាគំនូរជីវចលម្តងមួយជំហានៗ ជាមួយការបន្លិចបន្ទាត់ pseudocode ត្រូវគ្នា ហើយតម្លៃដែលបាន pop នឹងប្រមូលផ្តុំនៅចំហៀង ដើម្បីឱ្យអ្នកឃើញថាពួកវាចេញមកតាមលំដាប់បញ្ច្រាស។ ប្រតិបត្តិការទាំងបីប្រើពេល O(1) ក្នុងកំណែទាំងពីរ។
របៀបប្រើឧបករណ៍ បង្ហាញដំណើរការ Stack
- ជ្រើសរើស Array ឬ Linked list។
- វាយតម្លៃរួចចុច Push។ ចុច Pop ដើម្បីដកតម្លៃខាងលើបង្អស់ចេញ ឬ Peek ដើម្បីមើលវា។
- បន្ត push លើ array stack ដើម្បីបង្កើត overflow ឬ pop លើ stack ទទេដើម្បីឃើញ underflow។
- ប្រើ Step និង Back ដើម្បីតាមដានប្រតិបត្តិការនីមួយៗ និងអាន pseudocode។
ហេតុអ្វីប្រើ បង្ហាញដំណើរការ Stack របស់ ToolOrca
- Array stack មានទំហំផ្ទុក សន្ទស្សន៍ top និង overflow
- Linked stack មានអាសយដ្ឋាន node និង next pointers
- គំនូរជីវចល Push, pop និង peek
- តម្លៃដែល pop ចេញ បង្ហាញតាមលំដាប់ដែលបានដក
- សារជូនដំណឹង Underflow និង overflow
- កូដជា C++, Java, Python និង JavaScript
ដំណើរការរបស់ stack
Stack គាំទ្រប្រតិបត្តិការចម្បងបី៖ push(x) បន្ថែម x ទៅលើគេ, pop() ដកចេញ និងបង្ហាញតម្លៃលើគេបង្អស់, និង peek() (ឬ top) បង្ហាញតម្លៃលើគេដោយមិនដកចេញ។ តម្លៃដែល push ចូលចុងក្រោយគេ តែងតែជាតម្លៃដែលត្រូវ pop ចេញមុនគេ ដែលហៅថា LIFO។
នៅក្នុង array stack អថេរ top ផ្ទុកសន្ទស្សន៍នៃធាតុខាងលើបង្អស់ (−1 ពេលទទេ)។ Push ដំណើរការ top = top + 1 ហើយរក្សាទុកតម្លៃនោះ፤ pop អាន a[top] និងបន្ថយ top។ ប្រសិនបើ array ពេញ ការ push នឹងបង្កឱ្យមាន stack overflow፤ ការ pop លើ stack ទទេ គឺជា stack underflow។ ចំណែក linked stack ធ្វើ push ដោយបង្កើត node ថ្មីដែលចង្អុលទៅ top ចាស់ ដូច្នេះវានឹងពេញលុះត្រាតែអស់អង្គចងចាំប៉ុណ្ណោះ。
កន្លែងដែលគេប្រើ stack
Stack ត្រូវបានប្រើប្រាស់គ្រប់ទីកន្លែងក្នុងវិស័យកុំព្យូទ័រ។ Call stack ផ្ទុកអថេរមូលដ្ឋាន និង return address នៃការហៅអនុគមន៍នីមួយៗ ដែលជាប្រភពនៃកំហុស “stack overflow” ពេលមាន recursion ជ្រៅពេក។ Stack ក៏ត្រូវបានប្រើសម្រាប់បង្កើតមុខងារ undo, ប៊ូតុង back លើកម្មវិធីរុករក, ការពិនិត្យវង់ក្រចកផ្គូផ្គង, ការគណនាកន្សោម reverse Polish notation, ការបំប្លែង infix ទៅ postfix, និង depth-first search។
Visualizer ទាំងអស់នៅលើគេហទំព័រនេះដំណើរការក្នុងកម្មវិធីរុករករបស់អ្នក ជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, Step forward, Step back និងគ្រាប់រំកិលល្បឿន។ អ្នកក៏អាចអូសគ្រាប់រំកិលទីតាំងដើម្បីផ្លោះទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូររួចប្រើ Space bar និងគ្រាប់ចុចព្រួញ។
សំណួរដែលសួរញឹកញាប់
តើ LIFO មានន័យដូចម្តេច?
Last in, first out (ចូលក្រោយ ចេញមុន)៖ ធាតុដែលទើបតែបន្ថែមចុងក្រោយគេ គឺជាធាតុដំបូងគេដែលត្រូវដកចេញ ដូចជាការលើកចានលើគេបង្អស់ចេញពីជង់ចាន។
តើ time complexity នៃ push និង pop គឺជាអ្វី?
ទាំងពីរគឺ O(1) សម្រាប់ array និង linked stack។ ចំពោះ dynamic array stack ពេលខ្លះត្រូវការបង្កើនទំហំ ប៉ុន្តែ push នៅតែជា O(1) amortized។
តើ stack overflow និង underflow ខុសគ្នាយ៉ាងដូចម្តេច?
Overflow គឺជាការ push ទៅលើ stack ដែលពេញរួចហើយ។ Underflow គឺជាការ pop ឬ peek លើ stack ដែលទទេ។
តើខ្ញុំគួរប្រើ array ឬ linked list សម្រាប់ stack?
ជាទូទៅគួរប្រើ array (ឬ dynamic array)៖ វាប្រើអង្គចងចាំតិចជាង និងលឿនជាង ព្រោះតម្លៃស្ថិតនៅក្បែរគ្នាក្នុងអង្គចងចាំ។ Linked stack មិនចាំបាច់ប្តូរទំហំឡើងវិញទេ ដែលមានប្រយោជន៍ក្នុងកូដកម្រិតទាប (low-level) មួយចំនួន។
តើត្រូវប្រើ stack ក្នុង Python, Java ឬ JavaScript យ៉ាងដូចម្តេច?
Python៖ ប្រើ list ជាមួយ append() និង pop()។ Java៖ ប្រើ ArrayDeque ជាមួយ push(), pop() និង peek()។ JavaScript៖ ប្រើ array ជាមួយ push() និង pop()។ C++៖ ប្រើ std::stack។