1. เขียนไว้ข้างหน้า
คิวในโครงสร้างข้อมูลควรคุ้นเคยมากขึ้นซึ่งเป็นครั้งแรกในการออก เนื่องจากคำสั่งพวกเขาถูกตั้งชื่อเป็นคิว มันก็เหมือนกับการเข้าคิว การแทรกโหนดใหม่ที่ส่วนท้ายของด้านหน้าลบโหนดที่เฟรมเวิร์กคอลเลกชันแรก JDK ยังมีอินเทอร์เฟซคิว อินเทอร์เฟซนี้แสดงถึงคิว คิวลำดับ: arrayblockingqueue, linkedblockingqueue (สองข้างต้นเป็นคิวสีเท้า) และอีกอันหนึ่งคือ concurentlinkedqueue
การดำเนินการพื้นฐานประกอบด้วยสองประเภทของรายการรวม การดำเนินการของอาร์เรย์จะมีข้อเสียซึ่งจะทำให้เกิดความสมบูรณ์แบบเท็จ ที่จุดเริ่มต้นเมื่อคิวว่างเปล่าตัวแปรอ้างอิงของตัวแปรอ้างอิงแรกไปที่หางจะเป็นโมฆะ เมื่อองค์ประกอบของคิวถูกลบไปด้านหน้า+1 จะเกิดขึ้นและด้านหลังเท่ากับความจุของอาร์เรย์พื้นฐาน ในโครงสร้างการจัดเก็บตามลำดับด้านหน้ามักจะบันทึกดัชนีขององค์ประกอบที่กำลังจะออกจากคิวในคิวและด้านหลังมักจะบันทึกดัชนีขององค์ประกอบที่กำลังจะเข้าสู่คิว จำนวนองค์ประกอบในคิวอยู่ด้านหลัง ในคิวต่อเนื่องเลเยอร์พื้นฐานเป็นอาร์เรย์ดังนั้นองค์ประกอบข้อมูลที่บันทึกไว้จะไม่เปลี่ยนแปลงและมีเพียงสองตัวแปรอ้างอิงด้านหลังและด้านหน้าจะเปลี่ยนไป
สิ่งที่สามารถใช้ในการใช้พื้นที่อย่างมีประสิทธิภาพโดยใช้การจัดเก็บโซ่ที่นี่คือตัวแปรอ้างอิงใช้พื้นที่เพิ่มเติม
การดำเนินการทั่วไปสำหรับคิว:
1: การเริ่มต้น
2: ส่งคืนความยาวของคิว
3: เพิ่มองค์ประกอบ
4: ลบองค์ประกอบ
5: เข้าถึงองค์ประกอบส่วนหัว
6: เข้าถึงองค์ประกอบหางคู่ของคิว
7: ตรวจสอบว่าคิวว่างเปล่า
8: ล้างคิว
2. การใช้งานที่กำหนดเอง
การแสดงซอร์สโค้ดชัดเจนดังนั้นจึงไม่จำเป็นต้องแนะนำ
คลาสสาธารณะ LinkedQueue <T> {// คลาสโซ่แบบคิว-การใช้คลาสที่ไม่ใช่แบบคงที่เพื่อแสดงโหนดข้อมูลของโหนดคลาสส่วนตัวคิวโซ่โหนด {// แสดงโหนดข้อมูลของคิวโซ่ส่วนตัว T ข้อมูล; // อ้างอิงไปยังโหนดส่วนตัวโหนดถัดไปถัดไป; @suppresswarnings ("ไม่ได้ใช้") โหนดสาธารณะ () {} โหนดสาธารณะ (ข้อมูล t, โหนดถัดไป) {this.data = ข้อมูล; this.next = ถัดไป; }} // กำหนดการอ้างอิงไปยังหัวและหางของคิวโซ่หน้าโหนดส่วนตัว; โหนดส่วนตัวด้านหลัง; // กำหนดขนาดของโซ่สแต็คขนาด INT ส่วนตัว; // สร้าง linkedQueue สาธารณะที่ว่างเปล่าเป็นลูกโซ่ () {front = null; ด้านหลัง = null;} // สร้างคอลัมน์โซ่คู่ที่มีองค์ประกอบบางอย่างและมีเพียงหนึ่งโหนด public linkedqueue (องค์ประกอบ t) {front = โหนดใหม่ (องค์ประกอบ, null); // ชี้ไปที่องค์ประกอบด้านหลัง = ด้านหน้า; ขนาด ++;} // การกลับมาของ que-head-head-head ElementFront () {ถ้า (! empty ()) {return front.data;} else {return null; }} // เข้าถึงองค์ประกอบสุดท้ายของคิวสาธารณะ t elementRear () {ถ้า (! empty ()) {return rear.data; } else {return null; }} // ส่งคืนว่าคิวคู่โซ่ปัจจุบันเป็นบูลีนสาธารณะที่ว่างเปล่าว่างเปล่า () {size return == 0; } // ล้างช่องว่างสาธารณะช่องว่างสาธารณะ Clear () {front = null; ด้านหลัง = null; size = 0;} // แทรกโหนดในคิวโซ่-โมฆะสาธารณะคู่เพิ่ม (องค์ประกอบ t) {// ถ้าคอลัมน์คู่โซ่ว่างเปล่าให้สร้างโหนดใหม่ถ้า (front == null) {hear = new node (องค์ประกอบ, null); ด้านหน้า = ด้านหลัง; } else {// dynamicly สร้างโหนดโหนดใหม่ newRear = new node (องค์ประกอบ, null); rear.next = newRear; ด้านหลัง = newRear; } size ++;} // ลบโหนดในคิวโซ่และส่งคืนโหนดที่ลบสาธารณะ t ลบ () {โหนด OldFront = ด้านหน้า; front = front.next; oldfront.next = null; ขนาด--; return oldfront.data;} // ส่งคืนคิวสาธารณะสตริง toString () {// ถ้าคิวโซ่เป็นคิวโซ่ว่างเปล่าคือถ้า (ว่าง ()) {return "[]"; } else {stringbuilder sbuilder = new StringBuilder ("["); สำหรับ (โหนด current = front; current! = null; current = current.next) {sbuilder.append (current.data.toString ()+",");} int len = sbuilder.length (); ส่งคืน sbuilder.delete (len-1, len) .append ("]"). toString ();}} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {linkedqueue <String> lqueue = new LinkedQueue <String> (); lqueue.add ("AAA"); lqueue.add ("BBB"); lqueue.add ("CCC"); lqueue.add ("ddd"); system.out.println ("ส่งคืนค่าของโหนดหัวของคิว:"+lqueue.elementfront ()); system.out.println ("ส่งคืนค่าของโหนดหางของ คิว: "+lqueue.elementrear ()); System.out.println (lqueue.length ()); System.out.println (lqueue);}}ผลการทำงาน:
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น