โครงสร้างข้อมูล — สแต็ก

ในการเขียนโปรแกรม เราต้องทำงานกับข้อมูลจำนวนมาก ดังนั้นเราจึงจำเป็นต้องจัดเก็บและจัดระเบียบข้อมูลอย่างมีประสิทธิภาพ นี่คือเมื่อโครงสร้างข้อมูลมีประโยชน์ เราสามารถใช้โครงสร้างข้อมูลเพื่อจัดเก็บ จัดระเบียบ ประมวลผล และเรียกใช้ข้อมูล โครงสร้างข้อมูลสามารถแบ่งได้อีก 2 ประเภท ขึ้นอยู่กับวิธีการจัดเรียงข้อมูล

ในบทความนี้ ฉันจะพูดถึงโครงสร้างเชิงเส้น ( Stacks ) เมื่อเทียบกับโครงสร้างที่ไม่ใช่เชิงเส้น แนวคิดเบื้องหลังโครงสร้างเชิงเส้นจะเข้าใจได้ง่ายกว่า ตัวอย่างของโครงสร้างเชิงเส้น เช่น Stack, Queues, Deques และ Lists เราจะอธิบายโครงสร้างข้อมูลเหล่านี้ทีละรายการ โครงสร้างเชิงเส้นเหล่านี้ถือได้ว่ามี 2 ปลาย (ด้านหน้าและด้านหลัง | ซ้ายและขวา | บนและล่าง) โครงสร้างเชิงเส้นบางแบบอนุญาตให้ใส่หรือถอดองค์ประกอบที่ปลายด้านเดียวเท่านั้น ในขณะที่โครงสร้างบางอย่างอนุญาตให้ใส่ที่ปลายด้านใดด้านหนึ่ง

1. กอง

• โดยพื้นฐานแล้ว สแต็กคือชุดขององค์ประกอบที่เรียงลำดับ ซึ่งการแทรกและการลบรายการจะเกิดขึ้นที่ปลายเดียวกัน ปลายนี้เรียกว่า "ด้านบน" นอกจากนี้ปลายตรงข้ามกับด้านบนเรียกว่า "ด้านล่าง"
• นอกจากนี้ รายการใหม่ๆ จะอยู่ด้านบน ในขณะที่รายการเก่าๆ จะอยู่ด้านล่าง ดังนั้น ลำดับการเอาของออกจากสแต็คจะตรงกันข้ามกับลำดับการใส่ของเข้าสแต็ก
• ตอนนี้เรามีความเข้าใจที่ดีเกี่ยวกับพฤติกรรมของสแต็กแล้ว มาดูการดำเนินการที่สำคัญบางอย่างที่เชื่อมโยงกับโครงสร้างข้อมูลสแต็ก
• พุช (องค์ประกอบ) — วิธีการพุชใช้เพื่อแทรกรายการไปที่ด้านบนของสแต็ก
• ป๊อป ()- วิธีป๊อปใช้เพื่อลบรายการด้านบน - รายการส่วนใหญ่ออกจากสแต็ก
• peek () — วิธี Peek ใช้เพื่อดูรายการบนสุดปัจจุบันของสแต็ก
• ขนาด () — ส่งกลับจำนวนรายการที่มีอยู่ในกอง
• is_empty () — วิธีนี้มีประโยชน์ในการตรวจสอบว่าสแต็กว่างเปล่าหรือไม่
• โปรดทราบว่าที่นี่จุดสิ้นสุดของรายการถือเป็นจุดสูงสุดของสแต็ก (ความซับซ้อนของเวลา — O(1))เราสามารถพิจารณาให้จุดเริ่มต้นของรายการอยู่ด้านบนสุดของสแต็ก อย่างไรก็ตาม จะไม่มีประสิทธิภาพมากนัก เนื่องจากความซับซ้อนของเวลาจะเป็นO(n)เมื่อเราพุชหรือป๊อปรายการ
• เมื่อเราถือว่าจุดสิ้นสุดของรายการอยู่ด้านบนสุดของสแต็ก


• ตอนนี้เรารู้วิธีนำสแต็กไปใช้แล้ว ทีนี้มาดูบางสถานการณ์ที่การใช้โครงสร้างข้อมูลสแต็กมีความสำคัญ
• การแปลงระบบตัวเลข
• ก่อนอื่นมาดูกันว่าเราจะแปลงเลขฐานสิบเป็นเลขฐานสองโดยใช้สแต็กได้อย่างไร

• ตอนนี้เรามาขยายอัลกอริทึมด้านบนเพื่อแปลงเลขฐานสิบเป็นระบบตัวเลขระหว่าง 2 ถึง 16


ภาษาการเขียนโปรแกรมเกือบทุกภาษาใช้วงเล็บในไวยากรณ์ ดังนั้นหากเราไม่ใช้วงเล็บอย่างสมดุล ข้อผิดพลาดทางไวยากรณ์อาจเกิดขึ้นได้

