خلال المقابلات ، غالبًا ما تظهر المداخن والطوابع في أزواج لفحصها. تحتوي هذه المقالة على محتويات الاختبار التالية للمكدس والقوائم:
(1) إنشاء المكدس
(2) إنشاء قائمة الانتظار
(3) اثنين من المداخن تنفذ قائمة انتظار
(4) طوابتان تنفذون كومة
(5) تصميم مكدس مع الحد الأدنى للوظيفة min () ، ويتطلب أن يكون التعقيد الزمني من دقيقة ، والدفع ، والبوب ، وجميع O (1)
(6) تحديد ما إذا كانت تسلسلات الدفع والبوب من المكدس متسقة
1. إنشاء المكدس:
بعد ذلك ، نقوم بإنشاء مكدس في شكل قائمة مرتبطة لتسهيل التوسع.
تنفيذ الكود:
Close Class {Public Node Head ؛ العقدة = العقدة الجديدة) ؛ } العقدة العامة {if (current == null) {return null ؛ يتم وضع العقدة على Node على Node {int data ؛ }} static void main (args [] pop (). data) ؛عند إدخال المكدس ، فإن 14 أو 15 سطرًا من التعليمات البرمجية هي المفتاح.
تأثير الجري:
2. إنشاء قائمة الانتظار:
هناك نوعان من إنشاء قائمة انتظار: استنادًا إلى تنفيذ بنية الصفيف (قائمة انتظار متتابعة) ، واستنادا إلى تنفيذ بنية القائمة المرتبطة (قائمة انتظار السلسلة).
بعد ذلك ، سنقوم بإنشاء قائمة انتظار في شكل قائمة مرتبطة ، بحيث تكون قائمة الانتظار أكثر ملاءمة عند التوسع. عندما يتم إزالة قائمة الانتظار ، ابدأ من بداية رأس العقدة.
تنفيذ الكود:
عند إدخال المكدس ، يكون إضافة العقد في قائمة مرتبطة عادية ؛
قائمة انتظار الفئة العامة {Public Node Head ؛ } آخر {current.next = New Node (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. المكدس <integer> stack2 = مكدس جديد <> () ؛ // مكدس لتنفيذ عملية إزالة الإزالة // الطريقة: أضف عملية enqueue إلى قائمة انتظار الفراغ العام (بيانات int) {stack1.push (data) ؛}//method : امنح قائمة الانتظار عملية dequeue public int pop () رمي الاستثناء {if (stack2.empty ()) {// قبل وضع البيانات في Stack1 في Stack2 ، يجب عليك التأكد من أن Stack2 فارغ (أو يكون فارغًا في البداية ، إما أن تم إصدار البيانات الموجودة في Stack2) ، وإلا فإن ترتيب إزالة التخلص من الدقة سيتم إفساده ، وهو أمر يسهل نسيانه بينما (! stack1.empty ()) {stack2.push (stack1.pop ()) ؛ البيانات في Stack1 ووضعها في Stack2 [CORE CODE]}} if (stack2 تم الانتهاء من البيانات في Stack2 (Queu فارغ ") ؛ 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 <integer> Queue2 = جديد arraydeque <integer> () بيانات int ؛ {data = queue1.poll () ؛ queue1.poll ()) ؛ = stack.push (1) ؛ ) ؛تأثير الجري:
5. تصميم مكدس مع الحد الأدنى للوظيفة min () ، ويتطلب أن تعقيد الوقت من دقيقة ، والدفع ، والبوب ، وجميع O (1). الغرض من طريقة MIN هو: يمكنه إرجاع الحد الأدنى للقيمة في المكدس. 【أسئلة مقابلة WeChat】
الأفكار العادية:
بشكل عام ، قد نفكر بهذه الطريقة: باستخدام متغير Min ، في كل مرة نضيف فيها عنصرًا ، يتم مقارنته بعنصر MIN ، بحيث يمكن ضمان ضمان القيمة الدنيا المخزنة في الدقيقة.但是这样的话，会存在一个问题：如果最小的元素出栈了，那怎么知道剩下的元素中哪个是最小的元素呢？
أفكار للتحسين:
هنا تحتاج إلى إضافة مكدس إضافي إلى مساحة التبادل للوقت. في المكدس الإضافي ، يحفظ الجزء العلوي من المكدس دائمًا أصغر قيمة في المكدس الحالي. It is specific: every time a new element is added in the original stack, it is compared with the top element of the auxiliary stack. If the new element is small, put the value of the new element into the auxiliary stack. If the new العنصر كبير ، ثم نسخ العنصر العلوي من المكدس المساعد إلى أعلى المكدس الإضافي ؛
تنفيذ الكود الكامل:
import java.util.Stack;/*** Created by smyhvae on 2015/9/9.*/public class MinStack {private Stack<Integer> stack = new Stack<Integer>(); private S tack<Integer> minStack = new Stack<Integer>(); //Auxiliary stack: The top of the stack always saves the smallest element in the stack public void push(int data) { stack.push(data); //Add data directly to the stack/ /في المساعد (minstack.size () == 0 || البيانات <minstack.peek ()) {minstack.push (data) ؛ code] The peek method returns the element at the top of the stack} } public int pop() throws Exception { if (stack.size() == 0) { throw new Exception("Empty in the stack"); }int البيانات = stack.pop () Hollow ") ؛} إرجاع 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 صحيحًا.
sequenceispop sequenceispop (int [] data1 ، int [] data2) {
مكدس <integer> stack = new 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 ++ ؛
}
}
إرجاع stack.size () == 0 ؛
}
الفراغ الثابت العام الرئيسي (سلسلة [] args) {
المكدس <integer> stack = new 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 (SequenseSpop (Data1 ، Data2)) ؛
System.out.println (SequenseSpop (Data1 ، Data3)) ؛
}
}
الكود موجز نسبيًا ، ولكن من الصعب أيضًا فهمه ، لذلك عليك أن تفهمها بعناية.
تأثير الجري:
ما ورد أعلاه هي أسئلة المقابلة الكلاسيكية حول Java Stack و Leaues.