สแต็คและคิว:
โดยทั่วไปจะใช้เป็นเครื่องมือสำหรับโปรแกรมเมอร์เพื่อช่วยในการคิดของอัลกอริทึมโดยมีวงจรชีวิตสั้นและถูกสร้างขึ้นเมื่อรันไทม์เท่านั้น
การเข้าถึงถูก จำกัด และในช่วงเวลาหนึ่งข้อมูลเดียวเท่านั้นที่สามารถอ่านหรือลบได้
มันเป็นโครงสร้างที่เป็นนามธรรมโดยมีกลไกการใช้งานภายในที่ผู้ใช้มองไม่เห็นเช่นการใช้อาร์เรย์และรายการที่เชื่อมโยงเพื่อใช้สแต็ก
จำลองโครงสร้างสแต็ก
ในขณะเดียวกันข้อมูลเพียงข้อมูลเดียวเท่านั้นที่ได้รับอนุญาตให้เข้าถึงและความซับซ้อนของเวลาของการออกไปข้างหน้าครั้งแรกสำหรับทั้งในและนอกคือ O (1) นั่นคือมันไม่ได้ขึ้นอยู่กับจำนวนรายการข้อมูลในสแต็ก การดำเนินการค่อนข้างเร็วโดยใช้อาร์เรย์เป็นโครงสร้างการจัดเก็บของสแต็ก
สแต็คระดับสาธารณะ <T> {ส่วนตัวสูงสุด; ส่วนตัว t [] ary; ด้านบนสุดส่วนตัว; // ตัวชี้ตัวห้อยไปที่องค์ประกอบด้านบนของสแต็กสแต็กสแต็ก (ขนาด int) {this.max = size; ary = (t []) วัตถุใหม่ [สูงสุด]; ด้านบน = -1; } // สแต็กโมฆะสาธารณะ push (t data) {ถ้า (! isfull ()) ary [++ top] = ข้อมูล; } // สแต็กสาธารณะ t pop () {ถ้า (isempty ()) {return null; } return ary [top--]; } // ดูด้านบนของสแต็กสาธารณะ t peek () {return ary [top]; } // คือสแต็กบูลีนสาธารณะที่ว่างเปล่า isempty () {return top == -1; } // เป็นสแต็กบูลีนสาธารณะแบบเต็ม isfull () {return top == สูงสุด - 1; } // ขนาด int สาธารณะขนาด () {return top + 1; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สแต็ก <integer> stack = สแต็คใหม่ <จำนวนเต็ม> (3); สำหรับ (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ("peek:" + peek); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 0; i <5; i ++) {จำนวนเต็มป๊อป = stack.pop (); System.out.println ("ป๊อป:" + ป๊อป); System.out.println ("ขนาด:" + stack.size ()); } system.out.println ("----"); สำหรับ (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 5; i> 0; i--) {integer peek = stack.peek (); System.out.println ("peek:" + peek); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 5; i> 0; i--) {จำนวนเต็มป๊อป = stack.pop (); System.out.println ("ป๊อป:" + ป๊อป); System.out.println ("ขนาด:" + stack.size ()); - ในตัวอย่างข้างต้นมีกฎระเบียบสูงสุดเนื่องจากต้องมีขนาดอาร์เรย์ หากคุณไม่ต้องการขีด จำกัด คุณสามารถใช้โครงสร้างอื่น ๆ สำหรับการจัดเก็บและแน่นอนคุณยังสามารถใหม่อาร์เรย์ของความยาวใหม่ได้
ตัวอย่างใช้ที่เก็บข้อมูล LinkedList เพื่อใช้สแต็ก
สแต็คคลาสสาธารณะ <T> {Private LinkedList <T> DATAS; Public Stackss () {datas = new LinkedList <T> (); } // ใส่โมฆะสาธารณะสแต็ก (ข้อมูล t) {dataS.addlast (ข้อมูล); } // วางสแต็กสาธารณะ t pop () {return dataS.RemoVelast (); } // ตรวจสอบด้านบนของสแต็กสาธารณะ t peek () {return data.getLast (); } // ว่าสแต็กเป็นบูลีนสาธารณะที่ว่างเปล่า isempty () {return dataS.isempty (); } // ขนาด int สาธารณะขนาด () {return dataS.Size (); } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {สแต็ก <integer> stack = สแต็คใหม่ <จำนวนเต็ม> (3); สำหรับ (int i = 0; i <5; i ++) {stack.push (i); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ("peek:" + peek); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 0; i <5; i ++) {จำนวนเต็มป๊อป = stack.pop (); System.out.println ("ป๊อป:" + ป๊อป); System.out.println ("ขนาด:" + stack.size ()); } system.out.println ("----"); สำหรับ (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 5; i> 0; i--) {stack.push (i); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 5; i> 0; i--) {integer peek = stack.peek (); System.out.println ("peek:" + peek); System.out.println ("ขนาด:" + stack.size ()); } สำหรับ (int i = 5; i> 0; i--) {จำนวนเต็มป๊อป = stack.pop (); System.out.println ("ป๊อป:" + ป๊อป); System.out.println ("ขนาด:" + stack.size ()); -ตัวอย่างคำสั่งซื้อย้อนกลับโดยใช้โครงสร้าง statck
คลาสสาธารณะ WordReverse {โมฆะคงที่สาธารณะหลัก (String [] args) {reverse ("co., Ltd. "); } โมฆะคงที่ reverse (สตริงคำ) {ถ้า (word == null) return; สแต็ค <caricy> stack = stackss ใหม่ <carise> (); ถ่าน [] chararray = word.tochararray (); int len = chararray.length; สำหรับ (int i = 0; i <len; i ++) {stack.push (chararray [i]); } StringBuilder sb = new StringBuilder (); ในขณะที่ (! stack.isempty ()) {sb.append (stack.pop ()); } system.out.println ("หลังการผกผัน:" + sb.toString ()); -พิมพ์:
หลังจากการกลับรายการ: สไตล์โซเชียล
คิวการจำลอง (คิวทั่วไปคิวสองปลายคิวลำดับความสำคัญ)
คิว:
ครั้งแรกในการออกไปจัดการกับปัญหาการเข้าคิว คิวแรกกระบวนการแรกแถวแรกแถวที่สอง ฯลฯ กระบวนการก่อนหน้านี้เสร็จสมบูรณ์และความซับซ้อนของเวลาของการแทรกและการดำเนินการกำจัดคือ O (1) แทรกจากด้านหลังและลบคิวสองปลายออกจากด้านหน้า:
นั่นคือคุณสามารถแทรกและลบที่ปลายทั้งสองของคิว: แทรก, intright, removeleft, removeright
ฟังก์ชั่นที่มีสแต็กและคิว หากคุณลบส่วนแทรกและ removeLeft มันจะเหมือนกับสแต็ก หากคุณลบ insterletft และ removeright มันจะเหมือนกับคิว โดยทั่วไปความถี่ในการใช้งานต่ำและความซับซ้อนของเวลา o (1)
คิวลำดับความสำคัญ:
รักษาลำดับภายในเรียงลำดับตามลำดับความสำคัญ เมื่อแทรกคุณต้องเปรียบเทียบและค้นหาตำแหน่งการแทรกความซับซ้อนของเวลา o (n) ลบ o (1)
/** คิวก่อนในครั้งแรกตัวชี้ระบุตำแหน่งการแทรกและตัวชี้ระบุตำแหน่งของรายการข้อมูลที่ถูกนำออก*/ คลาสสาธารณะคิว queueq <t> {ส่วนตัว int สูงสุด; ส่วนตัว t [] ary; ด้านหน้าส่วนตัว // หัวหน้าทีมระบุตำแหน่งของรายการข้อมูลที่ถูกนำออกมาด้านหลังส่วนตัว // หางของทีมระบุตำแหน่งของรายการข้อมูลที่แทรก nitems int ส่วนตัว; // จำนวนรายการข้อมูลจริง queueq สาธารณะ (ขนาด int) {this.max = size; ary = (t []) วัตถุใหม่ [สูงสุด]; ด้านหน้า = 0; ด้านหลัง = -1; nitems = 0; } // แทรกหางของช่องว่างสาธารณะคิว (t t) {ถ้า (ด้านหลัง == สูงสุด - 1) {// มันมาถึงจุดสิ้นสุดของคิวจริงเริ่มจากจุดเริ่มต้น, ด้านหลัง = -1; } ary [++ ด้านหลัง] = t; NITEMS ++; } // ลบหัวของทีมสาธารณะ t ลบ () {t temp = ary [front ++]; ถ้า (front == สูงสุด) {// คิวมาถึงจุดสิ้นสุดเริ่มจากจุดเริ่มต้นเริ่มจากจุดเริ่มต้นเริ่มจากจุดเริ่มต้นเริ่มจากจุดเริ่มต้น 0; } nitems-; กลับอุณหภูมิ; } // ดูหัวหน้าของทีมสาธารณะ t peek () {return ary [front]; } บูลีนสาธารณะ isempty () {return nitems == 0; } บูลีนสาธารณะ isfull () {return nitems == สูงสุด; } ขนาด int สาธารณะ () {return nitems; } โมฆะคงที่สาธารณะหลัก (String [] args) {queueq <integer> queue = queueq ใหม่ <teger> (3); สำหรับ (int i = 0; i <5; i ++) {queue.insert (i); System.out.println ("ขนาด:" + queue.size ()); } สำหรับ (int i = 0; i <5; i ++) {integer peek = queue.peek (); System.out.println ("peek:" + peek); System.out.println ("ขนาด:" + queue.size ()); } สำหรับ (int i = 0; i <5; i ++) {จำนวนเต็มลบ = queue.remove (); System.out.println ("ลบ:" + ลบ); System.out.println ("ขนาด:" + queue.size ()); } system.out.println ("----"); สำหรับ (int i = 5; i> 0; i--) {queue.insert (i); System.out.println ("ขนาด:" + queue.size ()); } สำหรับ (int i = 5; i> 0; i--) {integer peek = queue.peek (); System.out.println ("peek:" + peek); System.out.println ("ขนาด:" + queue.size ()); } สำหรับ (int i = 5; i> 0; i--) {จำนวนเต็มลบ = queue.remove (); System.out.println ("ลบ:" + ลบ); System.out.println ("ขนาด:" + queue.size ()); - /** คิวสองส่วนปลาย <span style = "space สีขาว: pre"> </span> แทรกและลบที่ปลายทั้งสอง*/คลาสสาธารณะ queueqt <t> {รายการ LinkedList ส่วนตัว <T>; Queueqt () {list = new LinkedList <T> (); } // แทรกโมฆะหัวคิวสาธารณะช่องว่าง (t t) {list.addfirst (t); } // แทรกโมฆะสาธารณะของคิวหางสาธารณะช่องว่าง (t t) {list.addlast (t); } // ลบ queue head สาธารณะ t RemoveLeft () {return list.removefirst (); } // ลบจุดสิ้นสุดของ Team Public T Removeright () {return list.removelast (); } // ดูหัวหน้าทีมสาธารณะ t Peekleft () {return list.getFirst (); } // ดูจุดสิ้นสุดของทีมสาธารณะ t peekright () {return list.getLast (); } บูลีนสาธารณะ isempty () {return list.isempty (); } ขนาด int สาธารณะ () {return list.size (); - /** คิวลำดับความสำคัญถูกจัดเรียงตามลำดับความสำคัญและเป็นคิวที่สั่งซื้อ*/ คลาสสาธารณะ queueqp {ส่วนตัว int สูงสุด; ส่วนตัว int [] ary; NITEMS INT ส่วนตัว; // จำนวนรายการข้อมูลจริง queueqp สาธารณะ (ขนาด int) {this.max = size; ary = new int [max]; nitems = 0; } // แทรกจุดสิ้นสุดของช่องว่างสาธารณะคิว (int t) {int j; if (nitems == 0) {ary [nitems ++] = t; } else {สำหรับ (j = nitems-1; j> = 0; j--) {ถ้า (t> ary [j]) {ary [j + 1] = ary [j]; // กำหนดอันก่อนหน้าให้กับอันถัดไปเทียบเท่ากับการใช้การเรียงลำดับการแทรก ลำดับที่กำหนดได้รับการสั่งซื้อเดิมดังนั้นประสิทธิภาพ o (n)} อื่น {break; }} ary [j + 1] = t; NITEMS ++; } system.out.println (array.toString (ary)); } // ลบหัวของทีมสาธารณะ int ลบ () {return ary [-nitems]; // ลบลำดับความสำคัญเล็ก ๆ } // ดูลำดับความสำคัญต่ำสุดของทีมสาธารณะ peekmin () {return ary [nitems - 1]; } บูลีนสาธารณะ isempty () {return nitems == 0; } บูลีนสาธารณะ isfull () {return nitems == สูงสุด; } ขนาด int สาธารณะ () {return nitems; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {queueqp queue = ใหม่ queueqp (3); queue.insert (1); queue.insert (2); queue.insert (3); int ลบ = queue.remove (); System.out.println ("ลบ:" + ลบ); -