ในบล็อกก่อนหน้านี้ฉันแนะนำรายการต่อไปนี้ รายการเป็นโครงสร้างที่ง่ายที่สุด แต่ถ้าคุณต้องการจัดการกับโครงสร้างที่ซับซ้อนมากขึ้นรายการดูง่ายเกินไปดังนั้นเราจึงต้องการโครงสร้างข้อมูลบางอย่างคล้ายกับรายการ แต่ซับซ้อนกว่า - สแต็ก สแต็กเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพเนื่องจากข้อมูลสามารถเพิ่มหรือลบได้ที่ด้านบนของสแต็กเท่านั้นดังนั้นการดำเนินการนี้จึงรวดเร็วและง่ายต่อการใช้งาน
1: การดำเนินการบนสแต็ก
สแต็กเป็นรายการพิเศษ องค์ประกอบในสแต็กสามารถเข้าถึงได้ผ่านปลายด้านหนึ่งของรายการเท่านั้นและจุดสิ้นสุดนี้เป็นด้านบนของสแต็ก ตัวอย่างเช่นเมื่อล้างจานในร้านอาหารคุณสามารถล้างจานบนสุดก่อน หลังจากล้างจานคุณสามารถหอยทากด้านบนของสแต็คอาหารเท่านั้น สแต็กเรียกว่าโครงสร้างข้อมูล "สายแรก-ออก" (LIFO)
เนื่องจากสแต็กมีลักษณะของการย้อนกลับเป็นครั้งแรกจึงไม่มีองค์ประกอบที่ไม่สามารถเข้าถึงได้ที่ด้านบนสุดของสแต็ก เพื่อให้ได้องค์ประกอบที่มีสแต็กต่ำองค์ประกอบด้านบนจะต้องถูกลบออกก่อน การดำเนินการหลักสองประการที่เราสามารถทำได้กับสแต็กคือการผลักองค์ประกอบลงบนสแต็กและเปิดองค์ประกอบลงบนสแต็ก เมื่อเข้าสู่สแต็กเราสามารถใช้วิธีการ push () วิธีการและเมื่อเราใส่เราสามารถใช้วิธี POP () แม้ว่าวิธี POP () สามารถเข้าถึงองค์ประกอบที่ด้านบนของสแต็กหลังจากเรียกวิธีการ แต่องค์ประกอบที่ด้านบนของสแต็กจะถูกลบอย่างถาวรจากสแต็ก อีกวิธีหนึ่งที่เราใช้คือ peek () ซึ่งส่งคืนเฉพาะองค์ประกอบด้านบนของสแต็กโดยไม่ต้องลบ
ไดอะแกรมคอลัมน์จริงของรายการสแต็กและทางออกสแต็กมีดังนี้:
push (), pop () และ peek () เป็นสามวิธีหลักของสแต็ก แต่สแต็กมีวิธีการและคุณสมบัติอื่น ๆ ดังนี้:
Clear (): ล้างองค์ประกอบทั้งหมดในสแต็ก
ความยาว (): บันทึกจำนวนองค์ประกอบในสแต็ก
สอง: การดำเนินการของสแต็กมีดังนี้:
เราสามารถเริ่มต้นด้วยการใช้วิธีสแต็กคลาสก่อน ดังนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่นสแต็ค () {
this.datastore = [];
this.top = 0;
-
ดังที่กล่าวมาข้างต้น: Datastore บันทึกองค์ประกอบทั้งหมดในสแต็ก ตัวแปรด้านบนบันทึกตำแหน่งที่ด้านบนของสแต็กและเริ่มต้นเป็น 0 หมายความว่าตำแหน่งเริ่มต้นของอาร์เรย์ที่เกี่ยวข้องที่ด้านบนของสแต็กคือ 0 ถ้าองค์ประกอบใด ๆ ถูกผลักเข้าไปในสแต็ก ค่าของตัวแปรนี้จะเปลี่ยนไปตามลำดับ
นอกจากนี้เรายังมีวิธีการต่อไปนี้: push (), pop (), peek (), clear (), ความยาว ();
1. วิธีการกด (); เมื่อผลักองค์ประกอบใหม่ลงในสแต็กจะต้องบันทึกไว้ในอาร์เรย์ที่สอดคล้องกับตัวแปรด้านบนและจากนั้นค่าสูงสุดจะเพิ่มขึ้น 1 เพื่อให้ชี้ไปที่ตำแหน่งถัดไปในอาร์เรย์ รหัสต่อไปนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชันกด (องค์ประกอบ) {
this.datastore [this.top ++] = องค์ประกอบ;
-
2. วิธี POP () ตรงข้ามกับวิธีการกด () - มันส่งคืนองค์ประกอบด้านบนและหักค่าสูงสุดโดย 1 รหัสต่อไปนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่นป๊อป () {
ส่งคืนสิ่งนี้ datastore [-this.top];
-
3. วิธี PEEK () ส่งคืนองค์ประกอบที่ตำแหน่ง TOP-1 ของอาร์เรย์นั่นคือองค์ประกอบ TOP-1 ของสแต็ก;
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่น peek () {
ส่งคืนสิ่งนี้ datastore [this.top - 1];
-
4. วิธีความยาว () บางครั้งเราจำเป็นต้องรู้ว่ามีองค์ประกอบกี่อย่างในสแต็ก เราสามารถส่งคืนจำนวนองค์ประกอบในสแต็กโดยส่งคืนค่าตัวแปรสูงสุดดังที่แสดงในรหัสต่อไปนี้:
การคัดลอกรหัสมีดังนี้:
ความยาวฟังก์ชั่น () {
คืนสิ่งนี้ท็อป;
-
5. ชัดเจน (); บางครั้งเราต้องการล้างสแต็กและเราตั้งค่าสูงสุดของตัวแปรเป็น 0; รหัสต่อไปนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่นชัดเจน () {
this.top = 0;
-
รหัสทั้งหมดด้านล่าง:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่นสแต็ค () {
this.datastore = [];
this.top = 0;
-
stack.prototype = {
// กดองค์ประกอบใหม่ลงในสแต็ก
กด: ฟังก์ชั่น (องค์ประกอบ) {
this.datastore [this.top ++] = องค์ประกอบ;
-
// เข้าถึงองค์ประกอบด้านบนของสแต็กองค์ประกอบด้านบนของสแต็กจะถูกลบอย่างถาวร
ป๊อป: ฟังก์ชั่น () {
ส่งคืนสิ่งนี้ datastore [-this.top];
-
// ส่งคืนองค์ประกอบที่ตำแหน่ง TOP-1 ในอาร์เรย์นั่นคือองค์ประกอบด้านบนของสแต็ก
peek: function () {
ส่งคืนสิ่งนี้ datastore [this.top - 1];
-
// มีกี่องค์ประกอบที่เก็บไว้ในสแต็ก
ความยาว: ฟังก์ชัน () {
คืนสิ่งนี้ท็อป;
-
// ล้างสแต็ก
ล้าง: ฟังก์ชั่น () {
this.top = 0;
-
-
ตัวอย่างของการสาธิตมีดังนี้:
var stack = new Stack ();
stack.push ("a");
stack.push ("B");
stack.push ("C");
console.log (stack.length ()); // 3
console.log (stack.peek ()); // C
var popped = stack.pop ();
console.log (popped); // C
console.log (stack.peek ()); // B
stack.push ("D");
console.log (stack.peek ()); // D
stack.clear ();
console.log (stack.length ()); // 0
console.log (stack.peek ()); // ไม่ได้กำหนด
ด้านล่างเราสามารถใช้คำจำกัดความแบบเรียกซ้ำของฟังก์ชั่นแฟคทอเรียล ตัวอย่างเช่น 5! แฟคทอเรียล 5! = 5 * 4 * 3 * 2 * 1;
รหัสต่อไปนี้:
การคัดลอกรหัสมีดังนี้:
ฟังก์ชั่นข้อเท็จจริง (n) {
var s = ใหม่สแต็ก ();
ในขณะที่ (n> 1) {
s.push (n--);
-
ผลิตภัณฑ์ var = 1;
ในขณะที่ (s.length ()> 0) {
ผลิตภัณฑ์ *= s.pop ();
-
ผลิตภัณฑ์ส่งคืน;
-
console.log (ข้อเท็จจริง (5));
รหัสข้างต้นหมายถึง: ก่อนหมายเลข 5 ลงในฟังก์ชั่นให้ใช้การวนซ้ำในขณะที่และก่อนที่จะลดลง 1 ในแต่ละครั้งกด () ของฟังก์ชั่นที่คุณใช้กับสแต็กจนกว่าตัวแปร n จะน้อยกว่า 1 จากนั้นกำหนดผลิตภัณฑ์ตัวแปร ตรวจสอบว่ามันมีค่ามากกว่า 0 โดยวิธีความยาว () ของสแต็กและทุกครั้งที่มีการดำเนินการวิธีการ* = s.pop () วิธีการ POP () จะส่งคืนองค์ประกอบด้านบนของสแต็กและลบองค์ประกอบออกจากสแต็ก ดังนั้นทุกครั้งที่คุณดำเนินการลบองค์ประกอบจนกว่า s.length () <= 0 ดังนั้นผลิตภัณฑ์ = 5*4*3*2*1 เป็นต้น