Kami telah terpapar beberapa struktur data sebelumnya, termasuk array, daftar tertaut, tabel hash, dan pohon merah dan hitam (pohon kueri biner). Hari ini, mari kita lihat struktur data lain: tumpukan.
Apa itu tumpukan? Mari kita lihat contoh pertama: tumpukan setara dengan tong kayu yang sangat sempit. Ketika kami memasukkan barang -barang ke dalam tong kayu dan mengeluarkan semuanya, kami akan menemukan bahwa hal yang kami letakkan di bagian bawah pada awalnya, dan hal pertama yang kami ambil adalah yang baru saja kami masukkan. Oleh karena itu, tumpukan adalah wadah yang pertama masuk dan keluar (FirstInlastout, atau lebih lambat masuk dan pertama). Ini hanya memiliki satu mulut, memasukkan unsur -unsur di mulut ini, dan juga mengambil unsur -unsur di mulut ini. Lalu mari kita pelajari tumpukan di JDK berikutnya.
1. Pendahuluan Dasar dan Penggunaan Vektor & Tumpukan
Pertama -tama mari kita lihat definisi JDK:
Tumpukan Kelas Publik <E> Memperluas Vektor <E> {Dari atas, kita dapat melihat bahwa tumpukan diwarisi dari vektor, jadi kita juga harus memiliki pemahaman tertentu tentang vektor.
Vektor: array dinamis yang aman-aman
Tumpukan: Warisan Vektor, tumpukan yang aman dari benang yang diimplementasikan berdasarkan array dinamis;
1. Fitur Vektor dan Tumpukan:
Vektor dan arraylist pada dasarnya sama. Perbedaannya adalah bahwa vektor aman-utas dan akan menambahkan kata kunci yang disinkronkan sebelum metode yang memungkinkan utas-aman;
Vektor: Kecepatan akses acak cepat, penyisipan yang buruk dan kinerja penghapusan (karakteristik array); mendukung elemen nol; memiliki ketertiban; Elemen dapat diulang; Thread-Safe;
Tumpukan: Setelah-dalam, pertama-keluar, mengimplementasikan beberapa metode operasi tumpukan dasar (pada kenyataannya, bukan hanya setelah-dalam, pertama-keluar, karena diwarisi dari vektor, mungkin ada banyak operasi, dan dalam arti tertentu, itu bukan tumpukan);
2. Struktur Vektor dan Tumpukan:
Kelas Vektor
Ini pada dasarnya sama dengan arraylist, dan perbedaan utama yang tersisa adalah sebagai berikut:
1. Vektor aman
2. Pertumbuhan arraylist tidak konsisten dengan pertumbuhan vektor
Lainnya, jika metode konstruksi tidak konsisten, vektor dapat menginisialisasi kapasitas melalui metode konstruksi, dan ada metode lain, seperti metode indeks. Vektor mendukung pencarian dan pencarian dari lokasi yang ditentukan; Selain itu, vektor juga memiliki beberapa metode yang berlebihan dengan fungsi duplikat, seperti metode addElement dan setElementAt. Alasan untuk ini adalah karena alasan historis. Misalnya, metode addElement tertinggal sebelumnya. Ketika kerangka kerja koleksi diperkenalkan, Vector bergabung dengan keluarga koleksi dan diubah untuk mengimplementasikan antarmuka daftar. Beberapa metode yang ditentukan dalam antarmuka daftar perlu diimplementasikan. Namun, untuk alasan kompatibilitas, metode lama tidak dapat dihapus, sehingga beberapa metode lama dengan redundansi muncul. Sekarang telah digantikan oleh ArrayList dan pada dasarnya jarang digunakan, jadi hanya mengerti.
Kelas tumpukan
Operasi dasar tumpukan terwujud. Metode ini adalah sebagai berikut:
tumpukan publik ();
Buat tumpukan kosong
E peek yang disinkronkan publik ();
Mengembalikan nilai di bagian atas tumpukan;
PUBLIK E PUBLIK (ESIT E);
Operasi tumpukan;
POP yang disinkronkan secara publik ();
Operasi Out-Stack;
boolean publik kosong ();
Tentukan apakah tumpukan kosong;
Pencarian int yang disinkronkan publik (objek o);
Mengembalikan posisi objek di tumpukan;
Untuk tumpukan di atas, kami pada dasarnya hanya akan sering menggunakan metode di atas. Meskipun mewarisi vektor dan memiliki banyak metode, pada dasarnya tidak akan digunakan, tetapi hanya diperlakukan sebagai tumpukan.
3. Penggunaan Dasar
Beberapa metode dalam vektor digunakan sebagai berikut. Selain itu, metode vektor traversal sama dengan yang ada di ArrayList. Anda dapat menggunakan foreach, iterator, dan untuk loop traversal;
import java.util.Arrays;import java.util.Iterator;import java.util.List;import java.util.ListIterator;import java.util.Vector;public class Test { public static void main(String[] args) { Vector<Integer> vector = new Vector<Integer>(); untuk (int i = 0; i <10; i ++) {vector.add (i); } // cetak system.out.println (vector.toString ()); // size () system.out.println (vector.size ()); // berisi system.out.println (vector.contains (2)); // iterator iterator <Integer> iterator = vector.iterator (); while (iterator.hasnext ()) {System.out.print (iterator.next () + "); } // objek toarray [] objarr = vector.toArray (); System.out.println ("/Nobjarr:" + arrays.aslist (objarr)); Integer [] intarr = vector.toArray (integer baru [vector.size ()]); System.out.println ("intarr:" + arrays.aslist (intarr)); // tambahkan vektor.add (5); // hapus vektor.remove (5); System.out.println (vektor); // containSall system.out.println (vector.containsall (arrays.aslist (5,6)))); // addall vector.addall (arrays.aslist (555.666)); System.out.println (vektor); // hapus vektor.removeall (arrays.aslist (555.666)); System.out.println (vektor); // Metode Addall vektor.addall (5, arrays.aslist (666.666, 6)); System.out.println (vektor); // Dapatkan metode System.out.println (vector.get (5)); // atur metode vektor.set (5, 55); System.out.println (vector.get (5)); // tambahkan metode vektor.add (0, 555); System.out.println (vektor); // Hapus metode vektor.remove (0); System.out.println (vektor); // IndexOf Metode System.out.println (vector.indexof (6)); // lastIndexof Metode System.out.println (Vector.LastIndexof (6)); // ListIterator Metode ListIterator <Integer> listIterator = vector.listIterator (); System.out.println (listiterator.hasprevious ()); // listiterator (indeks) metode listiterator <Integer> ilistiterator = vector.listiterator (5); System.out.println (ilistiterator.Previous ()); // Sublist Metode System.out.println (Vector.Sublist (5, 7)); // hapus vektor.clear (); System.out.println (vektor); }}Beberapa metode dalam tumpukan digunakan sebagai berikut. Karena Stack mewarisi vektor, Stack juga dapat menggunakan metode yang dapat digunakan vektor. Berikut ini mencantumkan beberapa contoh metode unik Stack. Ini sangat sederhana, yang merupakan operasi dasar dari tumpukan. Selain beberapa metode traversal vektor, Stack juga memiliki metode traversal yang unik (menggunakan metode kosong dan metode pop untuk mencapai traversal dari atas ke bawah tumpukan):
impor java.util.stack; tes kelas publik {public static void main (string [] args) {stack <integer> stack = stack baru <integer> (); untuk (int i = 0; i <10; i ++) {stack.add (i); } System.out.println (stack); System.out.println (stack.peek ()); stack.push (555); System.out.println (stack); System.out.println (stack.pop ()); System.out.println (stack); System.out.println (stack.empty ()); System.out.println (Stack.Search (6)); System.out.println ("Stack Traversal:"); while (! stack.empty ()) {System.out.print (stack.pop () + ""); }}}Ayat:
Vektor aman-utas, tetapi memiliki kinerja yang buruk. Secara umum, Daftar Array digunakan kecuali ada persyaratan khusus;
Jika Anda berencana untuk menggunakan tumpukan sebagai tumpukan, Anda harus dengan jujur dan ketat mengikuti beberapa operasi tumpukan. Kalau tidak, akan bermakna menggunakan tumpukan, dan akan lebih baik menggunakan vektor;
2. Struktur Vektor & Stacke dan penyimpanan yang mendasarinya
Vektor kelas publik <E> Memperluas Daftar Abstrak <E> Menerapkan Daftar <E>, RandomAccess, Kloning, Java.IO.Serializable
Vektor adalah kelas implementasi daftar. Faktanya, vektor juga merupakan wadah daftar berdasarkan implementasi array. Fungsi dan kode implementasinya pada dasarnya sama dengan ArrayList. Jadi apa bedanya? Salah satunya adalah bahwa ketika array diperluas, vektor adalah *2 dan arraylist adalah *1,5+1; Yang lainnya adalah bahwa vektor aman-utas, sedangkan arraylist tidak. Pendekatan vektor yang aman dari utas adalah menambahkan kata kunci yang disinkronkan ke setiap metode untuk memastikannya. Tapi di sini, Vektor tidak lagi secara resmi (diakui oleh semua orang) dan tidak dianjurkan. Secara resmi karena metode keamanan utasnya adalah mengunci seluruh metode, yang mengarah pada efisiensi rendah. Jadi apakah ada solusi yang lebih baik? Faktanya, tidak dapat dikatakan bahwa ada satu, tetapi benar -benar ada satu, collections.synchronizedlist ()
Karena tumpukan diwarisi dan didasarkan pada vektor, mari kita lihat beberapa definisi dan metode kode sumber vektor:
// Lapisan yang mendasarinya menggunakan array untuk menyimpan objek yang dilindungi data [] ElementData; // Jumlah elemen yang dilindungi unsur elementcount; // Kustomisasi ekspansi kontainer dan ukuran Int yang dilindungi ukuran InTIncrement; vektor publik (int initialcapacity, int capityincrement) {super (); // Exit Bounds Periksa IF (InitialCapacity <0) Lempar IllegalArgumentException baru ("Kapasitas Ilegal:" + Inisial Kapasitas); // inisialisasi array this.elementData = objek baru [initialcapacity]; this.capacityIncrement = capityIncrement; } // Gunakan metode kunci kata kunci yang disinkronkan untuk memastikan bahwa hanya satu utas yang dapat memanipulasi metode pada saat yang sama, Boolean yang disinkronkan secara publik, Tambah (E E) {ModCount ++; // Pemeriksaan Pembesaran EnsureCapacityHelper (ElementCount + 1); elementData [elementcount ++] = e; Kembali Benar; } private void ensureCapacityHelper (int mincapacity) {// Jumlah elemen saat ini int oldcapacity = elementData .length; // Apakah perlu untuk memperluas kapasitas jika (MinCapacity> Oldcapacity) {objek [] oldData = elementData; // Jika ekspansi kontainer disesuaikan, kembangkan kapasitas sesuai dengan kapasitas, jika tidak kembangkan kapasitas dengan dua kali (*2) int newcapacity = (kapasitas cetakan> 0)? (Oldcapacity + CapasityIncrement): (Oldcapacity * 2); if (newcapacity <mintcapacity) {newcapacity = mintcapacity; } // array copy elementData = arrays.copyof (elementData, newcapacity); }}Vektor cukup lihat ini. Jika metode tumpukan lainnya tidak dipanggil, itu tidak akan dianalisis. Jika Anda tidak mengerti, Anda dapat memeriksa analisis kode sumber ArrayList.
3. Analisis metode utama
1.Peek () - Dapatkan objek di bagian atas tumpukan
/ ** * Dapatkan objek di bagian atas tumpukan, tetapi jangan hapus */ publik yang disinkronkan e peek () {// Jumlah elemen kontainer saat ini int len = size (); // Jika tidak ada elemen, lempar pengecualian secara langsung jika (len == 0) lempar baru kosongStackException (); // Metode Call Elementat untuk mengambil elemen terakhir dari array (elemen terakhir berada di bagian atas tumpukan) elemen pengembalian (len - 1); } / *** Dapatkan elemen pada posisi ini sesuai dengan indeks indeks, metode ini ada di vektor* / elemen e yang disinkronkan publik (indeks int) {// Keluar dari batas jika (index> = elemencount) {lempar arrayIndexOutOfboundsException baru (index + ">" + elementcount); } // Dapatkan elemen return (e) elementData [index]; }2.pop () - Pop stack (keluar dari tumpukan), dapatkan objek di bagian atas tumpukan, dan hapus objek dari wadah
/ *** Bumble the Stack, dapatkan dan hapus objek di bagian atas stack*/ public yang disinkronkan e pop () {// Rekam objek di bagian atas stack e obj; // Jumlah elemen kontainer saat ini int len = size (); // Dapatkan objek di bagian atas stack obj melalui metode peek () obj = peek (); // Panggil metode pelepasan untuk menghapus objek di bagian atas tumpukan RemestElementat (len - 1); // kembali ke objek di bagian atas stack return obj; } / *** Hapus elemen sesuai dengan indeks indeks* / public yang disinkronkan void removeElementAt (int index) {modcount ++; // Keluar Batas if (index> = elementCount) {lempar arrayIndexOutOfBoundsException baru (index + "> =" + elementCount); } else if (index <0) {throw ArrayIndExoutOfBoundsException baru (index); } // Hitung jumlah elemen array yang akan dipindahkan int j = elementcount - index - 1; if (j> 0) {// Pindahkan array, hapus satu di tengah, jadi gerakkan elemen berikutnya (bergerak di sini langsung menimpa elemen posisi indeks, yang setara dengan penghapusan) sistem. ArrayCopy (ElementData, Indeks + 1, ElementData, Indeks, J); } // minus 1 elementcount--; // Atur elemen terakhir dari wadah untuk mengosongkan (karena suatu elemen dihapus, dan elemen -elemen di belakang indeks dipindahkan ke depan, jadi yang terakhir tidak berguna) elementData [elementcount] = null; / * untuk membiarkan GC melakukan pekerjaannya */}3.Push (e item) - Tekan (ke dalam tumpukan), tambahkan objek ke dalam wadah dan kembalikan
/ ** * Tambahkan objek ke dalam wadah dan return */ public e Push (item E) {// Panggil AddElement ke AddElement (item); // Kembalikan item pengembalian elemen; } /*** Tambahkan elemen ke dalam wadah. Metode ini ada di vektor*/ public yang disinkronkan void addelement (e obj) {modcount ++; // Pemeriksaan Pembesaran EnsureCapacityHelper (ElementCount + 1); // Masukkan objek ke dalam array, jumlah elemen +1 elementData [elementcount ++] = obj; }4.Search (Object O) - Mengembalikan posisi objek dalam wadah, bagian atas tumpukan adalah 1
/ ** * Mengembalikan posisi objek dalam wadah, bagian atas tumpukan adalah 1 */ PUBLIC PUBLIK Pencarian int (objek O) {// Temukan elemen dari array, dari kemunculan terakhir int i = lastIndexof (o); // Karena bagian atas tumpukan menghitung 1, Anda perlu menggunakan size () - i untuk menghitung if (i> = 0) {return size () - i; } return -1; }5.empty () - adalah wadah kosong
/ *** Periksa apakah wadahnya kosong*/ public boolean kosong () {return size () == 0; }Ayat:
Pada titik ini, metode tumpukan dianalisis. Karena Stack pada akhirnya didasarkan pada array, masih mudah dimengerti (karena didasarkan pada ArrayList).
Meskipun kode sumber tumpukan di JDK telah dianalisis, perlu untuk membahasnya di sini. Saya tidak tahu apakah saya menemukan bahwa tumpukan di sini sangat aneh.
(1) Mengapa Stack diimplementasikan berdasarkan array?
Kita semua tahu karakteristik array: mereka nyaman untuk kueri berdasarkan subskrip (akses acak), tetapi memori tetap dan efisiensi ekspansi kapasitas rendah. Sangat mudah untuk memikirkan hal yang paling cocok untuk Stack untuk menggunakan daftar tertaut.
(2) Mengapa Stack Warisasi Vektor?
Warisan berarti bahwa Stack mewarisi metode vektor, yang membuat Stack terasa agak tidak pantas, baik daftar maupun tumpukan. Apa yang harus menjadi pendekatan yang masuk akal jika Anda harus mewarisi vektor: Stack tidak mewarisi vektor, tetapi hanya memiliki referensi untuk vektor itu sendiri, apakah agregasi benar?
Satu -satunya penjelasan adalah bahwa tumpukan dibuat oleh JDK1.0. Pada saat itu, wadah di JDK tidak hanya memiliki vektor, seperti ArrayList, LinkedList, dll., Dan karena mereka sudah memiliki vektor dan dapat menerapkan fungsi tumpukan, lalu lakukan. . . Karena sangat ideal untuk menerapkan tumpukan dengan daftar yang ditautkan, mari kita coba:
impor java.util.linkedlist; Public Class LinkedStack <E> {Private LinkedList <E> Linked; public linkedStack () {this.linked = new LinkedList <E> (); } public e Push (item E) {this.linked .addfirst (item); item pengembalian; } public e pop () {if (this.linked.isempty ()) {return null; } return this.linked.removefirst (); } public e peek () {if (this.linked.isempty ()) {return null; } return this.linked.getFirst (); } pencarian int publik (item e) {int i = this.linked.indexof (item); return i + 1; } public boolean kosong () {return this.linked.isempty (); }}Tumpukan yang diimplementasikan oleh LinkedList digunakan di sini. Ingat seperti yang disebutkan di LinkedList, LinkedList mengimplementasikan antarmuka Deque sehingga dapat digunakan sebagai tumpukan (pertama masuk dan keluar) dan antrian (pertama masuk dan keluar).
4. Perbedaan antara Vektor & ArrayList
Ada tiga kelas implementasi dalam antarmuka daftar, yaitu Daftar Array, Vektor dan LinkedList. Daftar digunakan untuk menyimpan banyak elemen, dapat mempertahankan urutan elemen, dan memungkinkan pengulangan elemen.
Perbedaan yang relevan antara tiga kelas implementasi spesifik adalah sebagai berikut:
1. ArrayList adalah kelas implementasi daftar yang paling umum digunakan, diimplementasikan secara internal melalui array, yang memungkinkan akses acak cepat ke elemen. Kerugian array adalah bahwa tidak dapat ada spasi di antara setiap elemen. Ketika ukuran array tidak terpenuhi, kapasitas penyimpanan perlu ditingkatkan. Penting untuk mengatakan bahwa data dari array yang sudah disalin ke ruang penyimpanan baru. Saat memasukkan atau menghapus elemen dari posisi tengah daftar array, array perlu disalin, dipindahkan, dan biayanya relatif tinggi. Oleh karena itu, cocok untuk pencarian dan traversal acak, bukan untuk penyisipan dan penghapusan.
2.Vektor juga diimplementasikan melalui array, perbedaannya adalah bahwa ia mendukung sinkronisasi utas, yaitu, pada saat tertentu, hanya satu utas yang dapat menulis vektor untuk menghindari ketidakkonsistenan yang disebabkan oleh banyak tulisan utas pada saat yang sama, tetapi harganya banyak untuk mengimplementasikan sinkronisasi, sehingga mengaksesnya lebih lambat daripada mengakses daftar array.
3. LinkedList menggunakan struktur daftar tertaut untuk menyimpan data, yang sangat cocok untuk penyisipan dinamis dan penghapusan data, dan akses acak dan kecepatan traversal relatif lambat. Selain itu, ini juga menyediakan metode yang tidak didefinisikan dalam antarmuka daftar, yang secara khusus digunakan untuk mengoperasikan header tabel dan elemen ekor, dan dapat digunakan sebagai tumpukan, antrian dan antrian dua arah.
5. Pemahaman singkat tentang antrian antrian, deque antrian ganda
1. Antrian
Antarmuka java.util.queue baru telah ditambahkan ke Java5 untuk mendukung operasi antrian umum. Antarmuka ini memperluas antarmuka java.util.collection.
Antrian Publik Antrian <E> Memperluas Koleksi <E>
Selain operasi pengumpulan dasar, antrian menyediakan operasi insert, ekstrak, dan periksa lainnya.
Setiap metode memiliki dua bentuk: satu melempar pengecualian (ketika suatu operasi gagal), dan yang lainnya mengembalikan nilai khusus (nol atau false, tergantung pada operasi).
Antrian biasanya (tetapi tidak harus) mengurutkan elemen individu dalam FIFO (pertama di First Out). Namun, antrian prioritas dan antrian LIFO (atau tumpukan) adalah pengecualian. Yang pertama mengurutkan elemen -elemen sesuai dengan urutan alami dari pembanding atau elemen yang disediakan, dan yang terakhir mengurutkan elemen -elemen di LIFO (terbaru di First Out).
Dalam antrian FIFO, semua elemen baru dimasukkan pada akhir antrian, dan elemen penghapusan dihapus dari header antrian.
Saat menggunakan antrian, cobalah untuk menghindari metode pengumpulan add () dan hapus (), tetapi gunakan penawaran () untuk menambahkan elemen dan menggunakan polling () untuk mendapatkan dan menghapus elemen. Keuntungan mereka adalah bahwa mereka dapat menentukan apakah keberhasilan dicapai dengan mengembalikan nilai, dan metode add () dan hapus () akan melempar pengecualian ketika mereka gagal. Jika Anda ingin menggunakan ujung depan tanpa menghapus elemen, gunakan metode elemen () atau peek ().
Metode penawaran dapat memasukkan elemen, jika tidak ia mengembalikan false. Ini berbeda dari metode collection.add, yang hanya dapat gagal menambahkan elemen dengan melemparkan pengecualian yang tidak dicentang.
Metode lepas () dan polling () Hapus dan mengembalikan header antrian. Elemen mana yang dihapus dari antrian adalah fungsi dari kebijakan penyortiran antrian, yang berbeda dalam berbagai implementasi. Metode lepas () dan polling () berperilaku berbeda hanya ketika antrian kosong: metode hapus () melempar pengecualian, sedangkan metode polling () mengembalikan nol.
element () dan peek () kembali, tetapi jangan hapus, header antrian.
Implementasi antrian umumnya tidak memungkinkan penyisipan elemen nol, meskipun beberapa implementasi (seperti LinkedList) tidak melarang penyisipan nol. Bahkan dalam implementasi yang memungkinkan nol, nol tidak boleh dimasukkan ke dalam antrian, karena nol juga digunakan sebagai nilai pengembalian khusus untuk metode jajak pendapat, menunjukkan bahwa antrian tidak mengandung elemen.
Perlu dicatat bahwa kelas LinkedList mengimplementasikan antarmuka antrian, sehingga kita dapat menggunakan LinkedList sebagai antrian.
impor java.util.queue; impor java.util.linkedlist; Testqueue kelas publik {public static void main (string [] args) {queue <string> queue = new LinkedList <String> (); Queue.offer ("Hello"); Queue.offer ("World!"); Queue.offer ("Halo!"); System.out.println (queue.size ()); String str; while ((str = queue.poll ())! = null) {System.out.print (str); } System.out.println (); System.out.println (queue.size ()); }}2. Deque
deque antarmuka publik <E> memperluas antrian <E>
Koleksi linier yang mendukung penyisipan dan penghapusan elemen di kedua ujungnya.
Nama deque adalah singkatan dari "antrian endak ganda" dan biasanya dibaca sebagai "dek".
Sebagian besar implementasi deque tidak memiliki batas tetap pada jumlah elemen yang dapat mereka dikandung, tetapi antarmuka ini mendukung antrian terbatas kapasitas dan antrian dual-end tanpa batas ukuran tetap.
Antarmuka ini mendefinisikan metode untuk mengakses elemen di kedua ujung antrian ganda. Memberikan metode untuk memasukkan, menghapus, dan memeriksa elemen. Karena antarmuka ini mewarisi antrian antarmuka antrian, ada dua bentuk untuk masing -masing metodenya: satu melemparkan pengecualian ketika operasi gagal, dan yang lainnya mengembalikan nilai khusus (nol atau false, tergantung pada operasi).
A. Saat menggunakan antrian ganda sebagai antrian, Anda akan mendapatkan perilaku FIFO (pertama, pertama-keluar). Tambahkan elemen ke ujung antrian endapan ganda dan lepaskan elemen dari awal antrian ujung ganda. Metode yang diwarisi dari antarmuka antrian sepenuhnya setara dengan metode deque, seperti yang ditunjukkan pada tabel berikut:
B. Digunakan sebagai Lifo (Last in First Out) Tumpukan. Antarmuka ini harus digunakan terlebih dahulu daripada kelas tumpukan warisan. Saat menggunakan antrian ganda sebagai tumpukan, elemen didorong ke awal antrian endapan ganda dan muncul dari awal antrian ganda. Metode tumpukan sepenuhnya setara dengan metode deque, seperti yang ditunjukkan pada tabel berikut: