Selama wawancara, tumpukan dan antrian sering muncul berpasangan untuk memeriksa. Artikel ini berisi konten pengujian berikut untuk tumpukan dan antrian:
(1) Penciptaan tumpukan
(2) Penciptaan antrian
(3) Dua tumpukan menerapkan antrian
(4) Dua antrian menerapkan tumpukan
(5) Desain tumpukan dengan fungsi minimum min (), dan mensyaratkan kompleksitas waktu min, dorong, pop, dan semuanya adalah O (1)
(6) Tentukan apakah urutan push dan pop dari tumpukan konsisten
1. Penciptaan tumpukan:
Selanjutnya, kami membuat tumpukan dalam bentuk daftar tertaut untuk memfasilitasi ekspansi.
Implementasi Kode:
Stack kelas publik {public node head; Node node = node baru (data); } node public () {if (current == null) {return null;} node node = arus; Node diletakkan di tumpukan ,, saat ini kembali node return;} node {int node pre; }} public static void main (string [] args) {stack stack = new stack (); POP (). Data);Saat memasuki tumpukan, 14 atau 15 baris kode adalah kuncinya.
Efek Menjalankan:
2. Penciptaan antrian:
Ada dua bentuk penciptaan antrian: berdasarkan implementasi struktur array (antrian berurutan), dan berdasarkan implementasi struktur daftar yang ditautkan (rantai antrian).
Selanjutnya, kami akan membuat antrian dalam bentuk daftar yang ditautkan, sehingga antrian akan lebih nyaman saat berkembang. Ketika antrian didequeued, mulailah dari awal kepala simpul.
Implementasi Kode:
Saat memasuki tumpukan, itu sama dengan menambahkan node dalam daftar tertaut biasa;
Antrian kelas publik {head simpul publik; } else {current.next = node new (data); "Antrian kosong");} simpul node = head; data; i = 0; .out.println (queue.pop ());}}Efek Menjalankan:
3. Dua tumpukan menerapkan antrian:
Ide:
Stack 1 digunakan untuk menyimpan elemen, Stack 2 digunakan untuk elemen pop, negatif dan negatif adalah positif.
Sederhananya, sekarang masukkan data 1, 2, dan 3 ke dalam tumpukan satu, lalu keluar dari tumpukan satu (3, 2, 1) dan memasukkannya ke dalam tumpukan dua, kemudian data keluar dari tumpukan dua (1, 2. 3) Ini sesuai dengan aturan antrian, yaitu negatif dan negatif adalah positif.
Versi lengkap dari implementasi kode:
Impor java.util.stack;/*** Dibuat oleh Smyhvae pada 2015/9/9.*/Queue kelas publik {private stack <Integer> stack1 = stack baru <> (); // stack PR untuk melakukan operasi enqueue ivate ivate Stack <Integer> stack2 = new stack <> (); // stack untuk mengeksekusi operasi dequeue // metode: tambahkan operasi enqueue ke antrian public void push (int data) {stack1.push (data);}////Metode : Berikan antrian operasi dequeue int int pop () melempar pengecualian {if (stack2.empty ()) {// sebelum meletakkan data di stack1 ke dalam stack2, Anda harus memastikan bahwa stack2 kosong (atau kosong di awal, Entah data di Stack2 telah dirilis), jika tidak, urutan dequeuing akan kacau, yang mudah dilupakan saat (! stack1.empty ()) {stack2.push (stack1.pop ()); // buka the Data di Stack1 dan masukkan ke dalam Stack2 [Core Code]}} if (stack2.empty ()) {// Ketika Stack2 kosong, ada dua kemungkinan: 1. Di awal, dua tumpukan semua data kosong; 2. Data di Stack2 selesai melempar pengecualian baru ("queu kosong");} return stack2.pop (); Push (1); );Perhatikan urutan kode pada baris 22 dan baris 30, serta komentar, dan Anda perlu memahami maknanya dengan cermat.
Efek Menjalankan:
4. Dua antrian menerapkan tumpukan:
Ide:
Masukkan 1, 2, dan 3 ke dalam antrian 1, lalu tinggalkan 3 teratas dalam antrian 1, masukkan 2 dan 3 bawah ke dalam antrian 2, dan letakkan 3 dari antrian 1. Pada saat ini, antriannya kosong, dan kemudian semua Data antrian 2. . . Beredar pada gilirannya.
Implementasi Kode:
Impor java.util.arraydeque; impor java.util.queue;/*** Dibuat oleh Smyhvae pada 2015/9/9.*/Tumpukan kelas publik {Queue <Integer> antrian1 = arr aydeque <Integer> baru <integer> queue2 = arraydeque baru <Integer> (); // Metode: Operasi tumpukan public public (data int) {queue1.add (data); int data; {data = queue1.poll (); queue1.poll ());} lempar pengecualian baru ("stack is old"); // Saya tidak tahu apa kode di baris ini} public static void main (string [] args) melempar pengecualian {stack st ack = Stack baru (); Stack.push (1); );Efek Menjalankan:
5. Desain tumpukan dengan fungsi minimum min (), dan mensyaratkan kompleksitas waktu min, dorong, pop, dan semuanya adalah O (1). Tujuan dari metode Min adalah: dapat mengembalikan nilai minimum dalam tumpukan. 【Pertanyaan Wawancara WeChat】
Ide Biasa:
Secara umum, kita mungkin berpikir seperti ini: menggunakan variabel min, setiap kali kita menambahkan elemen, dibandingkan dengan elemen min, sehingga dapat memastikan bahwa nilai minimum yang disimpan dalam min dapat dijamin. Tetapi dalam hal ini, akan ada masalah: jika elemen terkecil keluar dari tumpukan, bagaimana Anda bisa mengetahui elemen mana yang tersisa adalah elemen terkecil?
Ide Peningkatan:
Di sini Anda perlu menambahkan tumpukan tambahan untuk menukar ruang waktu. Di tumpukan tambahan, bagian atas tumpukan selalu menghemat nilai terkecil di tumpukan saat ini. Ini spesifik: setiap kali elemen baru ditambahkan dalam tumpukan asli, itu dibandingkan dengan elemen teratas dari tumpukan tambahan Elemen besar, lalu salin elemen teratas dari tumpukan tambahan ke atas tumpukan tambahan;
Implementasi Kode Lengkap:
Impor java.util.stack;/*** Dibuat oleh Smyhvae pada 2015/9/9.*/Kelas Publik Minstack {Private Stack <Integer> Stack = Stack baru <Integer> (); Stack baru <Integer> (); /Di Auxiliary if (minstack.size () == 0 || Data <Minstack.peek ()) {Minstack.push (data); kode] Metode PEEK mengembalikan elemen di bagian atas tumpukan}} public int pop () melempar pengecualian {if (stack.size () == 0) {lempar pengecualian baru ("kosong di stack"); data = stack.pop (); hollow ");} return minstack.peek ();} public static void main (string [] args) melempar Exception {MinStack stack = new Minstack (); stack.push (4); stack.pus h (3); stack .push (5); System.out.println (stack.min ());Efek Menjalankan:
6. Tentukan apakah urutan push dan pop dari tumpukan konsisten:
Sederhananya: Diketahui bahwa satu set data 1, 2, 3, 4, dan 5 dimasukkan ke dalam tumpukan secara berurutan, jadi ada banyak cara untuk mengeluarkannya. ?
Misalnya:
data:
1, 2, 3, 4, 5
Output 1:
5, 4, 3, 2, 1 (benar)
Output 2:
4, 5, 3, 2, 1 (benar)
Output 3:
4, 3, 5, 1, 2 (kesalahan)
Kode Versi Lengkap:
Impor java.util.stack;/*** Dibuat oleh Smyhvae pada 2015/9/9.
*/
kelas publik stacktest {
// Metode: Urutan array Data1 menunjukkan urutan susun. Sekarang menilai apakah urutan susun data2 benar.
public static boolean sequenceSpop (int [] data1, int [] data2) {
Stack <Integer> Stack = Stack baru <Integer> ();
untuk (int i = 0, j = 0; i <data1.length; i ++) {
stack.push (data1 [i]);
while (stack.size ()> 0 && stack.peek () == data2 [j]) {
stack.pop ();
j ++;
}
}
return stack.size () == 0;
}
public static void main (string [] args) {
Stack <Integer> stack = stack baru <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));
}
}
Kode ini relatif ringkas, tetapi juga sulit untuk dipahami, jadi Anda perlu memahaminya dengan cermat.
Efek Menjalankan:
Di atas adalah pertanyaan wawancara klasik tentang tumpukan dan antrian Java.