Deque (អានថា “deck”) គឺជា double-ended queue៖ អ្នកអាច push និង pop នៅខាងមុខ និងខាងក្រោយបានទាំងសងខាង។ វាអាចដំណើរការជា stack ផង ជា queue ផង ឬទាំងពីរដំណាលគ្នាក៏បាន។ Visualizer នេះបង្កើត deque លើ ring buffer ចំនួន 8 ចន្លោះ ហើយបង្ហាញវាជារង្វង់ និងជា array ដោយមាន front និង rear pointers រំកិលទៅមកទាំងសងខាង។
Push front រំកិល front ថយក្រោយមួយជំហាន ដោយវិលជុំពី 0 ទៅ 7፤ ចំណែក push back រំកិល rear ទៅមុខ។ រាល់ប្រតិបត្តិការទាំងអស់មានគំនូរជីវចលបង្ហាញជាមួយការគណនាសន្ទស្សន៍ច្បាស់លាស់ ហើយប្រតិបត្តិការទាំងបួនដំណើរការក្នុងរយៈពេល O(1)។
របៀបប្រើឧបករណ៍ កម្មវិធីបង្ហាញ Deque
- វាយតម្លៃរួចចុច Push front ឬ Push back។
- ចុច Pop front ឬ Pop back ដើម្បីដកចេញពីខាងមុខ ឬខាងក្រោយ។
- មើល front រំកិលថយក្រោយ និង rear រំកិលទៅមុខជុំវិញរង្វង់។
- ប្រើ Step និង Back ដើម្បីពិនិត្យមើលការគណនាសន្ទស្សន៍នីមួយៗ។
ហេតុអ្វីប្រើ កម្មវិធីបង្ហាញ Deque របស់ ToolOrca
- Push និង pop នៅចុងសងខាង
- ទិដ្ឋភាពជារង្វង់ និងជា array
- បង្ហាញការគណនាសន្ទស្សន៍ពេលវិលជុំ
- ការពិនិត្យស្ថានភាពពេញ និងទទេ
- បន្លិច Pseudocode សម្រាប់ជំហាននីមួយៗ
- កូដជា C++, Java, Python និង JavaScript
ដំណើរការរបស់ deque
Deque គាំទ្រ pushFront, pushBack, popFront និង popBack ហើយជាទូទៅក៏មាន peekFront និង peekBack ផងដែរ។ លើ ring buffer ទំហំ N ប្រតិបត្តិការ pushFront ដំណើរការ front = (front − 1 + N) mod N ហើយសរសេរនៅទីនោះ ចំណែក pushBack ដំណើរការ rear = (rear + 1) mod N។ ការបូក N មុនពេលធ្វើ modulo ជួយការពារកុំឱ្យសន្ទស្សន៍ចេញតម្លៃអវិជ្ជមាន។
Deque ក៏អាចបង្កើតជា doubly linked list បានដែរ។ ប៉ុន្តែកំណែ ring buffer ប្រើអង្គចងចាំតិចជាង និងលឿនជាងក្នុងការអនុវត្តជាក់ស្តែង ដូច្នេះហើយ ArrayDeque របស់ Java, collections.deque របស់ Python (ប្រើ blocks នៃ slots) និង std::deque របស់ C++ (ប្រើ chunks នៃ arrays) សុទ្ធតែចៀសវាងការបង្កើត node មួយសម្រាប់ធាតុមួយ។
ពេលណាដែលត្រូវប្រើ deque
ប្រើ deque នៅពេលអ្នកត្រូវការលក្ខណៈសម្បត្តិទាំង stack និង queue៖ បញ្ហា sliding window maximum, ប្រវត្តិ undo ដែលមានកម្រិតទំហំ, work-stealing schedulers, ការពិនិត្យពាក្យ palindrome និង 0-1 BFS ក្នុងក្រាហ្វ។ នៅក្នុង Java ថ្នាក់ ArrayDeque គឺជាជម្រើសដែលត្រូវបានណែនាំឱ្យប្រើសម្រាប់ទាំង stack និង queue។
Visualizer ទាំងអស់នៅលើគេហទំព័រនេះដំណើរការក្នុងកម្មវិធីរុករករបស់អ្នក ជាមួយប៊ូតុងបញ្ជាដូចគ្នា៖ Play, Pause, Step forward, Step back និងគ្រាប់រំកិលល្បឿន។ អ្នកក៏អាចអូសគ្រាប់រំកិលទីតាំងដើម្បីផ្លោះទៅជំហានណាមួយ ឬចុចលើផ្ទាំងគំនូររួចប្រើ Space bar និងគ្រាប់ចុចព្រួញ។
សំណួរដែលសួរញឹកញាប់
តើ deque គឺជាអ្វី?
Double-ended queue៖ ជាលំដាប់ទិន្នន័យដែលអ្នកអាចបន្ថែម និងដកធាតុចេញបានទាំងនៅខាងមុខ និងខាងក្រោយ។
តើ time complexity នៃប្រតិបត្តិការ deque គឺជាអ្វី?
Push និង pop នៅចុងសងខាងគឺ O(1)។ លើ ring buffer ការចូលប្រើតាមសន្ទស្សន៍ក៏ជា O(1) ដែរ។
តើ deque ជា stack ឬជា queue?
វាអាចជាទាំងពីរ។ បើប្រើតែម្ខាង វាគឺជា stack፤ បើ push ម្ខាងហើយ pop ម្ខាងទៀត វាគឺជា queue។
តើខ្ញុំគួរប្រើ deque មួយណា ក្នុង Python ឬ Java?
Python៖ collections.deque ជាមួយ append, appendleft, pop និង popleft។ Java៖ ArrayDeque ជាមួយ addFirst, addLast, pollFirst និង pollLast។