Java สแต็ค

Stack ใน Java มักหมายถึงคลาสจาก Collection Framework ที่ใช้อินเทอร์เฟซรายการ ทำงานบนหลักการของโครงสร้างข้อมูลแบบ Stack ซึ่งใช้ในการจัดระเบียบหน่วยความจำประเภทใดประเภทหนึ่ง นอกจากนี้ยังอาจเป็นส่วนหนึ่งของหน่วยความจำในการเก็บข้อมูล ในบทความนี้เราจะให้ความสนใจกับคลาส Stackเป็นอันดับแรกพิจารณาวิธีการและยกตัวอย่าง แต่เราจะพูดถึงโครงสร้างข้อมูลเช่นStackและสิ่งที่ใช้สำหรับ

โครงสร้างข้อมูลแบบสแต็กคืออะไร

ก่อนอื่น เรามาดูกันก่อนว่าโครงสร้างข้อมูลสแต็กคืออะไร เป็นโครงสร้างข้อมูลเชิงเส้นที่อิงตามหลักการ Last-in-First-out (LIFO) เป็นการต่อต้านคิว ลองนึกภาพสำรับไพ่หรือกองหนังสือในกล่อง หนังสือที่คุณใส่ในกองก่อนจะอยู่ด้านล่าง และเล่มแรกที่เราจะนำออกจากกล่องคือหนังสือที่อยู่ด้านบนสุด นั่นคือหนังสือที่เข้าไปในกล่องเป็นคนสุดท้าย นี่คือภาพ gif เพื่อแสดงให้เห็นถึงหลักการนี้ Java สแต็ค - 1

เกิดอะไรขึ้นที่นี่? เรามีขวดที่สามารถตีได้ครั้งละหนึ่งลูกเท่านั้น ลูกแรกในขวดเป็นลูกบอลสีส้ม ตามด้วยสีม่วง และสุดท้ายเป็นสีเขียว (ขออภัยท่านที่ทราบชื่อสีเหล่านี้ถูกต้องกว่า) อย่างไรก็ตาม ในการสกัดลูกบอลสีส้มออกจากกองขวดของเรา เราต้องแยกลูกบอลที่ไปถึงก่อน (สีเขียว) ก่อน จากนั้นจึงแยกลูกบอลที่อยู่สุดท้าย (แต่ตอนสกัดนั้นเป็นลูกสุดท้าย หนึ่ง). โครงสร้างข้อมูลแบบสแตกใน Java หรือที่อื่น ๆ ในการเขียนโปรแกรมมีการดำเนินการที่สำคัญที่สุดสองอย่างคือpushและpop การดำเนินการพุชจะแทรกองค์ประกอบลงในสแต็กและการดำเนินการป๊อปจะลบองค์ประกอบออกจากด้านบนของสแต็ก

โครงสร้างข้อมูลแบบ Stack มีไว้เพื่ออะไร?

การใช้สแต็กที่สำคัญที่สุดอย่างหนึ่งคือการจัดระเบียบการโทรรูทีนย่อย จุดเรียกบนสแต็กเก็บที่อยู่ส่งคืนจากรูทีนย่อยหลังจากสิ้นสุด (และอาจส่งผ่านพารามิเตอร์) ด้วยการเรียกรูทีนย่อยที่ซ้อนกัน (รวมถึงการเรียกซ้ำ) ที่อยู่ผู้ส่งใหม่จะถูกเพิ่มลงในสแต็ก ด้วยการดำเนินการส่งคืนแต่ละครั้งจากรูทีนย่อย (การส่งคืน) ที่อยู่ผู้ส่งคืนจะถูกลบออกจากสแต็กและการควบคุมจะถูกถ่ายโอนไปยังรูทีนย่อย แอ็พพลิเคชันนี้มีความสำคัญต่อการเขียนโปรแกรมมาก ซึ่งในโปรเซสเซอร์ส่วนใหญ่นั้น return stack จะถูกนำไปใช้ในฮาร์ดแวร์ในชุดคำสั่ง อย่างไรก็ตาม ในกรณีอื่นๆ สแต็กจะต้องมีการสร้างแบบจำลองบนโครงสร้างข้อมูลทั่วไปมากขึ้น

Java Stack Class of Collection Framework

ใน Java Stack Class เป็นคลาสจากเฟรมเวิร์ก Collection ที่ใช้ List interface และขยายคลาส Vector นอกจากนี้ยังใช้อินเทอร์เฟซ Collection, Iterable, Cloneable, Serializable ดังที่คุณอาจเดาแล้วว่าคลาสนี้เป็นตัวแทนของออบเจกต์ LIFO นี่คือการเรียกตัวสร้างของ คลาส Stackนั่นคือการสร้างวัตถุของคลาสนี้


Stack<E> stack = new Stack<E>();

โดยที่Eคือประเภทของวัตถุ

วิธี Java Stack

คลาสนี้มีตัวสร้างเริ่มต้นเพียงตัวเดียวและเมธอดทั้งหมดของคลาสVector นอกจากนี้Stackยังมี 5 วิธีของตัวเอง:

