Queue គឺជាបណ្តុំទិន្នន័យបែបចូលមុនចេញមុន (FIFO) ដូចជាជួរតម្រង់ជួរនៅហាងទំនិញ៖ ធាតុថ្មីចូលតាម rear (ខាងក្រោយ) ហើយចាកចេញតាម front (ខាងមុខ)។ ឧបករណ៍ visualizer នេះរក្សាទុក queue ក្នុង array ចំនួន 8 ចន្លោះ ជាមួយសន្ទស្សន៍ front និងសន្ទស្សន៍ rear ព្រមទាំងបង្ហាញគំនូរជីវចលនៃរាល់ enqueue, dequeue និង peek ជាមួយ pseudocode ត្រូវគ្នា។
បន្ត enqueue និង dequeue នោះអ្នកនឹងឃើញចំណុចខ្សោយនៃ array queue ធម្មតានេះ៖ rear ដើរដល់ចន្លោះចុងក្រោយ ហើយ queue បង្ហាញថាពេញ ទោះបីជាចន្លោះនៅខាងមុខ front នៅទំនេរក៏ដោយ។ ការខាតបង់ទំហំទំនេរនេះហើយ គឺជាបញ្ហាដែល circular queue ចូលមកដោះស្រាយ។
របៀបប្រើឧបករណ៍ បង្ហាញដំណើរការ Queue
- វាយតម្លៃរួចចុច Enqueue ដើម្បីបន្ថែមវាទៅខាងក្រោយ។
- ចុច Dequeue ដើម្បីដកតម្លៃនៅខាងមុខចេញ ឬ Peek ដើម្បីមើលវា។
- មើលសញ្ញាសម្គាល់ front និង rear នៅក្រោម array រំកិលទៅស្តាំ។
- បញ្ចូលទិន្នន័យឱ្យពេញរហូតដល់ចុងបញ្ចប់ ដើម្បីឃើញបញ្ហា “ពេញនៅខាងចុង” រួចប្រៀបធៀបជាមួយ circular queue។
ហេតុអ្វីប្រើ បង្ហាញដំណើរការ Queue របស់ ToolOrca
- Array queue ជាមួយសន្ទស្សន៍ front និង rear
- គំនូរជីវចល Enqueue, dequeue និង peek មួយជំហានម្តងៗ
- បង្ហាញបញ្ហាខាតបង់ទំហំនៃ linear queue
- បន្លិច Pseudocode សម្រាប់ជំហាននីមួយៗ
- កូដជា C++, Java, Python និង JavaScript
- តារាង Complexity
ដំណើរការរបស់ queue
Queue មានសងខាង។ enqueue(x) បន្ថែម x នៅខាងក្រោយ, dequeue() ដកចេញ និងបង្ហាញតម្លៃខាងមុខ, និង peek() បង្ហាញតម្លៃខាងមុខដោយមិនដកចេញ។ តម្លៃដែលចូលមុនគេ តែងតែជាតម្លៃដែលចេញមុនគេជានិច្ច៖ FIFO។
នៅក្នុង array queue ធម្មតា front ចាប់ផ្តើមពី 0 ហើយ rear ចាប់ផ្តើមពី −1។ Enqueue បង្កើន rear និងសរសេរតម្លៃចូល፤ dequeue អាន a[front] និងបង្កើន front។ ទាំងពីរប្រើ O(1)។ ចំណុចសំខាន់គឺ front និង rear រំកិលទៅខាងស្តាំប៉ុណ្ណោះ។ នៅពេល rear ដល់ទីបញ្ចប់ គ្មានតម្លៃណាអាចដាក់ចូលបានទៀតទេ ទោះបីជាចន្លោះខាងមុខនៅសល់ច្រើនក៏ដោយ។ ការរុញធាតុទាំងអស់ត្រឡប់ទៅសន្ទស្សន៍ 0 វិញអាចដោះស្រាយបាន តែត្រូវចំណាយ O(n) រាល់ពេល dequeue ម្តងៗ។
កន្លែងដែលគេប្រើ queue
Queue ត្រូវបានប្រើសម្រាប់ដំណើរការការងារណាដែលត្រូវរង់ចាំតាមវេន៖ print jobs, keyboard input buffers, សំណើ web server, message queues រវាងសេវាកម្ម, task schedulers និង breadth-first search ក្នុងក្រាហ្វ។ ភាសាភាគច្រើនមានផ្ដល់ជូនរួចជាស្រេច៖ std::queue ក្នុង C++, ArrayDeque ក្នុង Java, collections.deque ក្នុង Python។
Visualizer ទាំងអស់នៅលើគេហទំព័រនេះដំណើរការក្នុងកម្មវិធីរុករករបស់អ្នក ជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, Step forward, Step back និងគ្រាប់រំកិលល្បឿន។ អ្នកក៏អាចអូសគ្រាប់រំកិលទីតាំងដើម្បីផ្លោះទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូររួចប្រើ Space bar និងគ្រាប់ចុចព្រួញ។
សំណួរដែលសួរញឹកញាប់
តើ FIFO មានន័យដូចម្តេច?
First in, first out (ចូលមុន ចេញមុន)៖ ធាតុនានាចាកចេញពី queue តាមលំដាប់លំដោយដូចគ្នាទៅនឹងពេលដែលពួកវាបានចូលមក។
តើ stack និង queue ខុសគ្នាយ៉ាងដូចម្តេច?
Stack ដកធាតុថ្មីបំផុតចេញមុនគេ (LIFO) ចំណែកឯ queue ដកធាតុចាស់ជាងគេចេញមុនគេ (FIFO)។
ហេតុអ្វីបានជា array queue ធម្មតារាយការណ៍ថាពេញ ទាំងដែលវាមិនទាន់ពេញ?
ពីព្រោះ front និង rear រំកិលទៅមុខតែប៉ុណ្ណោះ។ នៅពេល rear ដល់សន្ទស្សន៍ចុងក្រោយ ចន្លោះទំនេរនៅខាងមុខ front មិនអាចយកមកប្រើឡើងវិញបានទេ។ Circular queue ដោះស្រាយបញ្ហានេះដោយបង្វិល rear ត្រឡប់ទៅសន្ទស្សន៍ 0 វិញ។
ហេតុអ្វីមិនគួរប្រើ list.pop(0) ក្នុង Python ធ្វើជា queue?
ការដកធាតុដំបូងនៃ Python list ត្រូវរំកិលធាតុផ្សេងទៀតទាំងអស់ ដែលស៊ីពេល O(n)។ collections.deque អាចដកពីខាងមុខក្នុងរយៈពេល O(1)។