เราเคยสัมผัสกับโครงสร้างข้อมูลหลายอย่างมาก่อนรวมถึงอาร์เรย์รายการที่เชื่อมโยงตารางแฮชและต้นไม้สีแดงและสีดำ (ต้นไม้แบบสอบถามไบนารี) วันนี้มาดูโครงสร้างข้อมูลอื่น: สแต็ก
สแต็คคืออะไร? ก่อนอื่นให้ดูตัวอย่าง: สแต็กเทียบเท่ากับถังไม้ที่แคบมาก เมื่อเรานำสิ่งต่าง ๆ เข้าไปในถังไม้และนำสิ่งต่าง ๆ ออกไปเราจะพบว่าสิ่งที่เราวางไว้ที่ด้านล่างในตอนแรกและสิ่งแรกที่เรานำออกมาคือสิ่งที่เราเพิ่งใส่เข้าไปดังนั้นสแต็กจึงเป็นภาชนะที่เข้าและออกก่อน มันมีเพียงหนึ่งปากใส่องค์ประกอบในปากนี้และนำองค์ประกอบออกมาในปากนี้ จากนั้นมาเรียนรู้สแต็กใน JDK ต่อไป
1. การแนะนำขั้นพื้นฐานและการใช้เวกเตอร์และสแต็ก
ก่อนอื่นให้ดูคำจำกัดความของ JDK:
สแต็คระดับสาธารณะ <E> ขยายเวกเตอร์ <E> {จากด้านบนเราจะเห็นว่าสแต็กนั้นสืบทอดมาจากเวกเตอร์ดังนั้นเราจึงต้องมีความเข้าใจบางอย่างเกี่ยวกับเวกเตอร์
เวกเตอร์: อาร์เรย์แบบไดนามิกที่ปลอดภัยจากเธรด
สแต็ค: การสืบทอดเวกเตอร์สแต็กที่ปลอดภัยจากเธรดที่ใช้งานตามอาร์เรย์แบบไดนามิก
1. คุณสมบัติของเวกเตอร์และสแต็ค:
เวกเตอร์และอาร์เรย์ลิสต์นั้นเหมือนกัน ความแตกต่างคือเวกเตอร์คือเธรดที่ปลอดภัยและจะเพิ่มคำหลักที่ซิงโครไนซ์ก่อนที่จะใช้วิธีการแบบเธรดที่ปลอดภัย
เวกเตอร์: ความเร็วการเข้าถึงแบบสุ่มอย่างรวดเร็วการแทรกและประสิทธิภาพการกำจัดที่ไม่ดี (ลักษณะของอาร์เรย์); รองรับองค์ประกอบที่เป็นโมฆะ มีคำสั่ง; องค์ประกอบสามารถทำซ้ำได้ ด้ายปลอดภัย;
สแต็ค: หลังเข้ามาก่อนใช้วิธีการดำเนินการสแต็กขั้นพื้นฐานบางอย่าง (อันที่จริงมันไม่เพียง แต่หลังเข้ามาเป็นครั้งแรกเพราะสืบทอดมาจากเวกเตอร์อาจมีการดำเนินการมากมายและในแง่หนึ่งมันไม่ใช่สแต็ก);
2. พ่อค้าและโครงสร้างสแต็ก:
คลาสเวกเตอร์
โดยพื้นฐานแล้วจะเหมือนกับ ArrayList และความแตกต่างหลักที่เหลืออยู่มีดังนี้:
1. เวกเตอร์เป็นเธรดที่ปลอดภัย
2. การเติบโตของ ArrayList ไม่สอดคล้องกับการเติบโตของเวกเตอร์
อื่น ๆ หากวิธีการก่อสร้างไม่สอดคล้องกันเวกเตอร์สามารถเริ่มต้นความสามารถในการสร้างด้วยวิธีการก่อสร้างและมีวิธีการอื่น ๆ เช่นวิธีการดัชนี เวกเตอร์รองรับการค้นหาและค้นหาจากตำแหน่งที่ระบุ นอกจากนี้เวกเตอร์ยังมีวิธีการซ้ำซ้อนบางอย่างที่มีฟังก์ชั่นซ้ำซ้อนเช่นวิธีการเสริมและ setElementat เหตุผลนี้เกิดจากเหตุผลทางประวัติศาสตร์ ตัวอย่างเช่นวิธีการเสริมจะถูกทิ้งไว้ก่อนหน้านี้ เมื่อมีการแนะนำเฟรมเวิร์กคอลเลกชันเวกเตอร์เข้าร่วมตระกูลคอลเลกชันและเปลี่ยนไปใช้อินเทอร์เฟซรายการ บางวิธีที่กำหนดไว้ในอินเตอร์เฟสรายการจำเป็นต้องดำเนินการ อย่างไรก็ตามด้วยเหตุผลความเข้ากันได้วิธีการเก่าไม่สามารถลบได้ดังนั้นวิธีการเก่า ๆ ที่มีความซ้ำซ้อนปรากฏขึ้น ตอนนี้มันถูกแทนที่ด้วย arraylist และโดยทั่วไปไม่ค่อยได้ใช้ดังนั้นเพียงแค่เข้าใจ
ชั้นเรียนสแต็ก
การดำเนินการพื้นฐานของสแต็กนั้นเกิดขึ้นได้ วิธีนี้มีดังนี้:
สแต็คสาธารณะ ();
สร้างสแต็กที่ว่างเปล่า
สาธารณะที่ซิงโครไนซ์ e peek ();
ส่งคืนค่าที่ด้านบนของสแต็ก
สาธารณะ e push (รายการ e);
การดำเนินการสแต็ก;
สาธารณะที่ซิงโครไนซ์สาธารณะป๊อป ();
การดำเนินการนอก
บูลีนสาธารณะว่างเปล่า ();
ตรวจสอบว่าสแต็กว่างเปล่าหรือไม่
การค้นหา int ที่ซิงโครไนซ์สาธารณะ (Object O);
ส่งคืนตำแหน่งของวัตถุในสแต็ก
สำหรับสแต็คข้างต้นเราจะใช้วิธีข้างต้นบ่อย ๆ แม้ว่ามันจะสืบทอดเวกเตอร์และมีวิธีการมากมาย แต่โดยทั่วไปจะไม่ถูกใช้ แต่มันก็ถือว่าเป็นสแต็ก
3. การใช้งานขั้นพื้นฐาน
วิธีการบางอย่างในเวกเตอร์จะใช้ดังนี้ นอกจากนี้วิธีการสำรวจเวกเตอร์นั้นเหมือนกับของ ArrayList คุณสามารถใช้ foreach, iterator และสำหรับการสำรวจแบบวนซ้ำ
นำเข้า java.util.Arrays; นำเข้า java.util.iterator; นำเข้า java.util.list; นำเข้า java.util.listiterator; นำเข้า java.util.vector; การทดสอบระดับสาธารณะ สำหรับ (int i = 0; i <10; i ++) {vector.add (i); } // print system.out.println (vector.toString ()); // size () system.out.println (vector.size ()); // มี system.out.println (vector.contains (2)); // iterator iterator <teger> iterator = vector.iterator (); ในขณะที่ (iterator.hasnext ()) {system.out.print (iterator.next () + ""); } // toarray object [] objarr = vector.toarray (); System.out.println ("/nobjarr:" + arrays.aslist (objarr)); จำนวนเต็ม [] intarr = vector.toarray (จำนวนเต็มใหม่ [vector.size ()]); System.out.println ("intarr:" + array.aslist (intarr)); // เพิ่ม vector.add (5); // ลบ vector.remove (5); System.out.println (เวกเตอร์); // containsall system.out.println (vector.containsall (array.aslist (5,6))); // addall vector.addall (array.aslist (555,666)); System.out.println (เวกเตอร์); // removeAll vector.removeAll (array.aslist (555,666)); System.out.println (เวกเตอร์); // Addall Method Vector.Addall (5, array.aslist (666,666, 6)); System.out.println (เวกเตอร์); // รับ Method System.out.println (vector.get (5)); // set method vector.set (5, 55); System.out.println (vector.get (5)); // เพิ่ม method vector.add (0, 555); System.out.println (เวกเตอร์); // ลบ method vector.remove (0); System.out.println (เวกเตอร์); // indexof method system.out.println (vector.indexof (6)); // lastIndexof method System.out.println (vector.lastindexof (6)); // listiterator method listiterator <teger> listiterator = vector.listiterator (); System.out.println (listiterator.hasprevious ()); // listiterator (ดัชนี) เมธอด listiterator <integer> ilistiterator = vector.listiterator (5); System.out.println (ilistiterator.previous ()); // วิธีการย่อย System.out.println (Vector.Sublist (5, 7)); // ล้าง vector.clear (); System.out.println (เวกเตอร์); -วิธีการบางอย่างในสแต็กจะใช้ดังนี้ เนื่องจากสแต็กสืบทอดเวกเตอร์สแต็กจึงสามารถใช้วิธีการที่เวกเตอร์สามารถใช้งานได้ รายการต่อไปนี้แสดงตัวอย่างของวิธีการที่ไม่ซ้ำกันของสแต็ก มันง่ายมากซึ่งเป็นการดำเนินการขั้นพื้นฐานของสแต็ก นอกเหนือจากวิธีการสำรวจเวกเตอร์หลายวิธีแล้วสแต็กยังมีวิธีการข้ามทางที่เป็นเอกลักษณ์ของตัวเอง (ใช้วิธีที่ว่างเปล่าและวิธีการป๊อปเพื่อให้ได้ Traversal จากด้านบนถึงด้านล่างของสแต็ก):
นำเข้า java.util.stack; การทดสอบระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สแต็ก <teeger> stack = สแต็กใหม่ <integer> (); สำหรับ (int i = 0; i <10; i ++) {stack.add (i); } system.out.println (สแต็ก); System.out.println (stack.peek ()); stack.push (555); System.out.println (สแต็ค); System.out.println (stack.pop ()); System.out.println (สแต็ค); System.out.println (stack.empty ()); System.out.println (stack.search (6)); System.out.println ("Stack Traversal:"); ในขณะที่ (! stack.empty ()) {system.out.print (stack.pop () + ""); -ส่วนย่อย:
เวกเตอร์เป็นเธรดที่ปลอดภัย แต่มีประสิทธิภาพที่ไม่ดี โดยทั่วไปจะมีการใช้ ArrayList เว้นแต่จะมีข้อกำหนดพิเศษ
หากคุณวางแผนที่จะใช้สแต็กเป็นสแต็กคุณควรติดตามการดำเนินการหลายอย่างของสแต็กอย่างตรงไปตรงมาและเคร่งครัด มิฉะนั้นมันจะมีความหมายที่จะใช้สแต็กและจะเป็นการดีกว่าที่จะใช้เวกเตอร์
2. โครงสร้างของ Vector & Stacke และที่เก็บข้อมูลพื้นฐาน
เวกเตอร์ระดับสาธารณะ <e> ขยายบทคัดย่อ <e> ใช้รายการ <e>, สุ่ม, cloneable, java.io.serializable
Vector เป็นคลาสการใช้งานของรายการ ในความเป็นจริงเวกเตอร์ยังเป็นคอนเทนเนอร์รายการตามการใช้งานอาร์เรย์ ฟังก์ชั่นและรหัสการใช้งานนั้นเหมือนกับ ArrayList แล้วอะไรที่แตกต่างกัน? หนึ่งคือเมื่อมีการขยายอาร์เรย์เวกเตอร์คือ *2 และ ArrayList คือ *1.5+1; อีกอย่างคือเวกเตอร์นั้นปลอดภัยในขณะที่ ArrayList ไม่ได้ วิธีการที่ปลอดภัยของเธรดของเวกเตอร์คือการเพิ่มคำหลักที่ซิงโครไนซ์ในแต่ละวิธีเพื่อให้แน่ใจว่า แต่ที่นี่เวกเตอร์ไม่ได้เป็นทางการอีกต่อไป (ไม่ได้รับการยอมรับจากทุกคน) และไม่แนะนำ มันเป็นทางการเนื่องจากวิธีความปลอดภัยของด้ายคือการล็อควิธีทั้งหมดซึ่งนำไปสู่ประสิทธิภาพต่ำ มีทางออกที่ดีกว่านี้หรือไม่? ในความเป็นจริงมันไม่สามารถพูดได้ว่ามีหนึ่ง แต่มีหนึ่งคอลเล็กชั่น SynchronizedList ()
เนื่องจากสแต็กได้รับการสืบทอดและขึ้นอยู่กับเวกเตอร์ลองมาดูคำจำกัดความบางอย่างและรหัสแหล่งที่มาของเวกเตอร์:
// เลเยอร์พื้นฐานใช้อาร์เรย์เพื่อจัดเก็บข้อมูลที่ได้รับการป้องกันข้อมูล [] ElementData; // จำนวนองค์ประกอบที่ป้องกัน int elementCount; // ปรับแต่งการขยายตัวของคอนเทนเนอร์และขนาดการเพิ่มความสามารถในการป้องกัน int เวกเตอร์สาธารณะ (int initialcapacity, ความสามารถ int) {super (); // ออกจากขอบเขตการตรวจสอบว่า (การเริ่มต้นความจุ <0) โยน unlegalargumentException ใหม่ ("ความสามารถที่ผิดกฎหมาย:" + การเริ่มต้นความจุ); // เริ่มต้นอาร์เรย์ this.elementData = วัตถุใหม่ [initialCapacity]; this.capacityIncrement = ความสามารถในการกำหนด; } // ใช้วิธีการล็อคคำหลักที่ซิงโครไนซ์เพื่อให้แน่ใจว่ามีเพียงเธรดเดียวเท่านั้นที่สามารถจัดการวิธีการในเวลาเดียวกันบูลีนที่ซิงโครไนซ์สาธารณะเพิ่ม (E E) {ModCount ++; // การตรวจสอบการขยายตัว ensurecapacityhelper (ElementCount + 1); ElementData [ElementCount ++] = E; กลับมาจริง; } โมฆะส่วนตัว ensurecapacityHelper (int mincapacity) {// จำนวนปัจจุบันขององค์ประกอบ int int oldCapacity = elementData .length; // จำเป็นต้องขยายความจุหรือไม่หาก (mincapacity> oldcapacity) {object [] oldData = elementData; // หากการขยายตัวของคอนเทนเนอร์ถูกปรับแต่งให้ขยายกำลังการผลิตตามความสามารถในการขยายมิฉะนั้นจะขยายกำลังการผลิตสองครั้ง (*2) int newCapacity = (ความสามารถในการผลิต> 0)? (OldCapacity + ความสามารถในการผลิต): (OldCapacity * 2); if (newCapacity <mincapacity) {newCapacity = mincapacity; } // Array Copy ElementData = array.copyof (ElementData, newCapacity); -เวกเตอร์เพียงแค่เห็นสิ่งนี้ หากไม่ได้เรียกวิธีสแต็กอื่นมันจะไม่ถูกวิเคราะห์ หากคุณไม่เข้าใจคุณสามารถตรวจสอบการวิเคราะห์ซอร์สโค้ด ArrayList
3. การวิเคราะห์วิธีการหลัก
1.Peek () - รับวัตถุที่ด้านบนของสแต็ก
/ ** * รับวัตถุที่ด้านบนของสแต็ก แต่อย่าลบ */ สาธารณะที่ซิงโครไนซ์ peek () {// จำนวนปัจจุบันขององค์ประกอบคอนเทนเนอร์ int len = size (); // หากไม่มีองค์ประกอบให้โยนข้อยกเว้นโดยตรงถ้า (len == 0) โยน emptystackexception ใหม่ (); // วิธีการโทรหาองค์ประกอบเพื่อดึงองค์ประกอบสุดท้ายของอาร์เรย์ (องค์ประกอบสุดท้ายอยู่ที่ด้านบนของสแต็ก) return elementat (len - 1); } / *** รับองค์ประกอบที่ตำแหน่งนี้ตามดัชนีดัชนีวิธีนี้อยู่ในเวกเตอร์* / public synchronized e elementat (int index) {// ออกจากขอบเขตถ้า (index> = elementCount) {โยน arrayIndExOfBoundSexception (ดัชนี + "> =" + elementCount); } // รับองค์ประกอบการส่งคืน (e) elementData [ดัชนี]; -2.Pop () - วางสแต็ก (ออกจากสแต็ค) รับวัตถุที่ด้านบนของสแต็กและลบวัตถุออกจากคอนเทนเนอร์
/ *** บัมเบิลสแต็กรับและลบวัตถุที่ด้านบนของสแต็ก*/ สาธารณะที่ซิงโครไนซ์ E POP () {// บันทึกวัตถุที่ด้านบนของสแต็ก E OBJ; // จำนวนปัจจุบันขององค์ประกอบคอนเทนเนอร์ int len = size (); // รับวัตถุที่ด้านบนของสแต็ก obj ผ่านวิธีการ peek () obj = peek (); // เรียกใช้วิธีการลบเพื่อลบวัตถุที่ด้านบนของสแต็ก requillementat (len - 1); // กลับไปที่วัตถุที่ด้านบนของสแต็กส่งคืน OBJ; } / *** ลบองค์ประกอบตามดัชนีดัชนี* / โมฆะที่ซิงโครไนซ์สาธารณะ remverElementat (INT ดัชนี) {ModCount ++; // ออกจากขอบเขตถ้า (index> = elementCount) {โยน arrayIndExOutOfBoundSexception ใหม่ (ดัชนี + "> =" + elementCount); } อื่นถ้า (ดัชนี <0) {โยน arrayIndExOutOfBoundSexception ใหม่ (ดัชนี); } // คำนวณจำนวนองค์ประกอบอาร์เรย์ที่จะย้าย int j = elementCount - ดัชนี - 1; if (j> 0) {// ย้ายอาร์เรย์ให้ลบหนึ่งอยู่ตรงกลางดังนั้นเลื่อนองค์ประกอบที่ตามมาไปข้างหน้า (ย้ายที่นี่โดยตรงเขียนทับองค์ประกอบตำแหน่งดัชนีซึ่งเทียบเท่ากับการลบ) ระบบ ArrayCopy (ElementData, INDEX + 1, ElementData, INDEX, J); } // ลบ 1 ElementCount--; // ตั้งค่าองค์ประกอบสุดท้ายของคอนเทนเนอร์ให้ว่างเปล่า (เนื่องจากองค์ประกอบถูกลบและองค์ประกอบที่อยู่เบื้องหลังดัชนีถูกย้ายไปข้างหน้าดังนั้นองค์ประกอบสุดท้ายนั้นไร้ประโยชน์) ElementData [ElementCount] = NULL; / * เพื่อให้ GC ทำงานได้ */}3.PUSH (รายการ E) - กด (ลงในสแต็ก) เพิ่มวัตถุลงในคอนเทนเนอร์และส่งคืน
/ ** * เพิ่มวัตถุลงในคอนเทนเนอร์และส่งคืน */ สาธารณะ e push (รายการ e) {// addElement การโทรไปยัง AddElement (รายการ); // ส่งคืนรายการผลตอบแทนองค์ประกอบ; } /*** เพิ่มองค์ประกอบลงในคอนเทนเนอร์ วิธีนี้อยู่ในเวกเตอร์*/ โมฆะที่ซิงโครไนซ์สาธารณะ (e obj) {modcount ++; // การตรวจสอบการขยายตัว ensurecapacityhelper (ElementCount + 1); // ใส่วัตถุลงในอาร์เรย์จำนวนองค์ประกอบ +1 ElementData [ElementCount ++] = OBJ; -4.Search (Object O) - ส่งคืนตำแหน่งของวัตถุในคอนเทนเนอร์ด้านบนของสแต็กคือ 1
/ ** * ส่งคืนตำแหน่งของวัตถุในคอนเทนเนอร์ด้านบนของสแต็กคือ 1 */ การค้นหา int ที่ซิงโครไนซ์สาธารณะ (วัตถุ o) {// ค้นหาองค์ประกอบจากอาร์เรย์จากการเกิดขึ้นครั้งสุดท้ายของ int i = lastindexof (o); // เนื่องจากด้านบนของสแต็กนับ 1 คุณต้องใช้ size () - ฉันเพื่อคำนวณว่า (i> = 0) {size return () - i; } return -1; -5. sempty () - เป็นคอนเทนเนอร์ที่ว่างเปล่า
/ *** ตรวจสอบว่าคอนเทนเนอร์ว่างเปล่า*/ บูลีนสาธารณะว่างเปล่า () {ขนาดคืน () == 0; -ส่วนย่อย:
ณ จุดนี้วิธีการสแต็กจะถูกวิเคราะห์ เนื่องจากสแต็กนั้นขึ้นอยู่กับอาร์เรย์ในที่สุดจึงยังเข้าใจง่าย (เพราะมันขึ้นอยู่กับ ArrayList)
แม้ว่าจะมีการวิเคราะห์ซอร์สโค้ดของสแต็คใน JDK แต่ก็จำเป็นที่จะต้องหารือเกี่ยวกับที่นี่ ฉันไม่รู้ว่าฉันพบว่าสแต็คที่นี่แปลกมากหรือไม่
(1) เหตุใดสแต็กจึงถูกนำไปใช้ตามอาร์เรย์
เราทุกคนรู้ถึงลักษณะของอาร์เรย์: สะดวกสำหรับการสืบค้นตามตัวห้อย (การเข้าถึงแบบสุ่ม) แต่หน่วยความจำได้รับการแก้ไขและประสิทธิภาพการขยายกำลังการผลิตต่ำ เป็นเรื่องง่ายที่จะนึกถึงสิ่งที่เหมาะสมที่สุดสำหรับสแต็กในการใช้รายการที่เชื่อมโยง
(2) ทำไมสแต็กจึงสืบทอดเวกเตอร์?
การสืบทอดหมายความว่าสแต็กสืบทอดวิธีเวกเตอร์ซึ่งทำให้สแต็กรู้สึกไม่เหมาะสมเล็กน้อยทั้งรายการและสแต็ก สิ่งที่ควรเป็นวิธีที่สมเหตุสมผลถ้าคุณต้องสืบทอดเวกเตอร์: สแต็กไม่ได้สืบทอดเวกเตอร์ แต่มีเพียงการอ้างอิงถึงเวกเตอร์เองการรวมตัวถูกต้องหรือไม่?
คำอธิบายเดียวคือสแต็กถูกสร้างขึ้นโดย JDK1.0 ในเวลานั้นคอนเทนเนอร์ใน JDK ไม่ได้มีเพียงเวกเตอร์เท่านั้นเช่น ArrayList, LinkedList ฯลฯ และเนื่องจากมีเวกเตอร์อยู่แล้วและสามารถใช้ฟังก์ชั่นสแต็กได้ - - เนื่องจากเหมาะอย่างยิ่งที่จะใช้สแต็คกับรายการที่เชื่อมโยงลองมาลองดูสิ:
นำเข้า java.util.linkedList; คลาสสาธารณะ LinkedStack <E> {Private LinkedList <E> เชื่อมโยง; Public LinkedStack () {this.linked = new LinkedList <E> (); } สาธารณะ e push (รายการ e) {this.linked .addfirst (รายการ); รายการส่งคืน; } สาธารณะ e pop () {ถ้า (this.linked.isempty ()) {return null; } return this.linked.removefirst (); } public e peek () {ถ้า (this.linked.isempty ()) {return null; } return this.linked.getFirst (); } การค้นหา int สาธารณะ (รายการ e) {int i = this.linked.indexof (รายการ); คืนฉัน + 1; } บูลีนสาธารณะว่างเปล่า () {return this.linked.isempty (); -สแต็กที่ใช้งานโดย LinkedList ใช้ที่นี่ โปรดจำไว้ว่าตามที่กล่าวไว้ใน LinkedList, LinkedList ใช้อินเทอร์เฟซ Deque เพื่อให้สามารถใช้เป็นสแต็ก (ครั้งแรกเข้าและออก) และคิว (ครั้งแรกเข้าและออก)
4. ความแตกต่างระหว่างเวกเตอร์และอาร์เรย์ลิสต์
มีสามคลาสการใช้งานในอินเทอร์เฟซรายการคือ ArrayList, Vector และ LinkedList รายการใช้เพื่อจัดเก็บองค์ประกอบหลายอย่างสามารถรักษาลำดับขององค์ประกอบและอนุญาตให้มีการทำซ้ำขององค์ประกอบ
ความแตกต่างที่เกี่ยวข้องระหว่างคลาสการใช้งานเฉพาะสามคลาสมีดังนี้:
1. ArrayList เป็นคลาสการใช้งานรายการที่ใช้กันมากที่สุดซึ่งใช้งานภายในผ่านอาร์เรย์ซึ่งช่วยให้การเข้าถึงองค์ประกอบแบบสุ่มอย่างรวดเร็ว ข้อเสียของอาร์เรย์คือไม่สามารถเว้นระยะระหว่างแต่ละองค์ประกอบ เมื่อขนาดอาร์เรย์ไม่พอใจความสามารถในการจัดเก็บจะต้องเพิ่มขึ้น มีความจำเป็นที่จะต้องบอกว่าข้อมูลของอาร์เรย์นั้นถูกคัดลอกไปยังพื้นที่เก็บข้อมูลใหม่ เมื่อแทรกหรือลบองค์ประกอบจากตำแหน่งกลางของ ArrayList อาร์เรย์จะต้องคัดลอกย้ายและค่าใช้จ่ายค่อนข้างสูง ดังนั้นจึงเหมาะสำหรับการค้นหาแบบสุ่มและการสำรวจข้ามไม่ใช่สำหรับการแทรกและการลบ
2. เวคเตอร์ยังถูกนำไปใช้ผ่านอาร์เรย์ความแตกต่างคือรองรับการซิงโครไนซ์เธรดนั่นคือในช่วงเวลาหนึ่งมีเพียงหนึ่งเธรดที่สามารถเขียนเวกเตอร์เพื่อหลีกเลี่ยงความไม่สอดคล้องกันที่เกิดจากหลายเธรดที่เขียนในเวลาเดียวกัน
3. LinkedList ใช้โครงสร้างรายการที่เชื่อมโยงเพื่อจัดเก็บข้อมูลซึ่งเหมาะมากสำหรับการแทรกแบบไดนามิกและการลบข้อมูลและการเข้าถึงแบบสุ่มและความเร็วในการเดินทางนั้นค่อนข้างช้า นอกจากนี้ยังมีวิธีการที่ไม่ได้กำหนดไว้ในอินเทอร์เฟซรายการซึ่งใช้โดยเฉพาะในการใช้งานส่วนหัวของตารางและองค์ประกอบหางและสามารถใช้เป็นสแต็กคิวและคิวแบบสองทิศทาง
5. ความเข้าใจสั้น ๆ เกี่ยวกับคิวคิวคิวคู่ปลายสองเท่า deque
1. คิว
มีการเพิ่มอินเทอร์เฟซ java.util.queue ใหม่ลงใน Java5 เพื่อรองรับการดำเนินการคิวทั่วไป อินเทอร์เฟซนี้ขยายอินเทอร์เฟซ Java.util.Collection
คิวส่วนต่อประสานสาธารณะ <E> ขยายคอลเลกชัน <E>
นอกเหนือจากการดำเนินการคอลเลกชันขั้นพื้นฐานแล้วคิวยังมีส่วนแทรกสารสกัดและตรวจสอบการดำเนินการอื่น ๆ
แต่ละวิธีมีสองรูปแบบ: หนึ่งโยนข้อยกเว้น (เมื่อการดำเนินการล้มเหลว) และอื่น ๆ ส่งคืนค่าพิเศษ (NULL หรือ FALSE ขึ้นอยู่กับการดำเนินการ)
คิวโดยปกติ (แต่ไม่จำเป็น) จัดเรียงองค์ประกอบแต่ละตัวใน FIFO (ครั้งแรกในครั้งแรก) อย่างไรก็ตามคิวลำดับความสำคัญและคิว Lifo (หรือสแต็ค) เป็นข้อยกเว้น อดีตเรียงลำดับองค์ประกอบตามลำดับธรรมชาติของตัวเปรียบเทียบหรือองค์ประกอบที่ให้มาและหลังเรียงลำดับองค์ประกอบใน LIFO (ล่าสุดในครั้งแรก)
ในคิว FIFO องค์ประกอบใหม่ทั้งหมดจะถูกแทรกที่ส่วนท้ายของคิวและองค์ประกอบการลบจะถูกลบออกจากส่วนหัวคิว
เมื่อใช้คิวให้พยายามหลีกเลี่ยงวิธีการสะสม add () และลบ () ของการรวบรวม แต่ใช้ข้อเสนอ () เพื่อเพิ่มองค์ประกอบและใช้แบบสำรวจ () เพื่อรับและลบองค์ประกอบ ข้อได้เปรียบของพวกเขาคือพวกเขาสามารถตัดสินได้ว่าความสำเร็จนั้นเกิดขึ้นได้หรือไม่โดยการคืนค่าและวิธีการเพิ่ม () และลบ () จะทำให้เกิดข้อยกเว้นเมื่อพวกเขาล้มเหลว หากคุณต้องการใช้ส่วนหน้าโดยไม่ลบองค์ประกอบให้ใช้องค์ประกอบ () หรือ PEEK ()
วิธีการเสนอสามารถแทรกองค์ประกอบไม่เช่นนั้นจะส่งคืนเท็จ สิ่งนี้แตกต่างจากวิธีการรวบรวม ADD ซึ่งสามารถล้มเหลวในการเพิ่มองค์ประกอบโดยการโยนข้อยกเว้นที่ไม่ได้ตรวจสอบ
วิธีการลบ () และโพล () ลบและส่งคืนส่วนหัวของคิว องค์ประกอบใดที่ถูกลบออกจากคิวคือฟังก์ชั่นของนโยบายการเรียงลำดับคิวซึ่งแตกต่างกันในการใช้งานที่หลากหลาย วิธีการลบ () และโพล () มีพฤติกรรมที่แตกต่างกันเฉพาะเมื่อคิวว่างเปล่า: วิธีการลบ () จะมีข้อยกเว้นในขณะที่วิธีการสำรวจความคิดเห็น () ส่งคืนโมฆะ
Element () และ Peek () กลับมา แต่อย่าลบส่วนหัวคิว
โดยทั่วไปแล้วการใช้งานคิวไม่อนุญาตให้มีการแทรกองค์ประกอบที่เป็นโมฆะแม้ว่าการใช้งานบางอย่าง (เช่น LinkedList) ไม่ได้ห้ามมิให้มีการแทรกของ nulls แม้ในการใช้งานที่อนุญาตให้ NULL ไม่ควรใส่ NULL ลงในคิวเพราะ NULL ใช้เป็นค่าคืนพิเศษสำหรับวิธีการสำรวจความคิดเห็นซึ่งบ่งชี้ว่าคิวไม่มีองค์ประกอบ
เป็นที่น่าสังเกตว่าคลาส LinkedList ใช้อินเทอร์เฟซคิวดังนั้นเราจึงสามารถใช้ LinkedList เป็นคิว
นำเข้า java.util.queue; นำเข้า java.util.linkedList; Public Class Testqueue {โมฆะสาธารณะคงที่หลัก (String [] args) {คิว <String> queue = ใหม่ LinkedList <String> (); queue.offer ("สวัสดี"); queue.offer ("World!"); queue.offer ("สวัสดี!"); System.out.println (queue.size ()); String str; ในขณะที่ ((str = queue.poll ())! = null) {system.out.print (str); } system.out.println (); System.out.println (queue.size ()); -2. Deque
อินเทอร์เฟซสาธารณะ deque <e> ขยายคิว <e>
คอลเลกชันเชิงเส้นที่รองรับการแทรกและการกำจัดองค์ประกอบที่ปลายทั้งสอง
ชื่อ deque เป็น ตัวย่อของ "คิวคู่สิ้นสุด" และมักจะอ่านเป็น "เด็ค"
การใช้งาน DEQUE ส่วนใหญ่ไม่มีขีด จำกัด คงที่เกี่ยวกับจำนวนองค์ประกอบที่สามารถมีได้ แต่อินเทอร์เฟซนี้รองรับทั้งคิวที่ จำกัด ขีดความสามารถและคิวคู่ปลายโดยไม่มีการ จำกัด ขนาดคงที่
อินเทอร์เฟซนี้กำหนดวิธีการเข้าถึงองค์ประกอบที่ปลายทั้งสองของคิวสองปลาย จัดเตรียมวิธีการแทรกลบและตรวจสอบองค์ประกอบ เนื่องจากอินเทอร์เฟซนี้สืบทอดคิวอินเทอร์เฟซคิวจึงมีสองรูปแบบสำหรับแต่ละวิธี: หนึ่งโยนข้อยกเว้นเมื่อการดำเนินการล้มเหลวและอื่น ๆ ส่งกลับค่าพิเศษ (null หรือเท็จขึ้นอยู่กับการดำเนินการ)
. เมื่อใช้คิวสองปลายเป็นคิวคุณจะได้รับพฤติกรรม FIFO (ครั้งแรก, ออกอันดับแรก) เพิ่มองค์ประกอบในตอนท้ายของคิวสองปลายและลบองค์ประกอบออกจากจุดเริ่มต้นของคิวสองปลาย วิธีการที่สืบทอดมาจากอินเทอร์เฟซคิวนั้นเทียบเท่ากับวิธี deque อย่างสมบูรณ์ดังที่แสดงในตารางต่อไปนี้:
ข. ใช้เป็น LIFO (สุดท้ายในครั้งแรก) สแต็ก อินเทอร์เฟซนี้ควรใช้ก่อนมากกว่าคลาสสแต็กดั้งเดิม เมื่อใช้คิวสองปลายเป็นสแต็กองค์ประกอบจะถูกผลักเข้าไปในจุดเริ่มต้นของคิวสองปลายและปรากฏขึ้นจากจุดเริ่มต้นของคิวสองปลาย วิธีการสแต็กนั้นเทียบเท่ากับวิธี deque อย่างสมบูรณ์ดังที่แสดงในตารางต่อไปนี้: