ในระหว่างการสัมภาษณ์สแต็คและคิวมักจะปรากฏเป็นคู่เพื่อตรวจสอบ บทความนี้มีเนื้อหาการทดสอบต่อไปนี้สำหรับสแต็กและคิว:
(1) การสร้างสแต็ก
(2) การสร้างคิว
(3) สองสแต็คใช้คิว
(4) สองคิวใช้สแต็ก
(5) ออกแบบสแต็คที่มีฟังก์ชั่นขั้นต่ำขั้นต่ำ () และต้องการให้ความซับซ้อนของเวลาของนาที, การผลัก, ป๊อปและทั้งหมดคือ O (1)
(6) พิจารณาว่าลำดับการกดและป๊อปของสแต็กนั้นสอดคล้องกันหรือไม่
1. การสร้างสแต็ค:
ต่อไปเราจะสร้างสแต็กในรูปแบบของรายการที่เชื่อมโยงเพื่ออำนวยความสะดวกในการขยายตัว
การใช้รหัส:
สแต็กระดับสาธารณะ {หัวโหนดสาธารณะ; Node Node = New Node (ข้อมูล); } โหนดสาธารณะป๊อป () {ถ้า (current == null) {return null; โหนดที่ถูกวางไว้บนสแต็กปัจจุบันกลับมาหนึ่งโหนด;} โหนดคลาส {int data; }} โมฆะคงที่หลัก (สตริง [] args) {สแต็กสแต็ก = ใหม่สแต็ก (); stack.push (1); POP (). ข้อมูล);เมื่อป้อนสแต็กรหัส 14 หรือ 15 บรรทัดเป็นกุญแจสำคัญ
เอฟเฟกต์การทำงาน:
2. การสร้างคิว:
การสร้างคิวมีสองรูปแบบ: ขึ้นอยู่กับการใช้งานโครงสร้างอาร์เรย์ (คิวต่อเนื่อง) และขึ้นอยู่กับการใช้งานโครงสร้างรายการที่เชื่อมโยง (คิวโซ่)
ต่อไปเราจะสร้างคิวในรูปแบบของรายการที่เชื่อมโยงเพื่อให้คิวจะสะดวกยิ่งขึ้นเมื่อขยาย เมื่อคิวถูก dequeued เริ่มจากจุดเริ่มต้นของหัวโหนด
การใช้รหัส:
เมื่อเข้าสู่สแต็กมันจะเหมือนกับการเพิ่มโหนดในรายการที่เชื่อมโยงสามัญ
คิวระดับสาธารณะ {หัวโหนดสาธารณะ; } else {current.next = new node (data); "คิวว่างเปล่า"); ข้อมูล; โหนดถัดไป; โหนดสาธารณะ (int data) {this.data = ข้อมูล; i = 0; .out.println (queue.pop ());}}เอฟเฟกต์การทำงาน:
3. สองสแต็คใช้คิว:
แนวคิด:
สแต็ก 1 ใช้เพื่อจัดเก็บองค์ประกอบสแต็ก 2 ใช้สำหรับองค์ประกอบป๊อป, ลบและลบเป็นบวก
ในตอนนี้ใส่ข้อมูล 1, 2 และ 3 ลงในสแต็คหนึ่งจากนั้นออกมาจากสแต็กหนึ่ง (3, 2, 1) แล้วนำไปใส่เป็นสแต็กสองจากนั้นข้อมูลจากสแต็คสอง (1, 2.3) มันสอดคล้องกับกฎของคิวนั่นคือลบและลบเป็นบวก
เวอร์ชันเต็มของการใช้งานรหัส:
นำเข้า java.util.stack;/*** สร้างโดย Smyhvae เมื่อวันที่ 2015/9/9.*/คิวคลาสสาธารณะ {สแต็คส่วนตัว <จำนวนเต็ม> stack1 = สแต็คใหม่ <> (); // สแต็คประชาสัมพันธ์สำหรับการดำเนินการ enqueue สแต็ค <Integer> stack2 = ใหม่สแต็ก <> (); // สแต็คสำหรับการดำเนินการ dequeue การทำงาน // วิธี: เพิ่มการดำเนินการ enqueue ลงในคิวโมฆะสาธารณะพุช (ข้อมูล int) {stack1.push (data);}//วิธีการ : ให้คิวการดำเนินการ dequeue public public pop () โยนข้อยกเว้น {ถ้า (stack2.empty ()) {// ก่อนที่จะใส่ข้อมูลใน stack1 ลงใน stack2 คุณต้องตรวจสอบให้แน่ใจว่า stack2 ว่างเปล่า (หรือว่างเปล่าที่จุดเริ่มต้น ไม่ว่าจะเป็นข้อมูลใน stack2) มิฉะนั้นคำสั่งของการ dequeuing จะยุ่งเหยิงซึ่งง่ายที่จะลืมในขณะที่ (! stack1.empty ()) {stack2.push (stack1.pop ()); // เปิด The ข้อมูลใน stack1 และนำไปใช้เป็น stack2 [core code]}} ถ้า (stack2.empty ()) {// เมื่อ stack2 ว่างเปล่ามีสองความเป็นไปได้: 1. ที่จุดเริ่มต้นสองสแต็กข้อมูลทั้งหมดว่างเปล่า ข้อมูลใน stack2 เสร็จสิ้นการยกเว้นใหม่ ("queu ว่างเปล่า")} return stack2.pop (); push (1); );ให้ความสนใจกับลำดับของรหัสในบรรทัดที่ 22 และบรรทัด 30 รวมถึงความคิดเห็นและคุณต้องเข้าใจความหมายของมันอย่างรอบคอบ
เอฟเฟกต์การทำงาน:
4. สองคิวใช้สแต็ก:
แนวคิด:
ใส่ 1, 2 และ 3 ลงในคิว 1 จากนั้นออกจาก 3 อันดับแรกในคิว 1 ใส่ 2 และ 3 ลงในคิว 2 และวาง 3 ออกจากคิว 1 ในเวลานี้คิวว่างเปล่าแล้วทั้งหมด ในคิว 2 ถูกทิ้งไว้ - - หมุนเวียนในทางกลับกัน
การใช้รหัส:
นำเข้า java.util.arraydeque; นำเข้า java.util.queue;/*** สร้างโดย Smyhvae เมื่อปี 2015/9/9.*/สแต็กระดับสาธารณะ {คิว <อินเทอร์> คิว 1 = ใหม่ <teger> queue2 = new ArrayDeque <Integer> (); // วิธีการ: สแต็กการดำเนินการสาธารณะโมฆะ (ข้อมูล int) {queue1.add (ข้อมูล); ข้อมูล int; {data = queue1.poll (); queue1.poll ()); = ใหม่ stack (); stack.push (1); )); stack.push (4);เอฟเฟกต์การทำงาน:
5. ออกแบบสแต็คที่มีฟังก์ชั่นขั้นต่ำขั้นต่ำ () และต้องการให้ความซับซ้อนของเวลาของนาที, การผลัก, ป๊อปและทั้งหมดคือ o (1) วัตถุประสงค์ของวิธีการขั้นต่ำคือ: สามารถส่งคืนค่าต่ำสุดในสแต็ก 【คำถามสัมภาษณ์ WeChat 】
ความคิดทั่วไป:
โดยทั่วไปแล้วเราอาจคิดด้วยวิธีนี้: การใช้ตัวแปรขั้นต่ำทุกครั้งที่เราเพิ่มองค์ประกอบจะถูกเปรียบเทียบกับองค์ประกอบขั้นต่ำเพื่อให้มั่นใจได้ว่าค่าต่ำสุดที่เก็บไว้ในขั้นต่ำสามารถรับประกันได้ แต่ในกรณีนี้จะมีปัญหา: หากองค์ประกอบที่เล็กที่สุดอยู่นอกกองคุณจะรู้ได้อย่างไรว่าองค์ประกอบใดที่เหลืออยู่คือองค์ประกอบที่เล็กที่สุด?
แนวคิดสำหรับการปรับปรุง:
ที่นี่คุณต้องเพิ่มสแต็กเสริมเพื่อแลกเปลี่ยนพื้นที่สำหรับเวลา ในสแต็คเสริมด้านบนของสแต็กจะช่วยประหยัดค่าที่เล็กที่สุดในสแต็กปัจจุบัน มันมีความเฉพาะเจาะจง: ทุกครั้งที่มีการเพิ่มองค์ประกอบใหม่ในสแต็กดั้งเดิมมันจะถูกเปรียบเทียบกับองค์ประกอบด้านบนของสแต็กเสริม องค์ประกอบมีขนาดใหญ่จากนั้นคัดลอกองค์ประกอบด้านบนของสแต็กเสริมไปที่ด้านบนของสแต็กเสริม
การใช้งานรหัสเสร็จสมบูรณ์:
นำเข้า java.util.stack;/*** สร้างโดย Smyhvae เมื่อวันที่ 2015/9/9.*/คลาสสาธารณะ Minstack {สแต็คส่วนตัว <อินเทอร์> สแต็ก = สแต็คใหม่ <integer> (); ใหม่สแต็ก <integer> (); /ในเสริมถ้า (minstack.size () == 0 || data <minstack.peek ()) {minstack.push (ข้อมูล); รหัส] วิธีการ PEEK ส่งคืนองค์ประกอบที่ด้านบนของสแต็ก}} pop pop () pop pop () โยนข้อยกเว้น {ถ้า (stack.size () == 0) {โยนข้อยกเว้นใหม่ ("ว่างในสแต็ก"); data = stack.pop (); Hollow ");} return minstack.peek ();} โมฆะคงที่สาธารณะหลัก (สตริง [] args) พ่นข้อยกเว้น {minstack stack = new minstack (); stack.push (4); stack.pus h (3); stack; .push (5); System.out.println (stack.min ());เอฟเฟกต์การทำงาน:
6. ตรวจสอบว่าลำดับการกดและป๊อปของสแต็กนั้นสอดคล้องกันหรือไม่:
เพื่อให้ง่าย: เป็นที่ทราบกันดีว่าชุดข้อมูล 1, 2, 3, 4 และ 5 ถูกใส่ลงในสแต็กตามลำดับดังนั้นจึงมีหลายวิธีที่จะนำออกมา ?
ตัวอย่างเช่น:
ข้อมูล:
1, 2, 3, 4, 5
เอาท์พุท 1:
5, 4, 3, 2, 1 (ถูกต้อง)
เอาท์พุท 2:
4, 5, 3, 2, 1 (ถูกต้อง)
เอาท์พุท 3:
4, 3, 5, 1, 2 (ข้อผิดพลาด)
รหัสเวอร์ชันเต็ม:
นำเข้า java.util.stack;/*** สร้างโดย Smyhvae เมื่อวันที่ 2015/9/9
-
ชั้นเรียนสาธารณะ stacktest {
// วิธีการ: ลำดับของอาร์เรย์ data1 หมายถึงลำดับการซ้อน ตอนนี้ตัดสินว่าลำดับการซ้อนของ DATA2 นั้นถูกต้องหรือไม่
Public Static Boolean SequenceIspop (int [] data1, int [] data2) {
สแต็ก <integer> stack = ใหม่สแต็ก <integer> ();
สำหรับ (int i = 0, j = 0; i <data1.length; i ++) {
stack.push (data1 [i]);
ในขณะที่ (stack.size ()> 0 && stack.peek () == data2 [j]) {
stack.pop ();
J ++;
-
-
return stack.size () == 0;
-
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {
สแต็ก <Integer> stack = ใหม่สแต็ก <integer> ();
int [] data1 = {1, 2, 3, 4, 5};
int [] data2 = {4, 5, 3, 2, 1};
int [] data3 = {4, 5, 2, 3, 1};
System.out.println (SequenSeispop (data1, data2));
System.out.println (SequenSeispop (data1, data3));
-
-
รหัสค่อนข้างกระชับ แต่ก็ยากที่จะเข้าใจดังนั้นคุณต้องเข้าใจอย่างรอบคอบ
เอฟเฟกต์การทำงาน:
ข้างต้นเป็นคำถามสัมภาษณ์แบบคลาสสิกเกี่ยวกับ Java Stack และคิว