Embedded Files
Home / ອານກໍລິກທຶມ / ສະແຕັກ Stack
ບົດທີ 4 Stacks ແລະ queues
ບົດທີ 4 Stacks ແລະ queues
- ຄວາມຮູ້ພື້ນຖານກ່ຽວກັບ stacks ແລະ queues
stacks ແລະ queues ແມ່ນສອງໂຄງສ້າງຂໍ້ມູນພື້ນຖານທີ່ຖືກນໍາໃຊ້ເພື່ອເກັບຮັກສາແລະຈັດການການລວບລວມອົງປະກອບ. ພວກເຂົາແມ່ນທັງສອງປະເພດຂໍ້ມູນທີ່ບໍ່ມີຕົວຕົນ, ຊຶ່ງຫມາຍຄວາມວ່າພວກເຂົາຖືກກໍານົດໃນແງ່ຂອງພຶດຕິກໍາຂອງພວກເຂົາແທນທີ່ຈະປະຕິບັດ.
stack ແມ່ນໂຄງສ້າງຂໍ້ມູນທີ່ປະຕິບັດຕາມຫຼັກການການສັ່ງຊື້ Last-In-First-Out (LIFO). ນີ້ຫມາຍຄວາມວ່າອົງປະກອບສຸດທ້າຍທີ່ເພີ່ມໃສ່ stack ຈະເປັນອົງປະກອບທໍາອິດທີ່ເອົາອອກຈາກ stack. Stacks ສາມາດຄິດວ່າເປັນ stack ຂອງແຜ່ນ, ບ່ອນທີ່ແຜ່ນສຸດທ້າຍທີ່ເພີ່ມເຂົ້າໄປໃນ stack ແມ່ນທໍາອິດທີ່ເອົາອອກ.
ໃນທາງກົງກັນຂ້າມ, A ຄິວປະຕິບັດຕາມຫຼັກການການສັ່ງຊື້ First-in-First-Out (FIFO). ນີ້ຫມາຍຄວາມວ່າອົງປະກອບທໍາອິດທີ່ເພີ່ມໃສ່ຄິວຈະເປັນອົງປະກອບທໍາອິດທີ່ຖືກລຶບອອກຈາກຄິວ. ຄິວສາມາດຄິດວ່າເປັນແຖວຂອງຄົນທີ່ລໍຖ້າໃຫ້ບໍລິການ, ເຊິ່ງຜູ້ທີ່ມາຮອດກ່ອນແມ່ນຄົນທໍາອິດທີ່ໄດ້ຮັບການບໍລິການ.
ການປະຕິບັດຕົ້ນຕໍສອງອັນໃນ stack ແມ່ນ push ແລະ pop, ເຊິ່ງເພີ່ມແລະເອົາອົງປະກອບອອກຈາກເທິງຂອງ stack, ຕາມລໍາດັບ. ການດໍາເນີນງານອື່ນໆໃນ stack ປະກອບມີ peek, ເຊິ່ງດຶງເອົາອົງປະກອບເທິງໂດຍບໍ່ມີການເອົາມັນອອກ, ຂະຫນາດ, ເຊິ່ງສົ່ງຄືນຈໍານວນອົງປະກອບໃນ stack, ແລະຫວ່າງເປົ່າ, ເຊິ່ງກວດເບິ່ງວ່າ stack ແມ່ນຫວ່າງບໍ່.
ເຊັ່ນດຽວກັນ, ສອງການດໍາເນີນງານຕົ້ນຕໍໃນແຖວແມ່ນ enqueue ແລະ dequeue, ເຊິ່ງເພີ່ມແລະເອົາອົງປະກອບຈາກດ້ານຫລັງແລະດ້ານຫນ້າຂອງແຖວ, ຕາມລໍາດັບ. ການດໍາເນີນງານອື່ນໆໃນຄິວປະກອບມີ peek, ຂະຫນາດ, ແລະຫວ່າງເປົ່າ.
stacks ແລະແຖວສາມາດຖືກປະຕິບັດໂດຍໃຊ້ arrays ຫຼືລາຍຊື່ທີ່ເຊື່ອມໂຍງ. ການປະຕິບັດທີ່ອີງໃສ່ array ປົກກະຕິແລ້ວແມ່ນໄວຂຶ້ນ, ແຕ່ພວກເຂົາຕ້ອງການຂະຫນາດຄົງທີ່ສໍາລັບ stack ຫຼືແຖວ. ໃນທາງກົງກັນຂ້າມ, ການປະຕິບັດບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງ, ອະນຸຍາດໃຫ້ຂະຫນາດແບບເຄື່ອນໄຫວແຕ່ຊ້າກວ່າ.
Stacks ແລະຄິວແມ່ນໃຊ້ໃນຫຼາຍຄໍາຮ້ອງສະຫມັກການຂຽນໂປລແກລມ, ເຊັ່ນ: ການປະເມີນຜົນການສະແດງອອກ, syntax parsing, ແລະລະບົບ backtracking algorithms (ສໍາລັບ stacks), ແລະການຈໍາລອງ, ການກໍານົດເວລາວຽກ, ແລະເຄືອຂ່າຍ packet routing (ສໍາລັບຄິວ).
2. ປະເພດ Stacks ແລະ queues
2. ປະເພດ Stacks ແລະ queues
Stack: ໂຄງສ້າງຂໍ້ມູນ stack ພື້ນຖານປະຕິບັດຕາມຫຼັກການ LIFO. ອົງປະກອບຖືກເພີ່ມແລະເອົາອອກຈາກດ້ານເທິງຂອງ stack.
ຄິວ: ໂຄງສ້າງຂໍ້ມູນຄິວພື້ນຖານປະຕິບັດຕາມຫຼັກການ FIFO. ອົງປະກອບຖືກເພີ່ມຢູ່ດ້ານຫລັງຂອງແຖວແລະເອົາອອກຈາກດ້ານຫນ້າ.
ຄິວບູລິມະສິດ: ແຖວບູລິມະສິດແມ່ນການປ່ຽນແປງຂອງໂຄງສ້າງຂໍ້ມູນແຖວທີ່ແຕ່ລະອົງປະກອບມີບູລິມະສິດທີ່ກ່ຽວຂ້ອງກັບມັນ. ອົງປະກອບຖືກໂຍກຍ້າຍອອກຈາກຄິວຕາມລໍາດັບຄວາມສໍາຄັນຂອງພວກມັນ, ໂດຍອົງປະກອບບູລິມະສິດສູງສຸດຈະຖືກລຶບອອກກ່ອນ. ແຖວບູລິມະສິດແມ່ນຖືກນໍາໃຊ້ທົ່ວໄປໃນການກໍານົດເວລາແລະຄໍາຮ້ອງສະຫມັກການຈັດສັນຊັບພະຍາກອນ.
Circular Queue: ຄິວວົງວຽນແມ່ນການປ່ຽນແປງຂອງໂຄງສ້າງຂໍ້ມູນຄິວພື້ນຖານທີ່ແຖວໜ້າ ແລະດ້ານຫຼັງຂອງແຖວເຊື່ອມຕໍ່ກັນເປັນວົງກົມ. ອັນນີ້ອະນຸຍາດໃຫ້ໃຊ້ຄວາມຊົງຈໍາໄດ້ຢ່າງມີປະສິດທິພາບ ແລະອະນຸຍາດໃຫ້ຄິວຫໍ່ໄປເຖິງຈຸດເລີ່ມຕົ້ນເມື່ອມັນເຕັມ.
Double Ended Queue (Deque): A deque ແມ່ນການປ່ຽນແປງຂອງໂຄງສ້າງຂໍ້ມູນແຖວທີ່ອົງປະກອບສາມາດຖືກເພີ່ມ ຫຼືເອົາອອກຈາກຈຸດສິ້ນສຸດຂອງ deque. ນີ້ອະນຸຍາດໃຫ້ມີຄວາມຍືດຫຍຸ່ນຫຼາຍໃນວິທີການໂຄງສ້າງຂໍ້ມູນຖືກນໍາໃຊ້.
Stack with Minimum: stack ທີ່ມີຕໍາ່ສຸດແມ່ນການປ່ຽນແປງຂອງໂຄງສ້າງຂໍ້ມູນ stack ພື້ນຖານທີ່ຍັງຕິດຕາມອົງປະກອບຕໍາ່ສຸດທີ່ໃນ stack. ນີ້ສາມາດເປັນປະໂຫຍດໃນບາງຄໍາຮ້ອງສະຫມັກ, ເຊັ່ນ: ການຊອກຫາອົງປະກອບຕໍາ່ສຸດໃນ stack ໃນເວລາຄົງທີ່.
Stack with Maximal Element: stack ທີ່ມີອົງປະກອບສູງສຸດແມ່ນການປ່ຽນແປງຂອງໂຄງສ້າງຂໍ້ມູນ stack ພື້ນຖານທີ່ຍັງຕິດຕາມອົງປະກອບສູງສຸດໃນ stack. ນີ້ສາມາດເປັນປະໂຫຍດໃນບາງຄໍາຮ້ອງສະຫມັກ, ເຊັ່ນ: ຊອກຫາອົງປະກອບສູງສຸດໃນ stack ໃນໄລຍະເວລາຄົງທີ່.
ຄວາມເຂົ້າໃຈກ່ຽວກັບປະເພດທີ່ແຕກຕ່າງກັນຂອງ stacks ແລະແຖວແລະຄຸນສົມບັດຂອງມັນແມ່ນສໍາຄັນສໍາລັບການເລືອກໂຄງສ້າງຂໍ້ມູນທີ່ເຫມາະສົມກັບຄໍາຮ້ອງສະຫມັກທີ່ກໍານົດໄວ້.
3. ຄວາມສາມາພື້ນຖານ stack and queues
3. ຄວາມສາມາພື້ນຖານ stack and queues
ທັງ stacks ແລະແຖວສະຫນັບສະຫນູນບາງການດໍາເນີນງານພື້ນຖານທີ່ຖືກນໍາໃຊ້ທົ່ວໄປໃນການດໍາເນີນໂຄງການ:
stacks:
Push: ເພີ່ມອົງປະກອບໃສ່ເທິງສຸດຂອງ stack.
pop: ເອົາອົງປະກອບເທິງສຸດອອກຈາກ stack ແລະສົ່ງຄືນມັນ.
Peek: ສົ່ງຄືນອົງປະກອບເທິງໂດຍບໍ່ຕ້ອງເອົາມັນອອກ.
Size: ຕອບຈໍານວນອົງປະກອບໃນ stack.
Empty: ກວດເບິ່ງວ່າ stack ແມ່ນຫວ່າງບໍ່.
ຄິວ:
Enqueue: ເພີ່ມອົງປະກອບໃສ່ດ້ານຫຼັງຂອງຄິວ.
Dequeue: ເອົາອົງປະກອບທາງຫນ້າອອກຈາກຄິວແລະສົ່ງຄືນມັນ.
Peek: ສົ່ງຄືນອົງປະກອບທາງຫນ້າໂດຍບໍ່ຕ້ອງເອົາມັນອອກ.
Size: ຕອບຈຳນວນອົງປະກອບໃນຄິວ.
Empty: ກວດເບິ່ງວ່າຄິວຫວ່າງບໍ່.
ນອກເຫນືອໄປຈາກການດໍາເນີນງານຂັ້ນພື້ນຖານເຫຼົ່ານີ້, ມີບາງການດໍາເນີນງານພິເສດທີ່ສາມາດປະຕິບັດໄດ້ໃນ stacks ແລະແຖວຂຶ້ນຢູ່ກັບຄໍາຮ້ອງສະຫມັກ. ຕົວຢ່າງ, ໃນແຖວບູລິມະສິດ, ອົງປະກອບອາດມີບູລິມະສິດທີ່ກ່ຽວຂ້ອງກັບພວກມັນ, ແລະການດໍາເນີນງານພິເສດເຊັ່ນ "ໃສ່ກັບບູລິມະສິດ" ແລະ "ເອົາອອກດ້ວຍຄວາມສໍາຄັນສູງສຸດ" ອາດຈະມີຢູ່.
ຄວາມສັບສົນທີ່ໃຊ້ເວລາຂອງການດໍາເນີນງານເຫຼົ່ານີ້ແມ່ນຂຶ້ນກັບການປະຕິບັດສະເພາະຂອງ stack ຫຼືແຖວ. ຕົວຢ່າງ, ການດໍາເນີນງານ push, pop, ແລະ peek ໃນ stack ປະຕິບັດໂດຍໃຊ້ array ໃຊ້ເວລາຄົງທີ່, ໃນຂະນະທີ່ການດໍາເນີນງານດຽວກັນເຫຼົ່ານີ້ຢູ່ໃນ stack ປະຕິບັດໂດຍໃຊ້ບັນຊີລາຍຊື່ທີ່ເຊື່ອມຕໍ່ໃຊ້ເວລາ linear.
ມັນເປັນສິ່ງສໍາຄັນທີ່ຈະເລືອກເອົາໂຄງສ້າງຂໍ້ມູນທີ່ເຫມາະສົມກັບຄໍາຮ້ອງສະຫມັກທີ່ກໍານົດໄວ້ໂດຍອີງໃສ່ຄວາມຕ້ອງການສະເພາະຂອງບັນຫາທີ່ມີຢູ່ໃນມື. Stacks ມັກຈະຖືກນໍາໃຊ້ໃນ algorithms ທີ່ຕ້ອງການ backtracking ຫຼືໃນກໍລະນີທີ່ຄໍາສັ່ງຂອງການດໍາເນີນງານມີຄວາມສໍາຄັນ, ໃນຂະນະທີ່ແຖວມັກຈະຖືກນໍາໃຊ້ໃນການຈໍາລອງ, ການກໍານົດເວລາວຽກ, ແລະຄໍາຮ້ອງສະຫມັກອື່ນໆທີ່ອົງປະກອບຕ້ອງໄດ້ຮັບການປຸງແຕ່ງໃນຄໍາສັ່ງທີ່ເຂົາເຈົ້າໄດ້ຖືກເພີ່ມ.
Page updated
Google Sites
Report abuse