สแต็กคืออะไรนอกจากโครงสร้างข้อมูลเชิงเส้นที่การแทรกและการลบเกิดขึ้นที่ปลายด้านเดียวเท่านั้น การดำเนินการแทรกมีชื่อพิเศษที่เรียกว่า PUSH และการดำเนินการลบยังมีชื่อพิเศษที่เรียกว่า POP PUSH และ POP เป็นการดำเนินการพื้นฐานสองอย่างที่สามารถทำได้เฉพาะในสแต็ก เป็นกลุ่มของตำแหน่งหน่วยความจำและตำแหน่งหน่วยความจำเกี่ยวข้องกับหน่วยความจำอ่านหรือเขียนหน่วยความจำ ใช้สำหรับจัดเก็บข้อมูลไบนารีในระหว่างการทำงานของโปรแกรมเมื่อเราเรียกใช้โปรแกรมใด ๆ เนื้อหาของโปรแกรมนั้นจะถูกเก็บไว้ในสแตก มันเป็นไปตาม เข้าก่อนออกครั้งสุดท้าย (LIFO) และใช้สำหรับจัดเก็บและเรียกข้อมูลเท่านั้น แต่ไม่ได้ใช้สำหรับจัดเก็บข้อมูล คำอธิบายสั้น ๆ ของตัวชี้สแต็ก / สแต็กจะกล่าวถึงด้านล่าง
Stack / Stack Pointer คืออะไร?
คำจำกัดความ: สแต็กเป็นอุปกรณ์จัดเก็บข้อมูลที่ใช้สำหรับจัดเก็บข้อมูลหรือข้อมูลในลักษณะของ LIFO (Last In First Out) เมื่อใดก็ตามที่เราป้อนข้อมูลในรูปแบบ LIFO องค์ประกอบที่ต้องถูกลบออกก่อนคือองค์ประกอบแทรกสุดท้ายดังนั้นองค์ประกอบที่แทรกสุดท้ายจะถูกนำออกก่อน เป็นหน่วยความจำภายในการลงทะเบียนแอดเดรสที่เรียกว่า stack pointer (SP) ตัวชี้สแต็กจะระบุองค์ประกอบบนสุดในสแต็กเสมอซึ่งหมายความว่าตำแหน่งใดที่ต้องแทรกข้อมูล
ประเภทของกอง
สแต็กมีสองประเภท ได้แก่ register stack และ memory stack
ลงทะเบียน Stack
สแต็กรีจิสเตอร์ยังเป็นอุปกรณ์หน่วยความจำที่มีอยู่ในหน่วยความจำ แต่จะจัดการข้อมูลเพียงเล็กน้อยเท่านั้น ความลึกของสแต็กจะถูก จำกัด ในสแต็กรีจิสเตอร์เสมอเนื่องจากขนาดของสแต็กรีจิสเตอร์เล็กมากเมื่อเทียบกับหน่วยความจำ
กดการดำเนินการใน Register Stack
ขั้นตอนที่ 1: ตัวชี้สแต็กจะเพิ่มขึ้นทีละ 1
SP ← SP + 1
ขั้นตอนที่ 2: ป้อนข้อมูลลงในสแตก
1,000 [SP] ← CT
DR อยู่ที่ไหนลงทะเบียนข้อมูล
ขั้นที่ 3: ตรวจสอบว่ากองเต็มหรือไม่
ถ้า (sp = 0) แล้ว (เต็ม← 1)
ขั้นตอนที่ 4: ทำเครื่องหมายว่าไม่ว่างเปล่า
ว่าง← 0
Pop Operation ใน Register Stack
ขั้นตอนที่ 1: อ่านข้อมูลจากสแตก
DR ← M [SP]
ขั้นตอนที่ 2: จุดสแต็กที่ลดลง
SP ← SP-1
ขั้นที่ 3: ตรวจสอบว่าสแตกว่างหรือไม่
ถ้า sp = 0 แล้วว่างเปล่า← 1
การจัดเรียงสแต็กของสแต็กรีจิสเตอร์ 64 บิตแสดงอยู่ในรูปด้านล่าง
ลงทะเบียน Stack Organization
หน่วยความจำ
ในสแตกหน่วยความจำความลึกของสแต็กมีความยืดหยุ่น มันใช้ข้อมูลหน่วยความจำจำนวนมากในขณะที่ในสแต็ก register จะมีการจัดเก็บคำหน่วยความจำจำนวน จำกัด เท่านั้น
กดการทำงานใน Memory Stack
ขั้นตอนที่ 1: SP ← SP-1
ขั้นตอนที่ 2: 1,000 [SP] ← CT
ป๊อปการทำงานใน Memory Stack
ขั้นตอนที่ 1: DR ← M [SP]
ขั้นตอนที่ 2: SP ← SP-1
เปรียบเทียบกับหน่วยรีจิสเตอร์หน่วยความจำจะเก็บข้อมูลจำนวนมาก รูปกองหน่วยความจำแสดงในรูปด้านล่าง
หน่วยความจำ
หน่วยความจำทั้งหมดแบ่งออกเป็นสามส่วนหน่วยความจำแรกมีโปรแกรม (ไม่มีอะไรนอกจากคำสั่ง) ส่วนที่สองคือข้อมูล (ตัวถูกดำเนินการ) และส่วนที่สามคือสแต็ก คำแนะนำของโปรแกรมจะเก็บไว้ในตัวนับโปรแกรม (PC) เสมอการลงทะเบียนข้อมูลจะถูกระบุโดยการลงทะเบียนที่อยู่ (AR) ที่อยู่ 3000 ถึง 4001 ที่ใช้สำหรับสแต็กและรายการหรือองค์ประกอบแรกจะถูกเก็บไว้ที่ 4001
Stack / Stack Pointer ในไมโครโปรเซสเซอร์ 8085
มุมมองโปรแกรมเมอร์ 8085 ไมโครโปรเซสเซอร์ ประกอบด้วยรีจิสเตอร์วัตถุประสงค์ทั่วไปและ การลงทะเบียนวัตถุประสงค์พิเศษ . รีจิสเตอร์เอนกประสงค์คือ A, B, C, D, E, H, L และรีจิสเตอร์วัตถุประสงค์พิเศษคือ SP (Stack Pointer) และ PC (Program Counter) มุมมองโปรแกรมเมอร์ของไมโครโปรเซสเซอร์ 8085 แสดงในรูปด้านล่าง
มุมมองโปรแกรมเมอร์ของ 8085
ตัวชี้สแต็กคือรีจิสเตอร์ 16 บิตมีที่อยู่หน่วยความจำสมมติว่าเนื้อหาของตัวชี้สแต็ก (SP) เป็น FC78H จากนั้นไมโครโปรเซสเซอร์ 8085 จะตีความ ตำแหน่งหน่วยความจำมีข้อมูลที่เป็นประโยชน์ตั้งแต่ FC78H ถึง FFFH และจาก FC77H ถึง 0000H ตำแหน่งหน่วยความจำไม่มีข้อมูลที่เป็นประโยชน์ การตีความของตัวชี้สแต็กจะแสดงในรูปด้านล่าง
การตีความตัวชี้สแต็ก
การทำงานพื้นฐานของ Stack / Stack Pointer
มีการดำเนินการสองอย่างของสแต็ก ได้แก่ การดำเนินการ PUSH และการดำเนินการ POP
การดำเนินการผลักดัน
PUSH หมายถึงการผลักหรือใส่องค์ประกอบลงในสแต็ก การดำเนินการ PUSH จะเพิ่มตัวชี้สแต็กเสมอและการดำเนินการ POP จะลดตัวชี้สแต็กเสมอ ในกรณีของการดำเนินการผลักดันเราต้องตรวจสอบว่ามีพื้นที่ว่างหรือไม่ หากมีพื้นที่ว่างเราสามารถไปที่การดำเนินการพุชได้หากไม่มีพื้นที่ว่างจะเกิดข้อความแสดงข้อผิดพลาดว่าล้น การล้นจะต้องตรวจสอบในกรณีของการผลักดันตามลำดับ การทำงานพื้นฐานของการกดและป๊อปแสดงดังรูปด้านล่าง
การทำงานพื้นฐานของ PUSH และ POP
รูป (a) คือสแต็ก หากคุณต้องการดันองค์ประกอบที่เป็นตัวแทรกองค์ประกอบลงในสแต็กคุณต้องกด (s, a) โดยที่ 's' ไม่ใช่อะไรเลยนอกจากสแต็ก ในสแต็กเรากำลังวางองค์ประกอบ 'a' และการดำเนินการนี้จะแสดงในรูป (b) ดูรูป (3) สมมติว่าสแต็กมีองค์ประกอบสามอย่าง a, b, c และสแต็กเต็มไปด้วยองค์ประกอบ
หากคุณต้องการแทรกองค์ประกอบที่สี่-‘d ’โดยใช้ push (s, d) แต่ไม่มีช่องว่างให้แทรกองค์ประกอบแสดงว่าสแต็กล้น คำศัพท์โอเวอร์โฟลว์ใช้เมื่อสแต็กเต็มและอัลกอริทึมของการดำเนินการพุชแสดงไว้ด้านล่าง
push (stack [], top, max stack, item)
ถ้า (top == maxstack-1)
{
พิมพ์ 'ล้น'
}
อื่น
{
top = top + 1
stack [top] = item
}
จบ
การทำงานของ POP
POP หมายถึงการลบองค์ประกอบที่ด้านบนสุดของสแต็ก ในกรณีของการทำงานแบบ pop เราต้องตรวจสอบว่าในตอนแรกสแตกว่างหรือไม่ หากสแต็กว่างเปล่าในตอนแรกจะมีสถานการณ์น้อยลง สมมติว่าสแต็กว่างเปล่า แต่คุณยังต้องการป๊อปองค์ประกอบในสแต็ก แต่ไม่มีองค์ประกอบในสแต็กจากนั้นจะนำไปสู่สแต็กอันเดอร์โฟลว์
ขั้นต่ำจะต้องตรวจสอบในกรณีของการดำเนินการป๊อปตามลำดับ ในการดำเนินการป๊อปไม่ว่าองค์ประกอบบนสุดใด ๆ ที่มีอยู่ในสแต็กที่ควรจะป๊อปหรือลบออกดังนั้นไม่จำเป็นต้องพูดถึงว่าองค์ประกอบใดจะถูกดึงออกโดยค่าเริ่มต้นองค์ประกอบที่อยู่บนสุดจะถูกดึง อัลกอริทึมของการทำงานป๊อปแสดงไว้ด้านล่าง
ป๊อป (stack [], ด้านบน, รายการ)
ถ้า (top == - 1)
{
พิมพ์ 'underflow'
}
อื่น
{
item = stack [top]
top = top-1
}
ตัวอย่าง
องค์ประกอบจะถูกแทรกตามลำดับเป็น A, B, C, D, E ซึ่งแสดงถึงสแต็กของห้าองค์ประกอบ ในรูป (a) เราต้องการดันองค์ประกอบ 'A' บนสแต็กจากนั้นด้านบนจะกลายเป็นศูนย์ (top = 0) ในทำนองเดียวกัน top = 1 เมื่อผลักองค์ประกอบ 'B' top = 2 เมื่อองค์ประกอบ 'C' ถูกผลักด้านบน = 3 เมื่อผลักองค์ประกอบ 'D' และด้านบน = 4 เมื่อผลักองค์ประกอบ 'E'
ดังนั้นองค์ประกอบใดก็ตามที่ฉันถ่ายไว้ในสแต็กตอนนี้สแต็กเต็มแล้ว หากคุณต้องการพุชองค์ประกอบอื่นจะไม่มีตำแหน่งในสแต็กดังนั้นจึงบ่งบอกถึงการล้น ตอนนี้สแต็กเต็มแล้วถ้าคุณต้องการป๊อปอัพองค์ประกอบ 'E' จะต้องถูกลบออกก่อน การดำเนินการกดจะแสดงในรูปด้านล่าง
ผลักดันการทำงาน
เราต้องใช้การดำเนินการ pop เพื่อลบองค์ประกอบในสแตก ดังนั้นเพียงพูดถึง pop () อย่าเขียนอาร์กิวเมนต์ในป๊อปเพราะโดยค่าเริ่มต้นจะลบองค์ประกอบด้านบน องค์ประกอบ 'E' แรกจะถูกลบองค์ประกอบถัดไป 'D' … .. ’A’ เมื่อองค์ประกอบด้านบนถูกลบค่าสูงสุดจะลดลง เมื่อ top = -1 สแต็กจะบ่งบอกถึงขั้นต่ำ การทำงานของป๊อปจะแสดงในรูปด้านล่าง
การทำงานของ POP
นี่คือคำอธิบายเกี่ยวกับวิธีการแทรกและลบองค์ประกอบในสแต็กโดยใช้การทำงานแบบพุชและป๊อป
การใช้งาน
แอปพลิเคชันของตัวชี้สแต็ก / สแต็กคือ
- การกลับรายการสตริง
- วงเล็บที่สมดุล
- UNDO / FINGER
- สแต็กระบบสำหรับบันทึกการเปิดใช้งาน
- Infix คำนำหน้า postfix นิพจน์
คำถามที่พบบ่อย
1). ตัวชี้สแต็กในแขนคืออะไร?
สแต็กพอยน์เตอร์รีจิสเตอร์ (R13) ใช้เป็นตัวชี้ไปยังสแต็กที่ใช้งานอยู่ใน ARM
2). เหตุใดตัวชี้สแต็กจึงเป็น 16 บิต
ตัวชี้สแต็ก (SP) และตัวนับโปรแกรม (PC) ใช้เพื่อจัดเก็บตำแหน่งก่อนหน้าและที่อยู่ตำแหน่งหน่วยความจำคือ 16 บิตดังนั้นตัวชี้สแต็ก (SP) จึงเป็น 16 บิตเช่นกัน
3). อะไรคือบทบาทของตัวชี้สแต็ก?
บทบาทของตัวชี้สแต็ก (SP) คือการระบุส่วนบนสุดขององค์ประกอบในสแตก
4). สแต็กใดที่ใช้ใน 8085?
สแต็กที่ใช้ใน 8085 คือ Last In First Out (LIFO)
5). ตัวชี้สแต็กเป็นรีจิสเตอร์หรือไม่?
ใช่ตัวชี้สแต็ก (SP) คือการลงทะเบียนที่อยู่ซึ่งจะระบุส่วนบนสุดขององค์ประกอบในสแต็กเสมอ