บูลีนว่าง ()วิธีการตรวจสอบว่าสแต็คว่างเปล่าหรือไม่ คืนค่าจริงหากสแต็กว่างเปล่าคืนค่าเท็จหากไม่
Object peek()เมธอดส่งกลับองค์ประกอบที่อยู่ด้านบนสุดของสแต็ก
Object pop()วิธีการส่งกลับองค์ประกอบที่อยู่ด้านบนของสแต็คและลบออก
Object push(Object element)วิธีการเพิ่มองค์ประกอบที่ระบุไปที่ด้านบนของสแต็ก
การค้นหา int (องค์ประกอบวัตถุ)วิธีการค้นหาสแต็กสำหรับองค์ประกอบที่ระบุ หากพบองค์ประกอบที่ต้องการ ระบบจะส่งกลับ "ระยะทาง" จากด้านบน (หมายเลขซีเรียล) หากไม่พบองค์ประกอบ -1 จะถูกส่งกลับ

ตัวอย่างรหัสสแต็ก

มาสร้างตัวอย่างโปรแกรมที่ใช้งานได้ดังภาพ gif ด้านบน เราจะวาง "ลูกบอล" สามลูก สีส้ม สีม่วง และสีเขียว ไว้บนกอง ตรวจสอบสแต็คสำหรับความว่างเปล่า จากนั้นเราจะแยกลูกบอลออกจากกองจนกว่ากองจะว่างเปล่า


import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

นี่คือผลลัพธ์ของโปรแกรมนี้:

สแต็กของฉันว่างเปล่าหรือไม่ องค์ประกอบที่แท้จริงในกอง: [ลูกบอลสีส้ม, ลูกบอลสีม่วง, ลูกบอลสีเขียว] กองของฉันว่างเปล่าหรือไม่? องค์ประกอบเท็จในกอง: [ลูกบอลสีส้ม, ลูกบอลสีม่วง] กองของฉันว่างเปล่าหรือไม่? องค์ประกอบเท็จในกอง: [ลูกบอลสีส้ม] กองของฉันว่างเปล่าหรือไม่ องค์ประกอบที่เป็นเท็จในสแต็ก: [] สแต็กของฉันว่างเปล่าหรือไม่ จริง

เนื่องจากStackสืบทอดมาจากVector Class และนำอินเทอร์เฟซList ไปใช้ Stackนอกจากการดำเนินการแบบพุชและป๊อปแบบคลาสสิกสำหรับโครงสร้างข้อมูลนี้สำหรับการเพิ่มและการแยกองค์ประกอบแล้ว ยังมีมาตรฐานสำหรับการดำเนินการ โครงสร้างรายการ add()และremove() ในตัวอย่างของเรา การเพิ่มองค์ประกอบสามารถทำได้ด้วยวิธีเดียวกันโดยใช้เมธอดadd () อย่างไรก็ตาม คุณสามารถแยกโดยใช้remove()เฉพาะกับองค์ประกอบที่ระบุ ซึ่งไม่สมเหตุสมผลสำหรับโครงสร้างข้อมูลสแต็ก


import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }

แน่นอนว่าผลลัพธ์ของการทำงานของโปรแกรมจะเหมือนกันทุกประการ

แล้วการใช้งาน Stack ของคุณเองล่ะ?

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

พุช — วิธีการที่จะเพิ่มองค์ประกอบ (ในตำแหน่งบนสุด)
ป๊อป — วิธีการที่จะให้ลบองค์ประกอบ (จากตำแหน่งบนสุด)
readTop — วิธีที่จะคืนค่าขององค์ประกอบที่อยู่ในตำแหน่งบนสุด
sEmpty — วิธีที่จะตรวจสอบความว่างเปล่าของสแต็ก
isFull — วิธีที่จะตรวจสอบว่า array ที่เราเก็บ stack นั้นไม่เต็มหรือไม่


import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;
      
   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());
      
       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}

ตอนนี้ลองใช้ตัวอย่างกับลูกบอลสามลูกตามสแต็คของเรา:


public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}

ผลลัพธ์อยู่ที่นี่:

สแต็กของฉันว่างเปล่าหรือไม่ จริง [Orange Ball, Violet Ball, Green Ball] กองของฉันว่างเปล่าหรือไม่? false การลบลูกบอลสีเขียว สแต็กของฉันว่างเปล่าหรือไม่ false การลบ Violet Ball สแต็กของฉันว่างเปล่าหรือไม่ เท็จ การลบ Orange Ball สแต็กของฉันว่างเปล่าหรือไม่ จริง

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

เราควรใช้ Java Stack หรือไม่

ในความเป็นจริง Java Stackเช่นเดียวกับ พาเรนต์ Vectorเป็นคลาสดั้งเดิม โดย ปกติจะใช้คลาสArrayListแทน ArrayListไม่ซิงโครไนซ์ในขณะที่Vectorถูกซิงโครไนซ์ นั่นหมายความว่าVectorสามารถเข้าถึงโค้ดได้ครั้งละหนึ่งเธรดเท่านั้น ในขณะที่ArrayListสามารถทำงานกับหลายเธรดได้ นอกจากนี้ArrayListยังมีประสิทธิภาพและเร็วกว่าอีก ด้วย ดังนั้นคุณมักจะเห็นคลาสนี้ในรหัสดั้งเดิมเท่านั้น แต่ โครงสร้างข้อมูลแบบ Stackถูกนำมาใช้ในการเขียนโปรแกรมบ่อยมาก