Java สแต็ค

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

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

ก่อนอื่น เรามาดูกันก่อนว่าโครงสร้างข้อมูลสแต็กคืออะไร เป็นโครงสร้างข้อมูลเชิงเส้นที่อิงตามหลักการ Last-in-First-out (LIFO) เป็นการต่อต้านคิว ลองนึกภาพสำรับไพ่หรือกองหนังสือในกล่อง หนังสือที่คุณใส่ในกองก่อนจะอยู่ด้านล่าง และเล่มแรกที่เราจะนำออกจากกล่องคือหนังสือที่อยู่ด้านบนสุด นั่นคือหนังสือที่เข้าไปในกล่องเป็นคนสุดท้าย นี่คือภาพ gif เพื่อแสดงให้เห็นถึงหลักการนี้ เกิดอะไรขึ้นที่นี่? เรามีขวดที่สามารถตีได้ครั้งละหนึ่งลูกเท่านั้น ลูกแรกในขวดเป็นลูกบอลสีส้ม ตามด้วยสีม่วง และสุดท้ายเป็นสีเขียว (ขออภัยท่านที่ทราบชื่อสีเหล่านี้ถูกต้องกว่า) อย่างไรก็ตาม ในการสกัดลูกบอลสีส้มออกจากกองขวดของเรา เราต้องแยกลูกบอลที่ไปถึงก่อน (สีเขียว) ก่อน จากนั้นจึงแยกลูกบอลที่อยู่สุดท้าย (แต่ตอนสกัดนั้นเป็นลูกสุดท้าย หนึ่ง). โครงสร้างข้อมูลแบบสแตกใน 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());
       }
   }

}

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

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

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