โครงสร้างข้อมูลคือชุดของค่าข้อมูลความสัมพันธ์ระหว่างกันและฟังก์ชันหรือการดำเนินการที่สามารถนำไปใช้กับข้อมูลได้ ตอนนี้มีโครงสร้างข้อมูลมากมาย แต่วันนี้เรามุ่งเน้นไปที่ Stack Data Structures ฉันจะพูดคุยในหัวข้อต่อไปนี้:
- ทำไมต้องมีโครงสร้างข้อมูล
- ประเภทของโครงสร้างข้อมูล
- Stack Data Structure คืออะไร?
- การสร้างโครงสร้างข้อมูลกองซ้อน
- พุชองค์ประกอบลงในกอง
- Pop Elements จาก Stack
- การประยุกต์ใช้โครงสร้างข้อมูลกองซ้อน
ทำไมต้องมีโครงสร้างข้อมูล
เพื่อตอบคำถามนี้คุณจะต้องคิดในระดับใหญ่ ลองนึกดูว่า Google Maps แสดงเส้นทางที่ดีที่สุดให้คุณได้อย่างไรในเวลาเพียงเสี้ยววินาทีซึ่งจะส่งคืนผลการค้นหาในหน่วยไมโครวินาทีอย่างไร ไม่ได้จัดการกับเว็บไซต์เพียง 100 แห่งเท่านั้น แต่เกี่ยวข้องกับเว็บไซต์มากกว่าพันล้านแห่งและยังแสดงผลให้คุณเห็นได้อย่างรวดเร็ว
แม้ว่าอัลกอริทึมที่ใช้จะมีบทบาทสำคัญ แต่โครงสร้างข้อมูลหรือคอนเทนเนอร์ที่ใช้ก็เป็นรากฐานของอัลกอริทึมนั้น ในแอปพลิเคชันใด ๆ การจัดระเบียบและจัดเก็บข้อมูลในลักษณะหรือโครงสร้างที่เหมาะสมที่สุดกับการใช้งานเป็นกุญแจสำคัญในการเข้าถึงและประมวลผลข้อมูล
ประเภทของโครงสร้างข้อมูล
มีโครงสร้างข้อมูลมาตรฐานบางอย่างที่สามารถใช้เพื่อทำงานกับข้อมูลได้อย่างมีประสิทธิภาพ เรายังสามารถปรับแต่งหรือสร้างใหม่ทั้งหมดเพื่อให้เหมาะกับการใช้งานของเรา
Stack Data Structure คืออะไร?
ลองพิจารณาตัวอย่างในชีวิตจริง:
- การขนส่งสินค้า
- แผ่นบนถาด
- กองเหรียญ
- กองลิ้นชัก
- การแบ่งรถไฟในลานรถไฟ
ตัวอย่างทั้งหมดนี้เป็นไปตามก Last-In-First-Out กลยุทธ์. พิจารณาจานบนถาดเมื่อคุณต้องการเลือกจานคุณถูกบังคับให้เลือกจานจากด้านบนในขณะที่เมื่อเก็บจานไว้บนถาดพวกเขาจะต้องอยู่ในลำดับย้อนกลับ ตัวอย่างข้างต้นซึ่งเป็นไปตาม Last-In-First-Out (LIFO) หลักการเรียกว่า ซ้อนกัน .
นอกเหนือจากการดำเนินการเสริมแล้วฉันอาจพูดได้ว่าการดำเนินการหลักที่เป็นไปได้ในสแต็กคือ:
- ดันหรือแทรกองค์ประกอบไปที่ด้านบนสุดของสแต็ก
- ป๊อปหรือลบองค์ประกอบจากด้านบนของสแต็ก
การสร้างโครงสร้างข้อมูลกองซ้อน
class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
- max_size คือจำนวนองค์ประกอบสูงสุดที่คาดหวังในสแต็ก
- องค์ประกอบของสแตกจะถูกเก็บไว้ในรายการไพ ธ อน
- ด้านบนแสดงดัชนีบนสุดของสแต็กซึ่งเริ่มต้น -1 เพื่อทำเครื่องหมายสแต็กว่าง
สถานะเริ่มต้นของ Stack สามารถดูได้ในรูปที่ max_size = 5
วิธีการตั้งค่าเส้นทาง java
พุชองค์ประกอบลงในกอง
ตอนนี้ถ้าคุณต้องการป้อนหรือพุชองค์ประกอบไปที่สแต็กคุณต้องจำไว้ว่า
- ด้านบนจะชี้ดัชนีที่จะแทรกองค์ประกอบ
- และจะไม่มีการแทรกองค์ประกอบเมื่อสแต็กเต็มเช่นเมื่อ max_size = top
แล้วอัลกอริทึมควรเป็นอย่างไร ??
# ส่งคืนขนาดสูงสุดของ stack def get_max_size (self): return self .__ max_size # ส่งคืนค่าบูลไม่ว่าสแต็กจะเต็มหรือไม่ True if full และ False หรือ def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes องค์ประกอบที่ด้านบนของสแต็ก def push (self, data): if (self.is_full ()): print ('stack is already full') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data # คุณสามารถใช้ด้านล่าง __str __ () เพื่อพิมพ์องค์ประกอบของออบเจ็กต์ DS ในขณะที่ดีบัก def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg = 'Stack data (Top to Bottom):' + msg return msgตอนนี้เมื่อคุณดำเนินการต่อไปนี้:
stack1 = สแต็ค (4)
# ผลักดันองค์ประกอบที่จำเป็นทั้งหมด
stack1.push (“ A”)
stack1.push (“ B”)
stack1.push (“ C”)
stack1.push (“ E”)
พิมพ์ (stack1.is_full ())
พิมพ์ (stack1)
เอาท์พุต:
กองเต็มแล้ว
จริง
ข้อมูลกองซ้อน (จากบนลงล่าง): D C B A
Pop Elements จาก Stack
ตอนนี้เมื่อคุณแทรกองค์ประกอบลงในสแต็กแล้วคุณต้องการที่จะแสดงองค์ประกอบเหล่านี้ดังนั้นคุณต้องดูแลสิ่งต่อไปนี้:
- กองซ้อนไม่ว่างเปล่านั่นคือ top! = -1
- เมื่อคุณลบข้อมูลด้านบนต้องชี้ไปที่ด้านบนสุดก่อนหน้าของสแต็ก
แล้วอัลกอริทึมจะเป็นอย่างไร ??
#returns ค่าบูลไม่ว่าสแต็กว่างหรือไม่ True ถ้าว่างและเป็นเท็จมิฉะนั้น def is_empty (self): return self .__ top == - 1 #returns popped value def pop (self): if (self.is_empty ()): print ('nothing to pop, already empty') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 ส่งกลับ # แสดงองค์ประกอบสแต็กทั้งหมดจากบนลงล่างการแสดงผล def (ตัวเอง): สำหรับฉันอยู่ในช่วง (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()ตอนนี้เมื่อพิจารณาถึงสแต็กที่สร้างขึ้นก่อนหน้านี้ให้ลองเปิดองค์ประกอบ
พิมพ์ (stack1.pop ())
พิมพ์ (stack1.pop ())
พิมพ์ (stack1)
พิมพ์ (stack1.pop ())
พิมพ์ (stack1.pop ())
พิมพ์ (stack1.pop ())
เอาท์พุต:
ง
ค
ข้อมูลสแต็ค (จากบนลงล่าง): B A
ข
ถึง
ไม่มีอะไรจะปรากฏว่างเปล่าแล้ว
การประยุกต์ใช้โครงสร้างข้อมูลกองซ้อน
- ตัวอย่างที่ 1:
สแต็กใช้เพื่อใช้อัลกอริธึมการจับคู่วงเล็บสำหรับการประเมินนิพจน์ทางคณิตศาสตร์และในการนำเมธอดไปใช้
คำตอบคือ 5
- ตัวอย่างที่ 2:
คลิปบอร์ดใน Windows ใช้สองสแต็กเพื่อใช้การดำเนินการเลิกทำซ้ำ (ctrl + z, ctrl + y) คุณคงเคยทำงานกับโปรแกรมแก้ไขคำใน Windows เช่น MS-Word, Notepad เป็นต้นนี่คือข้อความที่เขียนด้วย MS-Word สังเกตว่าข้อความเปลี่ยนไปอย่างไรเมื่อคลิก Ctrl-Z และ Ctrl-Y
นี่คือรหัสที่จำลองการเลิกทำซ้ำ อ่านโค้ดและสังเกตวิธีใช้สแต็กในการนำไปใช้งานนี้
#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('สแต็กเต็ม !!') else: self .__ top + = 1 self .__ elements [self .__ top] = data def pop (self): if (self.is_empty ()): print ('The stack is empty! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 return data def display (self): if (self.is_empty ()): print (' The stack is empty ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size # คุณสามารถใช้ __str __ () ด้านล่างเพื่อพิมพ์องค์ประกอบของ ออบเจ็กต์ DS ขณะดีบัก def __str __ (ตัวเอง): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg =' Stack data (จากบนลงล่าง): '+ msg ส่งคืน ms g #function เพื่อใช้ลบหรือลบการดำเนินการ backspace def remove (): คลิปบอร์ดส่วนกลาง, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remove:', clipboard) #function เพื่อใช้การดำเนินการเลิกทำ def undo (): คลิปบอร์ดส่วนกลาง, undo_stack, redo_stack if (undo_stack.is_empty ()): พิมพ์ ('ไม่มีข้อมูลที่จะเลิกทำ') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Undo:', clipboard) #function เพื่อใช้ทำซ้ำการดำเนินการ def redo (): คลิปบอร์ดส่วนกลาง, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('ไม่มีข้อมูล to redo ') else: data = redo_stack.pop () if (data not in clipboard): print (' There is no data to redo ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Redo:', clipboard) clipboard = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Stack (len (clipboard)) redo_stack = Stack (len (คลิปบอร์ด)) ลบ () เลิกทำ () ทำซ้ำ ()เอาท์พุต:
ลบ: ['A', 'B', 'C', 'D', 'E']
เลิกทำ: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]
ทำซ้ำ: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]
การเปลี่ยนแปลงการค้นหาในตัวอย่าง Informatica
ด้วยเหตุนี้เราจึงมาถึงตอนท้ายของบทความ Stack Data Structure ใน Python หากคุณเข้าใจและรันโค้ดด้วยตัวเองสำเร็จคุณจะไม่ใช่มือใหม่ในโครงสร้างข้อมูล Stacks อีกต่อไป
มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของบทความนี้และเราจะติดต่อกลับโดยเร็วที่สุด
หากต้องการรับความรู้เชิงลึกเกี่ยวกับ Python พร้อมกับแอปพลิเคชันต่างๆคุณสามารถลงทะเบียนเพื่อถ่ายทอดสด ด้วยการสนับสนุนตลอด 24 ชั่วโมงทุกวันและการเข้าถึงตลอดชีวิต