• ในขั้นแรกของปัญหานี้ ฉันจะพิจารณาวงเล็บเพียงประเภทเดียว กล่าวคือ () สิ่งที่เราต้องตรวจสอบคือชุดของวงเล็บนั้นสมดุลกันหรือไม่ หากสมดุลเราควรคืนค่าจริงมิฉะนั้นจะเป็นเท็จ
• ( ) — สมดุล | ( ( ) ) — สมดุล | ( ( ( )( ) ) ) — สมดุล
• ( ( ) ไม่สมดุล | ( ) ( ) ( — ไม่สมดุล | ( ( ( ) ) ( ) — ไม่สมดุล

• ( [ ] ) — สมดุล | ( ( ) { } ) — สมดุล | ( ( [ { } [ ] ] ) ) — สมดุล
• ( ( ) ไม่สมดุล | ( ) { } ]— ไม่สมดุล | ( { } [ [ ) — ไม่สมดุล


3. ย้อนกลับสตริงโดยใช้สแต็ก



4. ตรึง | สัญกรณ์ Postfix และคำนำหน้า

ในวิทยาการคอมพิวเตอร์ เราต้องจัดการกับนิพจน์ทางคณิตศาสตร์จำนวนมาก นิพจน์ประกอบด้วยตัวดำเนินการ (+, -, *, / ฯลฯ) ตัวถูกดำเนินการ (A, B, c, d, 1, 2, … ) และสัญลักษณ์ เช่น วงเล็บ

• สัญกรณ์ Infix —ในสัญกรณ์นี้ ตัวดำเนินการจะอยู่ระหว่างตัวถูกดำเนินการ (<ตัวดำเนินการ> <ตัวดำเนินการ> <ตัวดำเนินการ>)
• หากนิพจน์ประกอบด้วยโอเปอเรเตอร์เพียงตัวเดียว (เช่น 2 + 3, 4 * 6) เราสามารถแก้นิพจน์ได้ทันที อย่างไรก็ตาม หากนิพจน์มีโอเปอเรเตอร์มากกว่าหนึ่งตัว เราจะไม่สามารถแก้ไขได้โดยตรงเนื่องจากความไม่ชัดเจนของนิพจน์ พิจารณานิพจน์นี้1 + 4 * 5ถ้าเราทำการบวกก่อน เราจะได้คำตอบเป็น [ ( 1 + 4 ) * 5 ] = 25 และถ้าเราทำการคูณก่อน เราจะได้คำตอบเป็น [1 + (4 * 5 )] = 21 อย่างที่คุณเห็น มีความกำกวมในสัญกรณ์นี้ ดังนั้นเพื่อแก้ปัญหานี้ เราจึงใช้สิ่งที่เรียกว่า"ลำดับความสำคัญของตัวดำเนินการ" ตามลำดับความสำคัญของตัวดำเนินการควรทำการคูณก่อนการบวก ดังนั้นคำตอบที่ถูกต้องควรเป็น 21 ไม่ใช่ 25
• โดยพื้นฐานแล้ว ในการแก้นิพจน์ที่เขียนด้วยเครื่องหมาย infix เราต้องปฏิบัติตามกฎชุดหนึ่ง รวมทั้งต้องใส่วงเล็บด้วย ดังนั้นสัญกรณ์นี้อาจใช้หน่วยความจำมากขึ้นในขณะที่แก้ไข ดังนั้น เพื่อเอาชนะความท้าทายเหล่านี้ นักวิทยาศาสตร์จึงได้คิดสัญลักษณ์อีกสองแบบ ได้แก่ คำนำหน้าและคำนำหลัง
• ในรูปแบบคำนำหน้า ตัวดำเนินการจะถูกวางไว้ก่อนตัวถูกดำเนินการ(<ตัวดำเนินการ><ตัวดำเนินการ> <ตัวดำเนินการ>)ในขณะที่ตัวดำเนินการจะถูกวางไว้หลังตัวถูกดำเนินการ (<ตัวดำเนินการ> <ตัวดำเนินการ><ตัวดำเนินการ>)
• เมื่อเทียบกับสัญกรณ์ infix แล้ว อีกสองสัญกรณ์นั้นค่อนข้างยากสำหรับมนุษย์ที่จะอ่านและทำความเข้าใจ อย่างไรก็ตาม เนื่องจากสัญกรณ์ทั้งสองนี้ไม่มีสัญลักษณ์เพิ่มเติม เช่น วงเล็บเหลี่ยม และไม่มีความกำกวมใดๆ นิพจน์ที่เขียนใน 2 รูปแบบนี้จึงสามารถอ่านได้ง่ายด้วยคอมพิวเตอร์


• การประเมินนิพจน์ postfix :เมื่อเราต้องประเมินนิพจน์ postfix เราควรเริ่มสแกนจากด้านซ้ายจนกว่าจะพบตัวดำเนินการ เมื่อเราพบตัวดำเนินการแล้ว เราต้องทำการดำเนินการเกี่ยวกับพีชคณิตที่เกี่ยวข้องกับตัวถูกดำเนินการ 2 ตัวแรกทางซ้ายของตัวดำเนินการ

• ก่อนอื่นต้องลบช่องว่างทั้งหมดในการป้อนข้อมูลของเรา เราจึงต้องใช้วิธีแบ่ง จากนั้นเราต้องสแกนการแสดงออกของเราจากซ้ายไปขวา ถ้าเจอเลขต้องดันเข้ากอง หากเราเจอโอเปอเรเตอร์ เราจะต้องแสดงรายการบนสุด 2 รายการในสแต็กของเรา จากนั้นเราต้องเรียกใช้ฟังก์ชันตัวช่วยของเราเพื่อดำเนินการทางคณิตศาสตร์ หลังจากนั้นเราจะผลักดันผลลัพธ์ลงในสแต็ก เมื่อเราสแกนเสร็จแล้ว เราจะส่งคืนสิ่งที่เหลืออยู่ในสแต็กของเรา ซึ่งเป็นคำตอบสำหรับนิพจน์ postfix ที่ประเมินแล้ว


• มาดูกันว่าเราจะแปลงนิพจน์ในรูปแบบ infix เป็น postfix โดยใช้ Python ได้อย่างไร